Dynamic Voting for Consistent Primary Components.

Authors: Esti Yeger Lotem, Idit Keidar and Danny Dolev.

In the Sixteenth ACM Symposium on Principles of Distributed Computing (PODC '97), pages 63-71, Santa Barbara, CA, USA, August 21-24, 1997.

Abstract:

Distributed applications often use quorums in order to guarantee consistency. With emerging world-wide communication technology, many new applications (e.g., conferencing applications and interactive games) wish to allow users to freely join and leave, without restarting the entire system. The dynamic voting paradigm allows such systems to define quorums adaptively, accounting for the changes in the set of participants. Furthermore, dynamic voting was proven to be the most available paradigm for maintaining quorums in unreliable networks. However, the subtleties of implementing dynamic voting were not well understood; in fact, many of the suggested protocols may lead to inconsistencies in case of failures. Other protocols severely limit the availability in case failures occur during the protocol. In this paper we present a robust and efficient dynamic voting protocol for unreliable asynchronous networks. The protocol consistently maintains the primary component in a distributed system. Our protocol allows the system to make progress in cases of repetitive failures in which previously suggested protocols block. The protocol is simple to implement, and its communication requirements are small.

Postscript Version: ps, ps.gz. Israel mirror site: ps.gz.



Full version available as Technical Report CS96-7, Institute of Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel, June 1996: ps, ps.gz, Israel mirror site: ps.gz. ps.gz, abstract.


Last modified: Mon Jul 1 14:35:23 EDT 2002