Jump to content

SWIM Protocol

From Wikipedia, the free encyclopedia
SWIM "Outsourced Heartbeats"

The Scalable Weakly Consistent Infection-style Process Group Membership (SWIM) Protocol is a group membership protocol based on "outsourced heartbeats"[1] used in distributed systems, first introduced by Indranil Gupta in 2001.[2][3] It is a hybrid algorithm which combines failure detection with group membership dissemination.

Protocol

[edit]

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 N1 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

[edit]

The protocol provides the following guarantees:

  • Strong Completeness: Full completeness is guaranteed (e.g. the crash-failure of any node in the group is eventually detected by all live nodes).
  • Detection Time: The expected value of detection time (from node failure to detection) is , where is the length of the protocol period, and is the fraction of non-faulty nodes in the group.[3]

Extensions

[edit]

The original SWIM paper lists the following extensions to make the protocol more robust:[2]

  • 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.

See also

[edit]

References

[edit]
  1. ^ Petrov, Alex (2019). Database Internals. O'Reilly Media.
  2. ^ a b Gupta, Indranil; Chandra, Tushar D.; Goldszmidt, Germán S. (August 1, 2001). "On scalable and efficient distributed failure detectors". Proceedings of the twentieth annual ACM symposium on Principles of distributed computing. PODC '01. Newport, Rhode Island, US: Association for Computing Machinery. pp. 170–179. doi:10.1145/383962.384010. ISBN 978-1-58113-383-7. S2CID 216594.
  3. ^ a b Das, A.; Gupta, I.; Motivala, A. (June 23, 2002). "SWIM: Scalable weakly-consistent infection-style process group membership protocol". Proceedings International Conference on Dependable Systems and Networks. pp. 303–312. doi:10.1109/DSN.2002.1028914. ISBN 0-7695-1597-5. S2CID 11094028.