The obscure nature of epidemic quorum systems

ABSTRACT

Epidemic quorum systems enable highly available agreement even when a quorum is not simultaneously connected, and are therefore very interesting for mobile networks. Although recent work has proposed epidemic quorum algorithms, their properties and trade-offs are not well studied. This paper sheds some light on less known aspects of epidemic quorum systems. With simple counter-examples and combinatorial exercises, we contradict common misbeliefs that are often associated with epidemic quorum systems. Our claims advocate the need for a deeper study of these promising systems.

REFERENCES

• 1: Y. Amir , A. Wool, Evaluating quorum systems over the Internet, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.26, June 25-27, 1996
• 2: J. Barreto and P. Ferreira. The availability and performance of epidemic quorum algorithms. Technical Report 10/2007, INESC-ID, February 2007.
• 3: Ing-Ray Chen , Ding-Chau Wang, Analyzing dynamic voting using Petri nets, Proceedings of the 15th Symposium on Reliable Distributed Systems (SRDS '96), p.44, October 23-25, 1996
• 4: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 5: JoAnne Holliday , Robert Steinke , Divyakant Agrawal , Amr El Abbadi, Epidemic Algorithms for Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1218-1238, September 2003 [doi>10.1109/TKDE.2003.1232274]
• 6: Availability Study of Dynamic Voting Algorithms, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.247, April 16-19, 2001
• 7: S. Jajodia , David Mutchler, Dynamic voting algorithms for maintaining the consistency of a replicated database, ACM Transactions on Database Systems (TODS), v.15 n.2, p.230-280, June 1990 [doi>10.1145/78922.78926]
• 8: F. P. Junqueira and K. Marzullo. Coterie availability in sites. In P. Fraigniaud, editor, 19th International Symposium on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science, pages 3--17. Springer, 2005.
• 9: Peter J. Keleher, Decentralized replicated-object protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301345]
• 10: Eliezer Levy , Abraham Silberschatz, Distributed file systems: concepts and examples, ACM Computing Surveys (CSUR), v.22 n.4, p.321-374, Dec. 1990 [doi>10.1145/98163.98169]
• 11: David Peleg , Avishai Wool, The availability of quorum systems, Information and Computation, v.123 n.2, p.210-223, Dec. 1995 [doi>10.1006/inco.1995.1169]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

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

General Terms:
Algorithms