Group membership: a novel approach and the first single-round algorithm

ABSTRACT

We establish a new worst-case upper bound on the Membership problem: We present a simple algorithm that is able to always achieve Agreement on Views within a single message latency after the final network events leading to stability of the group become known to the membership servers. In contrast, all of the existing membership algorithms may require two or more rounds of message exchanges. Our algorithm demonstrates that the Membership problem can be solved simpler and more efficiently than previously believed.By itself, the algorithm may produce disagreement (that is, inconsistent, transient views) prior to the "final" view. Even though this is allowed by the problem specification, such views may create overhead at the application level, and are therefore undesirable.We propose a new approach for designing group membership services in which our algorithm for reaching Agreement on Views is combined with a filter-like mechanism for reducing disagreements. This approach can use the mechanisms of existing algorithms, yielding the same multi-round performance as theirs.However, the power of this approach is in being able to use other mechanisms. These can be tailored to the specifics of the deployment environments and to the desired combinations of the speed of agreement vs. the amount of preceding disagreement. We describe one mechanism that keeps the combined performance to within a single-round, and sketch another two.

REFERENCES

• 1: ACM. Communications of the ACM 39(4), special issue on Group Communications Systems, April 1996.
• 2: Y. Amir. Replication Using Group Communication Over a Partitioned Network. PhD thesis, Inst. of Comp. Science, Hebrew Univ., Jerusalem, Israel, 1995.
• 3: Y. Amir, D. Dolev, S. Kramer, and D. Malki. Transis: A communication sub-system for high availability. In 22nd IEEE Fault-Tolerant Computing Symposium (FTCS), July 1992.
• 4: Y. Amir , L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , P. Ciarfella, The Totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems (TOCS), v.13 n.4, p.311-342, Nov. 1995 [doi>10.1145/210223.210224]
• 5: Kenneth P. Birman, Building Secure and Reliable Network Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1996
• 6: K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.123-138, November 08-11, 1987, Austin, Texas, United States
• 7: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 8: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg , Bernadette Charron-Bost, On the impossibility of group membership, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.322-330, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248120]
• 9: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 10: Specifying and using a partitionable group communication service, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.171-216, May 2001 [doi>10.1145/377769.377776]
• 11: Idit Keidar , Danny Dolev, Efficient message ordering in dynamic networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.68-76, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248062]
• 12: Idit Keidar , Sergio Rajsbaum, A simple proof of the uniform consensus synchronous lower bound, Information Processing Letters, v.85 n.1, p.47-52, 16 January 2003 [doi>10.1016/S0020-0190(02)00333-2]
• 13: Idit Keidar , Jeremy Sussman , Keith Marzullo , Danny Dolev, Moshe: A group membership service for WANs, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.191-238, August 2002 [doi>10.1145/566340.566341]
• 14: Roger I. Khazan , Alan Fekete , Nancy A. Lynch, Multicast Group Communication as a Base for a Load-Balancing Replicated Data Service, Proceedings of the 12th International Symposium on Distributed Computing, p.258-272, September 24-26, 1998
• 15: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 16: Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996 [doi>10.1145/227210.227229]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Performance, Theory

Keywords:
consensus, group communication, group membership