Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions. (English) Zbl 1321.68048
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, PODC ’11, San Jose, CA, USA, June 06–08, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0719-2). 231-238 (2011).
MSC:
| 68M12 | Network protocols |
| 68M14 | Distributed systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
common knowledge; condition-based consensus; consensus; crash failure model; renaming; synchronous message passing model; topologyReferences:
| [1] | H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R. Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524-548, 1990. 10.1145/79147.79158 · Zbl 0699.68034 |
| [2] | H. Attiya and S. Rajsbaum. The combinatorial structure of wait-free solvable tasks. SIAM Journal on Computing, 31(4):1286-1313, 2002. 10.1137/S0097539797330689 · Zbl 1015.68080 |
| [3] | 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 |
| [4] | 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 |
| [5] | 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 |
| [6] | 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 |
| [7] | D. Dolev and H. R. Strong. Polynomial algorithms for multiple processor agreement. In Proc. 14th ACM Symp. on Theory of Computing, pages 401-407, 1982. 10.1145/800070.802215 |
| [8] | R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, Cambridge, MA, 1995. · Zbl 0839.68095 |
| [9] | M. J. Fischer and N. A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14:183-186, 1981. · Zbl 0493.68026 |
| [10] | 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 |
| [11] | J. Y. Halpern and Y. Moses. Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37(3):549-587, 1990. 10.1145/79147.79161 · Zbl 0699.68115 |
| [12] | M. Herlihy and N. Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858-923, 1999. 10.1145/331524.331529 · Zbl 1161.68469 |
| [13] | M. Herlihy and M. R. Tuttle. Wait-free computation in message-passing systems. In Proc. 9th ACM Symp. on Principles of Distributed Computing, pages 347-362, August 1990. 10.1145/93385.93439 |
| [14] | L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. on Programming Languages and Systems, 4(3):382-401, 1982. 10.1145/357172.357176 · Zbl 0483.68021 |
| [15] | T. Mizrahi and Y. Moses. Continuous consensus via common knowledge. Distributed Computing, 20(5):305-321, 2008. · Zbl 1266.68040 |
| [16] | Y. Moses and M. Raynal. No double discount: Condition-based simultaneity yields limited gain. In Proc. 22nd Int. Symp. on Distributed Computing, pages 423-437, September 2008. 10.1007/978-3-540-87779-0_29 · Zbl 1161.68346 |
| [17] | Y. Moses and M. Raynal. Revisiting simultaneous consensus with crash failures. Journal of Parallel and Distributed Computing, 69(4):400-409, 2009. 10.1016/j.jpdc.2009.01.001 |
| [18] | A. Mostefaoui, S. Rajsbaum, and M. Raynal. Conditions on input vectors for consensus solvability in asynchronous distributed systems. Journal of the ACM, 50(6):922-954, 2003. 10.1145/950620.950624 · Zbl 1325.68035 |
| [19] | A. Mostéfaoui, S. Rajsbaum, and M. Raynal. Synchronous condition-based consensus. Distributed Computing, 18(5):325-343, April 2006. · Zbl 1266.68065 |
| [20] | Y. Moses and M. R. Tuttle. Programming simultaneous actions using common knowledge. Algorithmica, 3:121-169, 1988. · Zbl 0646.68031 |
| [21] | M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980. 10.1145/322186.322188 · Zbl 0434.68031 |
| [22] | M. 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 |
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.
