Relay Aided Networks and Distributed Computing: Bounds and Algorithms for Cooperative Decentralized Systems

Abstract

In this work, we consider decentralized cooperative systems for the tasks of communication and distributed computing. In these systems, a central node uses a set of n cooperating decentralized nodes to perform an otherwise difficult/complex task. We primarily focus on two such systems: (i) a Gaussian half-duplex n relay network for communicating data from a source to a destination, and (ii) an adversarial distributed computing system for the computation of matrix-vector products. This work proposes bounds and efficient algorithms to improve the computational complexity of these systems. Our first major contributions lie in the area of wireless relay networks. The Shannon capacity of Gaussian relay networks is unknown. Therefore, approximate capacity has been proposed in the literature which approximates the Shannon capacity within a constant additive gap. However, for half-duplex relay networks, computing the approximate capacity and developing relaying schemes that can achieve this approximate capacity are problems of exponential complexity. Because of this, wireless network simplification approaches have been suggested in the literature, where, instead of operating the entire network in all its exponential number of states, the operation is simplified by considering either: (i) a subset of states, or (ii) a subset of relays. In this work, we provide significant advances in both these wireless simplification approaches.First, for the scenario of using a subset of states, we consider a single-source single-destination Gaussian half-duplex n-relay network with arbitrary topology, where the source communicates with the destination through a direct link and with the help of n half-duplex relays. For these networks, we characterize sufficient conditions under which operating the network in the n+1 energy-efficient states (out of the 2^n possible states) is sufficient to achieve the approximate capacity. Specifically, these n+1 energy-efficient states are those in which at most one relay is in transmit mode while the rest of the relays are in receive mode. Under such sufficient conditions, an efficient relaying scheme is proposed, and closed-form expressions for the scheduling and the approximate capacity are provided. Next, for the scenario of using a subset of relays, we consider the Gaussian half-duplex n-relay network with the diamond topology, where a source communicates with a destination by hopping information through one layer of n non-communicating relays that operate in half-duplex. The main focus consists of investigating the following question: What is the contribution of a single relay on the approximate capacity of the entire network? We answer this question by providing a tight fundamental bound on the ratio of the approximate capacity of the highest-performing single relay to the approximate capacity of the entire network, for any number n. Surprisingly, it is shown that this ratio guarantee is f = 1/(2+2 \cos(2 \pi /(n+2))), that is a decreasing sinusoidal function of n. The second decentralized cooperative system that we consider is the framework for distributed matrix-vector product, where the server distributes the task of matrix-vector product computation among n worker nodes, out of which L are compromised (but non-colluding) and may return incorrect results. Specifically, it is assumed that the compromised workers are unreliable, that is, at any given time, each compromised worker may return an incorrect and correct result with probabilities \alpha and 1-\alpha, respectively. Thus, the tests are noisy. This work proposes three probabilistic group testing schemes to identify the unreliable/compromised workers: (i) a noise-level-independent non-adaptive scheme, (ii) a noise-level-dependent non-adaptive scheme and (iii) a noise-level-dependent 2-stage adaptive scheme. Moreover, using the proposed group testing methods, sparse parity-check codes are constructed and used in the considered distributed computing framework for efficient encoding, decoding and identification of unreliable workers. Our scheme outperforms the existing works with respect to overall computational complexity. In the aforementioned distributed computing setup, we proposed probabilistic group testing techniques for efficient identification of unreliable workers. Related group testing techniques can also be utilized in another application referred to as the sparsity-constrained community-based group testing problem, where the goal is to identify infected families in a population. In particular, the population consists of F families, each with H members. A number k_f out of the F families are infected, and a family is said to be infected if k_h out of its H members are infected. Furthermore, the sparsity constraint allows at most \rho_T individuals to be grouped in each test. For this sparsity-constrained community model, we propose a probabilistic group testing scheme to identify the infected population with a vanishing probability of error and we provide an upper-bound on the number of tests. Our scheme outperforms existing results under many interesting regimes of (k_f, k_h, F, H). Moreover, our scheme can also be applied to the classical dilution model, where it outperforms existing noise-level-independent schemes in the literature.