Abstract
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 ε) (for arbitrary constant 0 < ε < 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 μn (for some constant 0 < μ < 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.
A full version of this paper, entitled “Almost-Everywhere Secure Computation with Edge Corruptions,” is available at http://eprint.iacr.org/2012/221.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: STOC 1988 (1988)
Chandran, N., Garay, J., Ostrovsky, R.: Almost-everywhere secure computation with edge corruptions. Cryptology ePrint Archive, Report 2012/221, http://eprint.iacr.org/
Chandran, N., Garay, J., Ostrovsky, R.: Improved Fault Tolerance and Secure Computation on Sparse Networks. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part II. LNCS, vol. 6199, pp. 249–260. Springer, Heidelberg (2010)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (abstract). In: STOC 1988 (1988)
Dwork, C., Peleg, D., Pippenger, N., Upfal, E.: Fault tolerance in networks of bounded degree (preliminary version). In: STOC 1986 (1986)
Fitzi, M., Garay, J.: Efficient player-optimal protocols for strong and differential consensus. In: PODC 2003 (2003)
Garay, J., Givens, C., Ostrovsky, R.: Secure Message Transmission by Public Discussion: A Brief Survey. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 126–141. Springer, Heidelberg (2011)
Garay, J.A., Ostrovsky, R.: Almost-Everywhere Secure Computation. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 307–323. Springer, Heidelberg (2008)
King, V., Saia, J., Sanwalani, V., Vee, E.: Towards secure and scalable computation in peer-to-peer networks. In: FOCS 2006 (2006)
Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Transactions on Programming Languages and Systems 4(3) (1982)
Neiger, G.: Distributed consensus revisited. Information Processing Letters 49(4), 195–201 (1994)
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. Journal of the ACM (1980)
Upfal, E.: Tolerating linear number of faults in networks of bounded degree. In: PODC 1992 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chandran, N., Garay, J., Ostrovsky, R. (2012). Edge Fault Tolerance on Sparse Networks. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds) Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31585-5_41
Download citation
DOI: https://doi.org/10.1007/978-3-642-31585-5_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31584-8
Online ISBN: 978-3-642-31585-5
eBook Packages: Computer ScienceComputer Science (R0)