Edge Fault Tolerance on Sparse Networks

Byzantine agreement, which requires n processors (nodes) in a completely connected network to agree on a value dependent on their initial values and despite the arbitrary, possible malicious behavior of some of them, is perhaps the most popular paradigm in fault-tolerant distributed systems. However, partially connected networks are far more realistic than fully connected networks, which led Dwork, Peleg, Pippenger and Upfal [STOC'86] to formulate the notion of almost-everywhere (a. e.) agreement which shares the same aim with the original problem, except that now not all pairs of nodes are connected by reliable and authenticated channels. In such a setting, agreement amongst all correct nodes cannot be guaranteed due to possible poor connectivity with other correct nodes, and some of them must be given up. The number of such nodes is a function of the underlying communication graph and the adversarial set of nodes. In this work we introduce the notion of almost-everywhere agreement with edge corruptions which is exactly the same problem as described above, except that we additionally allow the adversary to completely control some of the communication channels between two correct nodes-i.e., to "corrupt" edges in the network. While it is easy to see that an a. e. agreement protocol for the original node-corruption model is also an a. e. agreement protocol tolerating edge corruptions (albeit for a reduced fraction of edge corruptions with respect to the bound for node corruptions), no polynomial-time protocol is known in the case where a constant fraction of the edges can be corrupted and the degree of the network is sub-linear. We make progress on this front, by constructing graphs of degree O(n(epsilon)) (for arbitrary constant 0 < epsilon < 1) on which we can run a. e. agreement protocols tolerating a constant fraction of adversarial edges. The number of given-up nodes in our construction is mu n (for some constant 0 < mu < 1 that depends on the fraction of corrupted edges), which is asymptotically optimal. We remark that allowing an adversary to corrupt edges in the network can be seen as taking a step closer towards guaranteeing a. e. agreement amongst honest nodes even on adversarially chosen communication networks, as opposed to earlier results where the communication graph is specially constructed. In addition, building upon the work of Garay and Ostrovsky [Eurocrypt'08], we obtain a protocol for a. e. secure computation tolerating edge corruptions on the above graphs.