SWIM

Scalable Weakly-consistent Infection-style Process Group Membership Protocol      

Overview

SWIM is a generic software module that can be used by a distributed peer-to-peer application to maintain weakly-consistent group membership in a scalable manner. This membership system imposes low overhead on participating processes and the underlying network, and detects and disseminates membership updates quickly to participants.

Our effort is motivated by the apparent unscalability of popular heart-beating-based membership protocols. Heart-beating is reputed to suffer from hot-spot problems, or an unscalable response time to detecting simultaneous process failures, or network message loads that grow quadratically with the group size (with a per-process load that grows linearly with the group size) [2]. 

SWIM -

• imposes constant communication overheads per process in the group;
• detects any process failure in time that
  • on expectation, is invariant with the size of the group,
  • with high probability, varies with the logarithm of the group size,
  • is at most linear in the group size,
  • does not vary with the number of simultaneous failures, as long as a significant number of group members are alive;
• disseminates membership updates (resulting from process joins or drop-outs or failures) in time that grows slowly (logarithmically)  with the group size.

This is achieved through the use of randomized peer-to-peer protocols for failure detection [2] and  epidemic-style dissemination.

Distributed peer-to-peer systems that require membership tracking and failure detection in medium to large-sized process groups (or subgroups) occurring within them can achieve an order of magnitude reduction in membership maintenance overhead by using SWIM as a black box sub-system. 

Project Status

• Prototype implemented and tested on the Galaxy cluster of 60 nodes. Experimental results to appear in DSN 2002 [1].
• Like all others, this research project is constantly in flux. Current work directed at WAN-wide extensions, and software interface.

A Glimpse into The Internals

Process groups have unique identifiers. SWIM allows processes to join and leave the group. Process failures are detected using an efficient periodic randomized peer-to-peer probing protocol [2]. Membership changes such as newly joined, failed and left processes are reported to all alive processes in the group. This is achieved by piggybacking membership change information on the random probes, thus achieving an infection-style (also epidemic- or gossip-style) protocol. The system is weakly consistent as the latency of propagation of membership changes to the group varies with the group size, logarithmically on expectation, and linearly in the worst case.

Several research directions - adaptivity, large-area deployment issues, generic use of the Suspicion mechanism. Interested? Email gupta@cs.cornell.edu 

Publications/Presentations/Related Papers

1. Abhinandan Das, Indranil Gupta, Ashish Motivala, "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol", To appear in The International Conference on Dependable Systems and Networks (DSN 02), Washington DC,  June, 2002. PS PDF PPT
2. Indranil Gupta, Tushar D. Chandra, German Goldszmidt, "On Scalable and Efficient Distributed Failure Detectors", In 20th Symposium on Principles of Distributed Computing (PODC 2001), Newport, RI, August, 2001.  PS  PDF  PPT
3. SOSP 2001 Work-in-Progress PPT (the system was then called Dping).
4. Abhinandan Das and Ashish Motivala, CS 614 project report.

People

• Indranil Gupta
• Abhinandan Das
• Ashish Motivala

Contact

Your feedback is important. If you have comments on any of the papers, or want access to the software, please email gupta@cs.cornell.edu 

Verse

Maintained by: Indranil Gupta gupta@cs.cornell.edu Last revised : 29th July 2002.