Moshe: A Group Membership Service for WANs.

Authors: Idit Keidar, Jeremy Sussman, Keith Marzullo, and Danny Dolev.

To appear in ACM Transactions on Computer Systems (TOCS), August 2002.

Previous version: Technical Memorandum MIT-LCS-TM-593a Massachusetts Institute of Technology, Laboratory for Computer Science; also Technical Report CS99-623a University of California, San Diego, Department of Computer Science and Engineering, June 1999, revised September 2000.

Preliminary version appeared in the 20th International Conference on Distributed Computing Systems (ICDCS), pages 356-365, April 2000.

Abstract:

We present Moshe, a novel scalable group membership algorithm built specifically for use in wide area networks (WANs), which can suffer partitions. Moshe is designed with three new significant features that are important in this setting: it avoids delivering views that reflect out-of-date memberships; it requires a single round of messages in the common case; and it employs a client-server design for scalability. Furthermore, Moshe's interface supplies the hooks needed to provide clients with full virtual synchrony semantics. We have implemented Moshe on top of a network event mechanism also designed specifically for use in a WAN.

In addition to specifying the properties of the algorithm and proving that this specification is met, we provide empirical results of an implementation of Moshe running over the Internet. The empirical results justify the assumptions made by our design and exhibit good performance. In particular, Moshe terminates within a single communication round over 98% of the time. The experimental results also lead to interesting observations regarding the performance of membership algorithms over the Internet.

Download

Preprint of ACM TOCS paper (March 2002): ps, pdf, ps.gz.
Revised technical report (September 2000): ps, pdf, ps.gz.
ICDCS 2000 paper: ps, pdf, ps.gz.
Talk slides (powerpoint): ppt, ppt.gz.

Last modified: Mon Jul 1 14:34:43 EDT 2002