Gradecast is a variant of the Byzantine broadcast problem introduced by Feldman and Micali in 1988. In Gradecast, n processors would like to agree on a value sent from a leader, as well as a grade in {0, 1, 2}, such that the following three requirements are satisfied: 1) Every non-faulty processor outputs the leader’s initial value and grade 2 if the leader is non-faulty; 2) For any two non-faulty processors, if their decided grades are greater than zero, then they output the same value; and 3) For any two non-faulty processors, the difference of their decided grades is less than 2. In this work, we present a new Gradecast protocol with a total communication complexity of O(nℓ + n2log n) bits, given t < n/3, where ℓ is the message size and t is the maximum number of faulty processors tolerated in n consensus processors. The proposed protocol is an error-free and deterministic Gradecast protocol that does not rely on the authentication techniques such as signatures and secret sharing. The proposed protocol is also information-theoretic secure, i.e., it satisfies the above three requirements even if the computation power of the adversary is unbounded.

We consider a distributed computing framework where the distributed nodes have different communication capabilities, motivated by the heterogeneous networks in data centers and mobile edge computing systems. Following the structure of MapReduce, this framework consists of Map computation phase, Shuffle phase, and Reduce computation phase. The Shuffle phase allows distributed nodes to exchange intermediate values, in the presence of heterogeneous communication bottlenecks for different nodes (heterogeneous communication load constraints). For this setting, we characterize the minimum total computation load and the minimum worst-case computation load in some cases, under the heterogeneous communication load constraints. While the total computation load depends on the sum of the computation loads of all the nodes, the worst-case computation load depends on the computation load of a node with the heaviest job. We show an interesting insight that, for some cases, there is a tradeoff between the minimum total computation load and the minimum worst-case computation load, in the sense that both cannot be achieved at the same time. The achievability schemes are proposed with careful design on the file assignment and the data shuffling. Beyond the cut-set bound, a novel converse is proposed using the proof by contradiction. For the general case, we identify two extreme regimes in which both the scheme with coding and the scheme without coding are optimal, respectively.

In this work, we focus on the problem of byzantine agreement (BA), in which$n$distributed processors seek to reach an agreement on an$\ell$-bit value, but up to$t$processors might be corrupted by a Byzantine adversary and act as dishonest nodes. In particular, we consider the communication-efficient BA in an asynchronous setting, where the network communication might have arbitrarily time delay. The primary challenge of designing the BA protocol in this setting is that we need to handle both the message delay from honest nodes and the Byzantine behavior from dishonest nodes simultaneously. In this work we propose a new signature-free asynchronous byzantine agreement (ABA) protocol, which achieves the optimal communication complexity of$O(n\ell)$when$\ell\geq t\log t$, given$n\geq 5t+1$. A protocol is said to be signature-free if the protocol design does not depend on the cryptographic machinery such as hashing and signature. To the best of our knowledge, this is the first signature-free ABA protocol that achieves the optimal communication complexity of$O(n\ell)$when$\ell$is almost linearly scaled with$t$.

In communication networks secrecy constraints usually incur an extra limit in capacity or generalized degrees-of-freedom (GDoF), in the sense that a penalty in capacity or GDoF is incurred due to the secrecy constraints. Over the past decades a significant amount of effort has been made by the researchers to understand the limits of secrecy constraints in communication networks. In this work, we focus on how to remove the secrecy penalty in communication networks, i.e., how to remove the GDoF penalty due to secrecy constraints. We begin with three basic settings: a two-user symmetric Gaussian interference channel with confidential messages, a symmetric Gaussian wiretap channel with a helper, and a two-user symmetric Gaussian multiple access wiretap channel. Interestingly, in this work we show that adding common randomness at the transmitters can totally remove the penalty in GDoF or GDoF region of the three settings considered here. The results reveal that adding common randomness at the transmitters is a powerful way to remove the secrecy penalty in communication networks in terms of GDoF performance. Common randomness can be generated offline before the real-time message communication. The role of the common randomness is to jam the information signal at the eavesdroppers, without causing too much interference at the legitimate receivers. To accomplish this role, a new method of Markov chain-based interference neutralization is proposed in the achievability schemes utilizing common randomness. From the practical point of view, we need to minimize the amount of common randomness used for removing the secrecy penalty in terms of GDoF performance. With this motivation, for most of the cases we characterize the minimal GDoF of common randomness to remove secrecy penalty, based on our derived converses and achievability.

In this work we consider common randomness-aided secure communications, where a limited common randomness is available at the transmitters. Specifically, we focus on a two-user interference channel with secrecy constraints and a wiretap channel with a helper, in the presence of a limited common randomness shared between the transmitters. For both settings, we characterize the optimal secure sum degrees-of-freedom (DoF) or secure DoF as a function of the DoF of common randomness. The results reveal that the secure sum DoF or secure DoF increases as the DoF of common randomness increases, bridging the gap between the extreme DoF point without common randomness and the other extreme DoF point with unlimited common randomness. The proposed scheme is a two-layer coding scheme, in which two sub-schemes are designed in two layers respectively, i.e., at two different power levels, utilizing common randomness in the first layer only. The role of common randomness is to jam partial information signal at the eavesdroppers, without causing interference at the legitimate receivers. To prove the optimality of the proposed scheme, a new converse is also derived in this work.

In many communication networks, secrecy constraints usually incur an extra limit in capacity (or generalized degrees-of-freedom, GDoF), in the sense that a penalty in capacity (or GDoF) is incurred due to the secrecy constraints. Over the past decades a significant amount of effort has been made by the researchers to understand the limits of secrecy constraints in communication networks. In this work, we focus on how to break the limits of secrecy constraints in communication networks, i.e., how to remove the penalty in GDoF due to the secrecy constraints. We begin with three basic settings: a two-user symmetric Gaussian interference channel with confidential messages, a symmetric Gaussian wiretap channel with a helper, and a two-user symmetric Gaussian multiple access wiretap channel. Interestingly, in this work we show that adding common randomness at the transmitters can totally remove the penalty in sum GDoF or GDoF region of the three settings considered here. The results reveal that adding common randomness at the transmitters is a powerful way to break the limits of secrecy constraints in communication networks. Common randomness can be generated offline. The role of the common randomness is to jam the information signal at the eavesdroppers, without causing too much interference at the legitimate receivers. To accomplish this role, a new method of Markov chain-based interference neutralization is proposed in the achievability schemes utilizing common randomness. From the practical point of view, we hope to use less common randomness to break the limits of secrecy constraints. With this motivation, for most of the cases we characterize the minimal GDoF of common randomness to break the limits of secrecy constraints, based on our derived converses.

In many communication channels, secrecy constraintsusuallyincur a penalty in capacity, as well as generalized degrees-of-freedom (GDoF). In this paper, we show an interesting observation that adding a helper cantotallyremove the penalty in sum GDoF for a two-user symmetric Gaussian interference channel. For the interference channel where each transmitter sends a message to an intended receiver without secrecy constraints, the sum GDoF is a well-known “W” curve, characterized by Etkin–Tse–Wang in 2008. If the secrecy constraints are imposed on this interference channel, where the message of each transmitter must be secure from the unintended receiver (eavesdropper), then a GDoF penalty is incurred and the secure sum GDoF is reduced to a modified “W” curve, derived by Chen recently. In this paper, we show that, by adding a helper into this interference channel with secrecy constraints, thesecuresum GDoF turns out to be a “W” curve, which is the same as the sum GDoF of the setting without secrecy constraints. The proposed scheme is based on the cooperative jamming and a careful signal design such that the jamming signal of the helper is aligned at a specific direction and power level with the information signals of the transmitters, which allows us to totally remove the penalty in GDoF due to the secrecy constraints. Furthermore, the estimation approaches of noise removal and signal separation due to the rational independence are used in the secure rate analysis.

Motivated by mobile edge computing and wireless data centers, we study a wireless distributed computing framework where the distributed nodes exchange information over a wireless interference network. Our framework follows the structure of MapReduce. This framework consists of Map, Shuffle, and Reduce phases, where Map and Reduce are computation phases and Shuffle is a data transmission phase. In our setting, we assume that the transmission is operated over a wireless interference network. We demonstrate that, by duplicating the computation work at a cluster of distributed nodes in the Map phase, one can reduce the amount of transmission load required for the Shuffle phase. In this work, we characterize the fundamental tradeoff between computation load and communication load, under the assumption of one-shot linear schemes. The proposed scheme is based on side information cancellation and zero-forcing, and we prove that it is optimal in terms of computation-communication tradeoff. The proposed scheme outperforms the naive TDMA scheme with single node transmission at a time, as well as the coded TDMA scheme that allows coding across data, in terms of the computation-communication tradeoff.

Motivated by mobile edge computing and wireless data centers, we study a wireless distributed computing framework where the distributed nodes exchange information over a wireless interference network. Our framework follows the structure of MapReduce. This framework consists of Map, Shuffle, and Reduce phases, where Map and Reduce are computation phases and Shuffle is a data transmission phase. In our setting, we assume that the transmission is operated over a wireless interference network. We demonstrate that, by duplicating the computation work at a cluster of distributed nodes in the Map phase, one can reduce the amount of transmission load required for the Shuffle phase. In this work, we characterize the fundamental tradeoff between computation load and communication load, under the assumption of one-shot linear schemes. The proposed scheme is based on side information cancellation and zero-forcing, and we prove that it is optimal in terms of computation-communication tradeoff. The proposed scheme outperforms the naive TDMA scheme with single node transmission at a time, as well as the coded TDMA scheme that allows coding across data, in terms of the computation-communication tradeoff.