Modular randomized byzantine k-set agreement in asynchronous message-passing systems

ABSTRACT

k-Set agreement is a central problem of fault-tolerant distributed computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k different values are decided, and the decided values satisfy some context-depending validity condition. Synchronous message-passing algorithms solving k-set agreement have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t ≥ k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power.

Assuming t ≥ k, this paper presents a distributed algorithm that solves k-set agreement in an asynchronous message-passing system where up to t processes may commit Byzantine failures. To that end, each process is enriched with randomization power. While randomized k-set agreement algorithms exist for the asynchronous process crash failure model where t ≥ k, to our knowledge the proposed algorithm is the first that solves k-set agreement in the presence of up to t ≥ k Byzantine processes. Interestingly, this algorithm is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Its design is based on a modular construction which rests on a "no-duplicity" one-to-all broadcast abstraction, and two all-to-all communication abstractions.

References

1. Attiya H. and Welch J., Distributed computing: fundamentals, simulations and advanced topics, (2d Edition), Wiley-Interscience, 414 pages, 2004.
2. Borowsky E. and Gafni E., Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations. Proc. 25th ACM Symposium on Theory of Computing (STOC'93), ACM Press, pp. 91--100, 1993.
3. Bouzid Z., Mostéfaoui A., and Raynal M., Minimal synchrony for Byzantine consensus. Proc. 34th ACM Symposium on Principles of Distributed Computing (PODC'15), ACM Press, pp. 461--470, 2015.
4. Bracha G., Asynchronous Byzantine agreement protocols. Information & Computation, 75(2):130--143, 1987.
5. Censor Hillel K., Multi-sided shared coins and randomized set agreement. Proc. 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'10), ACM Press, pp. 60--68, 2010.
6. Chaudhuri S., More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132--158, 1993.
7. Fischer M. J., Lynch N. A., and Paterson M. S., Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374--382, 1985.
8. Friedman R., Mostéfaoui A., and Raynal M., Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems. IEEE Transactions on Dependable and Secure Computing, 2(1):46--56, 2005.
9. Gafni E. and Guerraoui R., Generalizing universality. Proc. 22nd Int'l Conference on Concurrency Theory (CONCUR'11), Springer LNCS 6901, pp. 17--27, 2011.
10. Herlihy M. P., Kozlov D., and Rajsbaum S., Distributed computing through combinatorial topology, Morgan Kaufmann/Elsevier, 336 pages, 2014.
11. Herlihy M., Shavit N., The Topological Structure of Asynchronous Computability. Journal of the ACM, 46(6):858--923, 1999.
12. Lamport L., Shostack R., and Pease M., The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3) 382--401, 1982.
13. Lynch N. A., Distributed algorithms. Morgan Kaufmann Pub., San Francisco (CA), 872 pages, 1996 (ISBN 1-55860-384-4).
14. Mostéfaoui A., Moumen H., and Raynal M., Signature-free asynchronous binary Byzantine consensus with t < n/3, O(n²) messages, and O(1) expected time. Extended version in Journal of the ACM, 62(4), Article 31, 21 pages, 2015.
15. Mostéfaoui A. and Raynal M., Randomized k-set agreement. Proc. 12nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'00), ACM Press, pp. 291--297, 2000.
16. Mostéfaoui A. and Raynal M., Signature-free broadcast-based intrusion tolerance: never decide a Byzantine value. Proc. 14th Int'l Conference On Principles Of Distributed Systems (OPODIS'10), Springer LNCS 6490, pp. 144--159, 2010.
17. Pease M., R. Shostak R., and Lamport L., Reaching agreement in the presence of faults. J. of the ACM, 27: 228--234, 1980.
18. de Prisco R., Malkhi D., and Reiter M. K., On k-Set consensus problems in asynchronous systems. IEEE Transactions on Parallel Distributed Systems, 12(1):7--21, 2001.
19. Rabin M., Randomized Byzantine generals. Proc. 24th IEEE Symposium on Foundations of Computer Science (FOCS'83), IEEE Computer Society Press, pp. 116--124, 1983.
20. Raynal M., Fault-tolerant agreement in synchronous message-passing systems. Morgan & Claypool, 165 pages, 2010 (ISBN 978-1-60845-525-6).
21. Raynal M., Concurrent programming: algorithms, principles and foundations. Springer, 515 pages, 2013 (ISBN 978-3-642-32026-2).
22. Raynal M., Stainer J., and Taubenfeld G., Distributed universality. Proc. 18th Int'l Conference on Principles of Distributed Systems (OPODIS'14), Springer LNCS 8878, pp. 469--484, 2014.
23. Saks M. and Zaharoglou F., Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM Journal on Computing, 29(5):1449--1483, 2000.
24. Srikanth T. K. and Toueg S., Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2: 80--94, 1987.
25. Toueg S., Randomized Byzantine agreement. Proc. 3rd Annual ACM Symposium on Principles of Distributed Computing (PODC'84), ACM Press, pp. 163--178, 1984.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Concurrency control

          • Process synchronization

    • Extra-functional properties

      • Software fault tolerance

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications

• Theory of computation

  • Models of computation

    • Computability