SWIM Protocol


The Scalable Weakly Consistent Infection-style Process Group Membership Protocol is a group membership protocol based on "outsourced heartbeats" used in distributed systems, first introduced by Abhinandan Das, Indranil Gupta and Ashish Motivala in 2002. It is a hybrid algorithm which combines failure detection with group membership dissemination.

Protocol

The protocol has two components, the Failure Detector Component and the Dissemination Component.
The Failure Detector Component functions as follows:
  1. Every T time units, each node sends a ping to random other node in its membership list.
  2. If receives a response from, is decided to be healthy and updates its "last heard from" timestamp for to be the current time.
  3. If does not receive a response, contacts k'' other nodes on its list, and requests that they ping.
  4. If after T units of time: if no successful response is received, marks as failed.
The Dissemination Component'' functions as follows:
  • Upon detecting a failed node, sends a multicast message to the rest of the nodes in its membership list, with information about the failed node.
  • Voluntary requests for a node to enter/leave the group are also sent via multicast.

    Properties

The protocol provides the following guarantees:
The original SWIM paper lists the following extensions to make the protocol more robust:
  • Suspicion: Nodes that are unresponsive to ping messages are not initially marked as failed. Instead, they are marked as "suspicious"; nodes which discover a "suspicious" node still send a multicast to all other nodes including this mechanism. If a "suspicious" node responds to a ping before some time-out threshold, an "alive" message is sent via multicast to remove the "suspicious" label from the node.
  • Infection-Style Dissemination: Instead of propagating node failure information via multicast, protocol messages are piggybacked on the ping messages used to determine node liveness. This is equivalent to gossip dissemination.
  • Round-Robin Probe Target Selection: Instead of randomly picking a node to probe during each protocol time step, the protocol is modified so that each node performs a round-robin selection of probe target. This bounds the worst-case detection time of the protocol, without degrading the average detection time.