Consider a synchronous point-to-point network of n nodes connected by directed links, wherein each node has a binary input. This paper proves a tight necessary and sucient condition on the underlying communication topology for achieving Byzantine consensus among these nodes in the presence of up to f Byzantine faults. We derive a necessary condition, and then we provide a constructive proof of suciency by presenting a Byzantine consensus algorithm for directed graphs that satisfy the necessary condition.
Several papers have also addressed communication between a single source-receiver pair. @cite_7 studied the problem of secure communication, which achieves both fault-tolerance and perfect secrecy between a single source-receiver pair in undirected graphs, in the presence of node and link failures. Desmedt and Wang considered the same problem in directed graphs @cite_9 . In our work, we do not consider secrecy, and address the consensus problem rather than the single source-receiver pair problem. @cite_6 investigated reliable communication between a source-receiver pair in directed graphs allowing for an arbitrarily small error probability in the presence of a Byzantine failures. Our work addresses deterministically correct algorithms for consensus.
@cite_9 @cite_6 @cite_7
2088665600 75522826 2635604129 2149522963
In the unconditionally reliable message transmission (URMT) problem, two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed graph. S has a message that he wishes to send to R; the challenge is to design a protocol such that after exchanging messages as per the protocol, the receiver R should correctly obtain S's message with arbitrarily small error probability Δ, in spite of the influence of a Byzantine adversary that may actively corrupt up to t nodes in the network (we denote such a URMT protocol as (t, (1 - Δ))-reliable). While it is known that (2t + 1) vertex disjoint directed paths from S to R are necessary and sufficient for (t, 1)-reliable URMT (that is with zero error probability), we prove that a strictly weaker condition, which we define and denote as (2t, t)-special-connectivity, together with just (t+1) vertex disjoint directed paths from S to R, is necessary and sufficient for (t, (1' - Δ))-reliable URMT with arbitrarily small (but non-zero) error probability, Δ. Thus, we demonstrate the power of randomization in the context of reliable message transmission. In fact, for any positive integer k > 0, we show that there always exists a digraph Gk such that (k, 1)-reliable URMT is impossible over Gk whereas there exists a (2k, (1 - Δ))-reliable URMT protocol, Δ > 0 in Gk. In a digraph G on which (t, (1 - Δ))-reliable URMT is possible, an edge is called critical if the deletion of that edge renders (t, (1 - Δ))-reliable URMT impossible. We give an example of a digraph G on n vertices such that G has Ω(n2) critical edges. This is quite baffling since no such graph exists for the case of perfect reliable message transmission (or equivalently (t, 1)-reliable URMT) or when the underlying graph is undirected. Such is the anomalous behavior of URMT protocols (when "randomness meet directedness") that it makes it extremely hard to design efficient protocols over arbitrary digraphs. However, if URMT is possible between every pair of vertices in the network, then we present efficient protocols for the same. Three decades ago, introduced the problem of Byzantine Agreement [PSL80] where nodes need to maintain a consistent view of the world in spite of the challenge posed by Byzantine faults. Subsequently, it is well known that Byzantine agreement over a completely connected synchronous network of n nodes tolerating up to t faults is (efficiently) possible if and only if t < n 3. further empowered the nodes with the ability to authenticate themselves and their messages and proved that agreement in this new model (popularly known as authenticated Byzantine agreement (ABA)) is possible if and only if t < n. (which is a huge improvement over the bound of t < n 3 in the absence of authentication for the same functionality). To understand the utility, potential and limitations of using authentication in distributed protocols for agreement, [GGBS10] studied ABA in new light. They generalize the existing models and thus, attempt to give a unified theory of agreements over the authenticated and non-authenticated domains. In this paper we extend their results to synchronous (undirected) networks and give a complete characterization of agreement protocols. As a corollary, we show that agreement can be strictly easier than all-pair point-to-point communication. It is well known that in a synchronous network over n nodes of which up to any t are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [Dol82, DDWY93]. Thus, a folklore in the area is that maintaining global consistency (agreement) is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete networks exist only if it is possible to simulate an overlay-ed complete network. Surprisingly, we show that the folklore is not always true. Thus, it seems that agreement protocols may be more fundamental to distributed computing than reliable communication. This paper characterizes the performance in terms of queueing stability of a network composed of multiple MIMO transmitter-receiver pairs taking into account the dynamic traffic pattern and the probing feedback cost. We adopt a centralized scheduling scheme that selects a number of active pairs in each time-slot. We consider that the transmitters apply interference alignment (IA) technique if two or more pairs are active, whereas in the special case where one pair is active point-to-point MIMO singular value decomposition (SVD) is used. We consider a time-division duplex (TDD) system where transmitters acquire their channel state information (CSI) by decoding the pilot sequences sent by the receivers. Since global CSI knowledge is required for IA, the transmitters have also to exchange their estimated CSIs over a backhaul of limited capacity (i.e. imperfect case). Under this setting, we characterize in this paper the stability region of the system under both the imperfect and perfect (i.e. unlimited backhaul) cases, then we examine the gap between these two resulting regions. Further, under each case we provide a centralized probing policy that achieves the max stability region. These stability regions and scheduling policies are given for the symmetric system, where all the path loss coefficients are equal to each other, as well as for the general system. For the symmetric system, we provide the conditions under which IA yields a queueing stability gain compared to SVD. Under the general system, the adopted scheduling policy is of a high computational complexity for moderate numbers of pairs, consequently we propose an approximate policy that has a reduced complexity but that achieves only a fraction of the system stability region. A characterization of this fraction is provided. There is a rich recent literature on information-theoretically secure communication at the physical layer of wireless networks, where secret communication between a single transmitter and receiver has been studied extensively. In this paper, we consider how single-hop physical layer security techniques can be extended to multi-hop wireless networks. We show that guaranteed security can be achieved in multi-hop networks by augmenting physical layer security techniques, such as cooperative jamming, with the higher layer network mechanisms, such as routing. Specifically, we consider the secure minimum energy routing problem, in which the objective is to compute a minimum energy path between two network nodes subject to constraints on the end-to-end communication secrecy and goodput over the path. This problem is formulated as a constrained optimization of transmission power and link selection, which is proved to be NP-hard. Nevertheless, we show that efficient algorithms exist to compute both exact and approximate solutions for the problem. In particular, we develop an exact solution of pseudo-polynomial complexity, as well as an e-optimal approximation of polynomial complexity. Simulation results are also provided to show the utility of our algorithms and quantify their energy savings compared to a combination of (standard) security-agnostic minimum energy routing and physical layer security. In the simulated scenarios, we observe that, by jointly optimizing link selection at the network layer and cooperative jamming at the physical layer, our algorithms reduce the network energy consumption by half.