Brief announcement: the price of anonymity: optimal consensus despite asynchrony, crash and anonymity

ABSTRACT

This paper proposes the first study of the consensus problem in the anonymous crash-prone message-passing systems.

REFERENCES

• 1: Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
• 2: Dana Angluin , James Aspnes , Zoë Diamadi , Michael J. Fischer , René Peralta, Computation in networks of passively mobile finite-state sensors, Distributed Computing, v.18 n.4, p.235-253, March 2006 [doi>10.1007/s00446-005-0138-3]
• 3: Hagit Attiya , Alla Gorbach , Shlomo Moran, Computing in totally anonymous asynchronous shared memory systems, Information and Computation, v.173 n.2, p.162-183, March 15, 2002 [doi>10.1006/inco.2001.3119]
• 4: Hagit Attiya , Marc Snir , Manfred K. Warmuth, Computing on an anonymous ring, Journal of the ACM (JACM), v.35 n.4, p.845-875, Oct. 1988 [doi>10.1145/48014.48247]
• 5: Bonnet F. and Raynal M., The Price of Anonymity: Optimal Consensus despite Asynchrony, Crash and Anonymity. Tech Report, #1918, IRISA, Université de Rennes (France),December 2008.
• 6: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 7: Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
• 8: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 9: Guerraoui R. and Ruppert E., Anonymous and Fault-tolerant Shared Memory Computing. Distributed Computing, 20(3):165--177, 2007.
• 10: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 11: Loui M.C., Abu-Amara H., Memory Requirements for Agreement Among Unreliable Asynchronous Processes. Advances in Computing research, JAI Press, 4:163--183, 1987.
• 12: Mostefaoui A., Rajsbaum S., Raynal M. and Travers C., On the Computability Power and the Robustness of Set Agreement-oriented Failure Detector Classes. Distributed Computing, 21(3):201--222, 2008.
• 13: Mostefaoui A., Rajsbaum S., Raynal M. and Travers C., The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. SIAM Journal of Computing, 38(4):1974--1601, 2008.
• 14: Masafumi Yamashita , Tsunehiko Kameda, Computing on Anonymous Networks: Part II-Decision and Membership Problems, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.90-96, January 1996 [doi>10.1109/71.481600]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Algorithms, Theory

Keywords:
anonymous systems, distributed agreement