Abstract
We present a solution to consensus on a torus with Byzantine faults. Any solution to classic consensus that is tolerant to f Byzantine faults requires \(2f+1\) node-disjoint paths. Due to limited torus connectivity, this bound necessitates spatial separation between faults. Our solution does not require this many disjoint paths and tolerates dense faults.
Specifically, we consider the case where all faults are in one column. We address the version of consensus where only processes in fault-free columns must agree. We prove that even this weaker version is not solvable if the column may be completely faulty. We then present a solution for the case where at least one row is fault-free. The correct processes share orientation but do not know the identities of other processes or the torus dimensions. The communication is synchronous.
To achieve our solution, we build and prove correct an all-to-all broadcast algorithm \(\mathcal {BAT}\) that guarantees delivery to all processes in fault-free columns. We use this algorithm to solve our weak consensus problem. Our solution, \(\mathcal {CBAT}\), runs in \(O(H+W)\) rounds, where H and W are torus height and width respectively. We extend our consensus solution to the fixed message size model where it runs in \(O(H^3W^2)\) rounds. Our results are immediately applicable if the faults are located in a single row, rather than a column.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Abraham, I., Devadas, S., Nayak, K., Ren, L.: Brief announcement: practical synchronous byzantine consensus. In: 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)
Alchieri, E.A.P., Bessani, A.N., da Silva Fraga, J., Greve, F.: Byzantine consensus with unknown participants. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 22–40. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92221-6_4
Alchieri, E.A.P., Bessani, A.N., da Silva Fraga, J., Greve, F.: Byzantine consensus with unknown participants. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 22–40. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92221-6_4
Ben-Or, M.: Another advantage of free choice (extended abstract) completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, pp. 27–30 (1983)
Bhandari, V., Vaidya, N.H.: On reliable broadcast in a radio network. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 138–147 (2005)
Chandy, K., Misra, J.: Parallel program design: a foundation. Addison Wesley Publishing Co., (1988)
Chlebus, B.S., Kowalski, D.R., Olkowski, J.: Fast agreement in networks with byzantine nodes. In: 34th International Symposium on Distributed Computing (DISC 2020) (2020)
Dolev, D.: The byzantine generals strike again. J. Algorithms 3(1), 14–30 (1982)
Dolev, D., Strong, H.R.: Authenticated algorithms for byzantine agreement. SIAM J. Comput. 12(4), 656–666 (1983)
Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26(4), 873–933 (1997)
Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. Distrib. Comput. 1, 26–39 (1986)
Ganesan, P., Yang, B., Garcia-Molina, H.: One torus to rule them all: multi-dimensional queries in P2P systems. In: Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, pp. 19–24 (2004)
Kandlur, D.D., Shin, K.G.: Reliable broadcast algorithms for harts. ACM Trans. Comput. Syst. (TOCS) 9(4), 374–398 (1991)
Katz, J., Koo, C.-Y.: On expected constant-round protocols for byzantine agreement. J. Comput. Syst. Sci. 75(2), 91–112 (2009)
Koo, C.-Y.: Broadcast in radio networks tolerating byzantine adversarial behavior. In: Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing, pp. 275–282 (2004)
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)
Maurer, A., Tixeuil, S.: Byzantine broadcast with fixed disjoint paths. J. Parallel Distrib. Comput. 74(11), 3153–3160 (2014)
Nesterenko, M., Tixeuil, S.: Discovering network topology in the presence of byzantine faults. In: International Colloquium on Structural Information and Communication Complexity, pages 212–226. Springer, Berlin, Heidelberg (2006). https://doi.org/10.1007/11780823_17
Oglio, J., Hood, K., Sharma, G., Nesterenko, M.: Byzantine Geoconsensus. In: Echihabi, K., Meyer, R. (eds.) NETYS 2021. LNCS, vol. 12754, pp. 19–35. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-91014-3_2
Oglio, J., Hood, K., Sharma, G., Nesterenko, M.: Consensus on unknown torus with dense byzantine faults. arXiv preprint arXiv:2303.12870 (2023)
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM (JACM) 27(2), 228–234 (1980)
Pelc, A., Peleg, D.: Broadcasting with locally bounded byzantine faults. Inf. Process. Lett. 93(3), 109–115 (2005)
Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM (2000)
Rabin, M.O.: Randomized byzantine generals. In: 24th Annual Symposium on Foundations of Computer Science (SFCS 1983), pp. 403–409. IEEE (1983)
Tseng, L., Vaidya, N.H.: Fault-tolerant consensus in directed graphs. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 451–460 (2015)
Winkler, K., Schwarz, M., Schmid, U.: Consensus in rooted dynamic networks with short-lived stability. Distrib. Comput. 32(5), 443–458 (2019). https://doi.org/10.1007/s00446-019-00348-0
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Oglio, J., Hood, K., Sharma, G., Nesterenko, M. (2023). Consensus on an Unknown Torus with Dense Byzantine Faults. In: Mohaisen, D., Wies, T. (eds) Networked Systems. NETYS 2023. Lecture Notes in Computer Science, vol 14067. Springer, Cham. https://doi.org/10.1007/978-3-031-37765-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-37765-5_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-37764-8
Online ISBN: 978-3-031-37765-5
eBook Packages: Computer ScienceComputer Science (R0)