Abstract
In the k-set agreement, each process must decide on a value in such a way that no more than k different values are decided by the processes. The case where \(k=1\) corresponds to the consensus problem. For both theoretical (possibility and impossibility results) and practical (state machine replication) reasons, this problem remains crucial in distributed computing.
In this paper, we study k-set agreement in the synchronous case with Byzantine failures. By extending and fixing the results in [3], we present an (almost) complete cartography of possibility and impossibility results on the Byzantine k-set agreement in synchronous systems depending on the number of processes n, and the number of Byzantine processes t and k.
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
Similar content being viewed by others
References
Aguilera, M.K., Toueg, S.: A simple bivalency proof that t-resilient consensus requires t+ 1 rounds. Inform. Process. Lett. 71(3–4), 155–158 (1999)
Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16–18, 1993, San Diego, CA, USA pp. 91–100. ACM (1993)
Bouzid, Z., Imbs, D., Raynal, M.: A necessary condition for byzantine k-set agreement. Inform. Process. Lett. 116(12), 757–759 (2016)
Chaudhuri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Inform. Comput. 105(1), 132–158 (1993)
Chaudhuri, S., Herlihy, M., Lynch, N.A., Tuttle, M.R.: Tight bounds for k-set agreement. J. ACM 47(5), 912–943 (2000)
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)
Gafni, E., Guerraoui, R.: Generalized universality. In: Katoen, J.-P., König, B. (eds.) CONCUR 2011. LNCS, vol. 6901, pp. 17–27. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23217-6_2
Herlihy, M., Kozlov, D.N., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, Burlington (2013)
Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16–18, 1993, San Diego, CA, USA. pp. 111–120. ACM (1993)
Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999)
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. (TOPLAS) 4(3), 382–401 (1982)
Pease, M.C., Shostak, R.E., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228–234 (1980)
Raynal, M.: Fault-tolerant agreement in synchronous message-passing systems. Synth. Lect. Distrib. Comput. Theory 1(1), 1–189 (2010)
Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29(5), 1449–1483 (2000)
Acknowledgments
This work was partially supported by the French ANR project DESCARTES 16-CE40-0023-03 devoted to layered and modular structures in distributed computing and FREDDA ANR-17-CE40-0013 devoted to Formal methods for the design of distributed algorithms.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Delporte-Gallet, C., Fauconnier, H., Safir, M. (2021). Byzantine k-Set Agreement. In: Georgiou, C., Majumdar, R. (eds) Networked Systems. NETYS 2020. Lecture Notes in Computer Science(), vol 12129. Springer, Cham. https://doi.org/10.1007/978-3-030-67087-0_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-67087-0_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-67086-3
Online ISBN: 978-3-030-67087-0
eBook Packages: Computer ScienceComputer Science (R0)