François Bonnet
Abstract
This article addresses the consensus problem in asynchronous systems prone to process crashes, where additionally the processes are anonymous (they cannot be distinguished one from the other: they have no name and execute the same code). To circumvent the three computational adversaries (asynchrony, failures, and anonymity) each process is provided with a failure detector of a class denoted ψ, that gives it an upper bound on the number of processes that are currently alive (in a nonanonymous system, the classes ψ and P---the class of perfect failure detectors---are equivalent).
The article first presents a simple ψ-based consensus algorithm where the processes decide in 2t + 1 asynchronous rounds (where t is an upper bound on the number of faulty processes). It then shows one of its main results, namely 2t + 1 is a lower bound for consensus in the anonymous systems equipped with ψ. The second contribution addresses early-decision. The article presents and proves correct an early-deciding algorithm where the processes decide in min(2f + 2, 2t + 1) asynchronous rounds (where f is the actual number of process failures). This leads us to think that anonymity doubles the cost (with respect to synchronous systems) and it is conjectured that min(2f + 2, 2t + 1) is the corresponding lower bound.
The article finally considers the k-set agreement problem in anonymous systems. It first shows that the previous ψ-based consensus algorithm solves the k-set agreement problem in Rt = 2⌊t k⌋ + 1 asynchronous rounds. Then, considering a family of failure detector classes {ψℓ}0 ≤ ℓ < k that generalizes the class ψ(= ψ0), the article presents an algorithm that solves the k-set agreement in Rt,ℓ = 2 ⌊t k − ℓ⌋ + 1 asynchronous rounds. This last formula relates the cost (Rt,ℓ) the coordination degree of the problem (k), the maximum number of failures (t), and the the strength (ℓ) of the underlying failure detector. Finally the article concludes by presenting problems that remain open.
- Aguilera, M. and Toueg, S. 1999. A simple bivalency proof that t-resilient consensus requires t + 1 rounds. Inform. Proc. Lett. 71, 155--178.Google Scholar
Cross Ref
- Angluin, D. 1980. Local and global properties in networks of processes. In Proceedings of the 12th Symposium on Theory of Computing (STOC’80). ACM Press, 82--93. Google ScholarDigital Library
- Aspnes, J. 2002. Wait-free consensus with infinite arrivals. In Proceedings of the 34th Symposium on Theory of Computing (STOC’02). ACM Press, 524--533. Google ScholarDigital Library
- Aspnes, J., Fich, F., and Ruppert, E. 2006. Relationship between broadcast and shared memory in reliable anonymous distributed systems. Distrib. Comput. 18, 3, 209--219. Google ScholarDigital Library
- Attiya, H., Gorbach, A., and Moran, S. 2002. Computing in totally anonymous asynchronous shared memory systems. Inform. Computat. 173, 2, 162--183. Google ScholarDigital Library
- Attiya, H., Snir, M., and Warmuth, M. 1988. Computing on an anonymous ring. J. ACM 35, 4, 845--875. Google ScholarDigital Library
- Attiya, H. and Welch, J. 2004. Distributed Computing, Fundamentals, Simulation and Advanced Topics 2nd Ed. Series on Parallel and Distributed Computing, Wiley. Google ScholarDigital Library
- Borowsky, E. and Gafni, E. 1993. Generalized FLP impossibility results for t-resilient asynchronous computations. In Proceedings of the 25th ACM Symposium on Theory of Computation (STOC’93). 91--100. Google ScholarDigital Library
- Buhrman, H., Panconesi, A., Silvestri, R., and Vityani, P. 2006. On the importance of having an identity or is consensus really universal? Distrib. Comput. 18, 3, 167--175. Google ScholarDigital Library
- Chandra, T. and Toueg, S. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2, 225--267. Google ScholarDigital Library
- Chandra, T., Hadzilacos, V., and Toueg, S. 1996. The weakest failure detector for solving consensus. J. ACM 43, 4, 685--722. Google ScholarDigital Library
- Chaudhuri, S. 1993. More choices allow more faults: Set consensus problems in totally asynchronous systems. Inform. Computat. 105, 132--158. Google ScholarDigital Library
- Chaudhuri, S., Herlihy, M., Lynch, N., and Tuttle, M. 2000. Tight bounds for k-set agreement. J. ACM 47, 5, 912--943. Google ScholarDigital Library
- Chothia, T. and Chatzikokolakis, K. 2005. A survey of anonymous peer-to-peer file-sharing. In Proceedings of the Satellite Workshop of the International Conference on Embedded and Ubiquitous Systems (EUS’05). 744--755. Google ScholarDigital Library
- Delporte-Gallet, C., Fauconnier, H., and Guerraoui, R. 2002. A realistic look at failure detectors. In Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN’02). 345--352. Google ScholarDigital Library
- Delporte-Gallet, C., Fauconnier, H., Helary, J.-M., and Raynal, M. 2003. Early stopping in global data computation. IEEE Trans. Parall. Distrib. Syst. 14, 9, 909--921. Google ScholarDigital Library
- Dolev, D., Reischuk, R., and Strong, R. 1990. Early stopping in byzantine agreement. J. ACM 37, 4, 720--741. Google ScholarDigital Library
- Durresi, A., Paruchuri, V., Durresi, M., and Barolli, L. 2005. A hierarchical anonymous communication protocol for sensor networks. In Proceedings of the Satellite Workshop of the International Conference on Embedded and Ubiquitous Systems (EUS’05). 1123--1132. Google ScholarDigital Library
- Dwork, C. and Moses, Y. 1990. Knowledge and common knowledge in a Byzantine environment: Crash failures. Inform. Computat. 88, 2, 156--186. Google ScholarDigital Library
- Elrad, T. and Francez, N. 1982. Decomposition of distributed programs into communication-closed layers. Sci. Comput. Program. 2, 3, 155--173.Google ScholarCross Ref
- Fischer, M. and Lynch, N. 1982. A lower bound on the time to assure interactive consistency. Inform. Proc. Lett. 14, 4, 183--186.Google ScholarCross Ref
- Fischer, M., Lynch, N., and Paterson, M. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2, 374--382. Google ScholarDigital Library
- Gafni, E. 1998. Round-by-round fault detectors: Unifying synchrony and asynchrony. In Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC’98). 143--152. Google ScholarDigital Library
- Guerraoui, R. and Raynal, M. 2007. The alpha of indulgent consensus. Comput. J. 50, 1, 53--67. Google ScholarDigital Library
- Guerraoui, R. and Ruppert, E. 2007. Anonymous and fault-tolerant shared memory computing. Distrib. Comput. 20, 3, 165--177.Google ScholarDigital Library
- Halpern, J. and Moses, Y. 1990. Knowledge and common knowledge in a distributed environment. J. ACM 37, 3, 549--587. Google ScholarDigital Library
- Herlihy, M. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13, 1, 124--149. Google ScholarDigital Library
- Helary, J.-M., Hurfin, M., Mostefaoui, A., Raynal, M., and Tronel, F. 2000. Computing global functions in asynchronous distributed systems with perfect failure detectors. IEEE Trans. Parall. Distrib. Syst. 11, 9, 897--909. Google ScholarDigital Library
- Herlihy, M., Luchangco, V., and Moir, M. 2003. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23th International IEEE Conference on Distributed Computing Systems (ICDCS’03). 522--529. Google ScholarDigital Library
- Herlihy, M. and Shavit, N. 1999. The topological structure of asynchronous computability. J. ACM 46, 6, 858--923. Google ScholarDigital Library
- Keidar, I. and Rajsbaum, S. 2003. A simple proof of the uniform consensus synchronous lower bound. Inform. Proc. Lett. 85, 47--52. Google ScholarDigital Library
- Lakshman, T. and Wei, V. 1994. Distributed computing on regular networks with anonymous nodes. IEEE Trans. Comput. 43, 2, 211--218. Google ScholarDigital Library
- Loui, M. and Abu-Amara, H. 1987. Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163--183.Google Scholar
- Lynch, N. 1996. Distributed Algorithms. Morgan Kaufmann Publisher. Google ScholarDigital Library
- Moses, Y. and Raynal, M. 2009. Revisiting simultaneous consensus with crash failures. J. Parall. Distrib. Comput. 69, 4, 400--409. Google ScholarDigital Library
- Moses, Y. and Tuttle, M. 1988. Programming simultaneous actions using common knowledge. Algorithmica 3, 121--169.Google ScholarDigital Library
- Mostefaoui, A. and Raynal, M. 2001. Leader-based consensus. Parall. Process. Lett. 11, 1, 95--107.Google ScholarCross Ref
- Mostefaoui, A., Rajsbaum, S., Raynal, M., and Travers, C. 2008a. The combined power of conditions and information on failures to solve asynchronous set agreement. SIAM J. Comput. 38, 4, 1574--1601. Google ScholarDigital Library
- Mostefaoui, A., Rajsbaum, S., Raynal, M., and Travers, C. 2008b. On the computability power and the robustness of set agreement-oriented failure detector classes. Distrib. Comput. 21, 3, 201--222.Google ScholarDigital Library
- Panconesi, A., Papatriantafilou, M., Tsigas, P., and Vityani, P. 1998. Randomized naming using wait-free shared variables. Distrib. Comput. 11, 3, 113--124. Google ScholarDigital Library
- Raynal, M. 2002. Consensus in synchronous systems: A concise guided tour. In Proceedings of the 9th IEEE Pacific Rim Internatinal Symposium on Dependable Computing (PRDC’02). 221--228. Google ScholarDigital Library
- Saks, M. and Zaharoglou, F. 2000. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput. 29, 5, 1149--1483. Google ScholarDigital Library
- Yamashita, M. and Kameda, T. 1996a. Computing on anonymous networks: Part 1--Characterizing the solvable cases. IEEE Trans. Parall. Distrib. Syst. 7, 1, 69--89. Google ScholarDigital Library
- Yamashita, M. and Kameda, T. 1996b. Computing on anonymous networks: Part 2---Decision and membership problems. IEEE Trans. Parall. Distrib. Syst. 7, 1, 90--96. Google ScholarDigital Library
Index Terms
- The Price of Anonymity: Optimal Consensus Despite Asynchrony, Crash, and Anonymity
Recommendations
Communication-efficient leader election and consensus with limited link synchrony
PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computingWe study the degree of synchrony required to implement the leader election failure detector Ω and to solve consensus in partially synchronous systems. We show that in a system with n processes and up to f process crashes, one can implement Ω and solve ...
Uniform Agreement Despite Process Omission Failures
IPDPS '03: Proceedings of the 17th International Symposium on Parallel and Distributed ProcessingA process fails by omission if it "forgets" to send or receive messages. Considering omission failures is crucial for distributed systems, as such failures model both crash failures and incorrect behavior of process input/output buffers (such as buffer ...
Failure detectors in homonymous distributed systems (with an application to consensus)
This paper is on homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership ("homonymous" means that several processes may have the same identifier). New classes of failure detectors ...
Comments