Unbeatable set consensus via topological and combinatorial reasoning. (English) Zbl 1373.68081
Proceedings of the 2016 ACM symposium on principles of distributed computing, PODC ’16, Chicago, IL, USA, July 25–28, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3964-3). 107-116 (2016).
MSC:
| 68M14 | Distributed systems |
| 05E45 | Combinatorial aspects of simplicial complexes |
| 55U10 | Simplicial sets and complexes in algebraic topology |
| 68M12 | Network protocols |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
\(k\)-set consensus; knowledge; optimality; topology; unbeatability; uniform \(k\)-set consensusCitations:
Zbl 1339.68306References:
| [1] | D. Alistarh, S. Gilbert, R. Guerraoui, and C. Travers. Of choices, failures and asynchrony: The many faces of set agreement. Algorithmica, 62(1-2):595-629, 2012. 10.1007/s00453-011-9581-7 · Zbl 1236.68016 |
| [2] | E. Borowsky and E. Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proc. 25th ACM Symp. on Theory of Computing, pages 91-100, 1993. 10.1145/167088.167119 · Zbl 1310.68078 |
| [3] | A. Casta neda, Y. A. Gonczarowski, and Y. Moses. Brief announcement: Pareto-optimal solutions to consensus and set consensus. In Proc. 32nd ACM Symp. on Principles of Distributed Computing, pages 113-115, 2013. 10.1145/2484239.2484280 |
| [4] | A. Casta neda, Y. A. Gonczarowski, and Y. Moses. Unbeatable consensus. In Proc. 28th International Symp. on Distributed Computing, pages 91{106, 2014. Full version available on arXiv.} |
| [5] | A. Casta neda, Y. A. Gonczarowski, and Y. Moses. Unbeatable set consensus via topological and combinatorial reasoning. Available on arXiv.org, 2016. |
| [6] | B. Charron-Bost and A. Schiper. Uniform consensus is harder than consensus. Journal of Algorithms, 51(1):15-37, 2004. 10.1016/j.jalgor.2003.11.001 · Zbl 1078.68157 |
| [7] | S. Chaudhuri. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proc. 9th ACM Symp. on Principles of Distributed Computing, pages 311-324, 1990. 10.1145/93385.93431 |
| [8] | S. Chaudhuri, M. Herlihy, N. A. Lynch, and M. R. Tuttle. Tight bounds for k-set agreement. Journal of the ACM, 47(5):912-943, 2000. 10.1145/355483.355489 · Zbl 1320.68034 |
| [9] | B. Coan. A communication-efficient canonical form for fault-tolerant distributed protocols. In Proc. 5th ACM Symp. on Principles of Distributed Computing, pages 63-72, 1986. 10.1145/10590.10596 |
| [10] | D. Dolev, R. Reischuk, and H. R. Strong. Early stopping in Byzantine agreement. Journal of the ACM, 34(7):720-741, 1990. 10.1145/96559.96565 · Zbl 0711.68008 |
| [11] | P. Dutta, R. Guerraoui, and B. Pochon. Tight bounds on early local decisions in uniform consensus. In Proc. 17th International Symp. on Distributed Computing, pages 264-278, 2003. · Zbl 1180.68054 |
| [12] | C. Dwork and Y. Moses. Knowledge and common knowledge in a Byzantine environment: crash failures. Information and Computation, 88(2):156-186, 1990. 10.1016/0890-5401(90)90014-9 · Zbl 0705.68019 |
| [13] | M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty processor. Journal of the ACM, 32(2):374-382, 1985. 10.1145/3149.214121 · Zbl 0629.68027 |
| [14] | E. Gafni, R. Guerraoui, and B. Pochon. The complexity of early deciding set agreement. SIAM Journal on Computing, 40(1):63-78, 2011. 10.1137/050640746 · Zbl 1216.68128 |
| [15] | R. Guerraoui, M. Herlihy, and B. Pochon. A topological treatment of early-deciding set-agreement. Theoretical Computer Science, 410(6-7):570-580, 2009. 10.1016/j.tcs.2008.10.002 · Zbl 1157.68015 |
| [16] | R. Guerraoui and B. Pochon. The complexity of early deciding set agreement: How can topology help? Electr. Notes Theor. Comput. Sci., 230:71-78, 2009. 10.1016/j.entcs.2009.02.017 · Zbl 1339.68306 |
| [17] | V. Hadzilacos. On the relationship between the atomic commitment and consensus problems. In Fault-Tolerant Distributed Computing, pages 201-208, 1986. |
| [18] | J. Y. Halpern, Y. Moses, and O. Waarts. A characterization of eventual Byzantine agreement. SIAM Journal on Computing, 31(3):838-865, 2001. 10.1137/S0097539798340217 · Zbl 1017.68007 |
| [19] | M. Herlihy, D. N. Kozlov, and S. Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013. · Zbl 1341.68004 |
| [20] | M. Herlihy, Y. Moses, and M. R. Tuttle. Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions. In Proc. 30th ACM Symp. on Principles of Distributed Computing, pages 231-238, 2011. 10.1145/1993806.1993849 · Zbl 1321.68048 |
| [21] | M. Herlihy, S. Rajsbaum, and M. R. Tuttle. Unifying synchronous and asynchronous message-passing models. In Proc. 17th ACM Symp. on Principles of Distributed Computing, pages 133-142, 1998. 10.1145/277697.277722 · Zbl 1333.68061 |
| [22] | M. Herlihy and N. Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858-923, Nov. 1999. 10.1145/331524.331529 · Zbl 1161.68469 |
| [23] | I. Keidar and S. Rajsbaum. A simple proof of the uniform consensus synchronous lower bound. Information Processing Letters, 85(1):47-52, 2003. 10.1016/S0020-0190(02)00333-2 · Zbl 1042.68010 |
| [24] | Y. Moses. Relating knowledge and coordinated action: The knowledge of preconditions principle. In Proc. 15th Conference on Theoretical Aspects of Rationality and Knowledge, pages 207-216, 2015. |
| [25] | Y. Moses and M. R. Tuttle. Programming simultaneous actions using common knowledge. Algorithmica, 3:121-169, 1988. · Zbl 0646.68031 |
| [26] | P. R. Parv-edy, M. Raynal, and C. Travers. Early-stopping k-set agreement in synchronous systems prone to any number of process crashes. In Proc. 8th International Conference on Parallel Computing Technologies, pages 49-58, 2005. 10.1007/11535294_5 |
| [27] | M. Raynal. Optimal early stopping uniform consensus in synchronous systems with process omission failures. In Proc. 16th Annual ACM Symp. on Parallelism in Algorithms and Architectures, pages 302{310. ACM Press, 2004. 10.1145/1007912.1007963} |
| [28] | M. E. Saks and F. Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM Journal on Computing, 29(5):1449-1483, 2000. 10.1137/S0097539796307698 · Zbl 0952.68159 |
| [29] | X. Wang, Y. M. Teo, and J. Cao. A bivalency proof of the lower bound for uniform consensus. Information Processing Letters, 96(5):167-174, 2005. 10.1016/j.ipl.2005.08.002 · Zbl 1184.68110 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
