Table of Contents


This week’s video lectures cover the topics of Grids, Membership, and Gossip. With this, you have all the concepts you need to complete the Programming Assignment in this course.

Goals and Objectives

After you actively engage in the learning experiences in this module, you should be able to:

  • Analyze various gossip/epidemic protocols.
  • Design and analyze various distributed membership protocols.
  • Know what grid computing is.

Key Phrases/Concepts

Keep your eyes open for the following key terms or phrases as you interact with the lectures. These topics will help you better understand the content in this module.

  • Failure detectors
  • Membership protocols
  • Gossip/epidemic protocols
  • Grid computing

Guiding Questions

Develop your answers to the following guiding questions while completing the activities throughout the week.

  • Why are gossip and epidemic protocols fast and reliable?
  • What is the most efficient way for cloud computing systems to detect failures of servers?
  • How is grid computing related to cloud computing?


what is multicast?

Suppose you have a group of processes or a group of nodes. Each of these processes or each of these nodes is potentially a process at some host on the Internet or connected to the network. And essentially, all we need is that these processes or nodes need to be able to talk with each other by being able to send and receive messages.

What are the requirements for multicast protocol?

  • fault tolerance
  • scalability

Centralized Multicast Protocol

  • If the sender fails, no one can received the multicast.
  • the overhead on the sender is very high. O(n)

Tree-Based Multicast Protocol

  • Build a spanning tree among the processes of the multicast group
  • Use spanning tree to disseminate multicasts
  • Use either acknowledgments (ACKs) or negative acknowledgements (NAKs) to repair multicasts not received
  • SRM (Scalable Reliable Multicast)
    • Uses NAKs
    • But adds random delays, and uses exponential backoff to avoid NAK storms
  • RMTP (Reliable Multicast Transport Protocol)
    • Uses ACKs
    • But ACKs only sent to designated receivers, which then re-transmit missing multicasts
  • These protocols still cause an O(N) ACK/NAK overhead
  • gossip_member_grid01.png

Epidemic Multicast

the sender periodically picks b nodes as gossip targets and sends them copies of the multicast message using what is known as a gossip message. When b turns from uninfected into infected they starts periodically sending out gossip message.

  • Push gossip
    • Once you have a multicast message, you start gossiping about it
    • Multiple messages? Gossip a random subset of them, or recently-received ones, or higher priority ones
  • Pull gossip
    • Periodically poll a few randomly selected processes for new multicast messages that you haven’t received
    • Get those messages
  • Hybrid variant: Push-Pull
    • As the name suggests

Topology-Aware Gossip

  • Network topology is hierachical
  • Random gossip target selection => core routers face O(N) load
  • In subnet i, which contains $n_i$ nodes, pick gossip target in your subnet with probability $\frac{1}{n_i}$
  • Router $load=O(1)$
  • Dissemination $time=O(log(N))$

Gossip Summary

  • Multicast is an important problem
  • Tree-bases multicast protocols
  • When concerns the scalability and fault tolerance, the gossip protocol is a good choice
  • Also known as epidemic
  • Fast, reliable, Fault-tolerant, scalability, topology-aware


The membership list Which maintains the list of most or all of the other processes that are currently in your system and that have not yet failed. That means non-faulty processes. This membership list is accessed by a variety of applications, for instance the application might be a distributed hash table.

Two sub-protocals

  • Failure Detection
  • Dissemination

Failure Detection

some process find out the failure process quickly

  • Desirable propertities
    • Completeness (most important)
    • Accuracy
    • Speed
    • Scale

Gossip Style Failure Detection

  1. If the heartbeat has not increased for more than $T_{tail}$ seconds, the member is considered fail.
  2. After $T_{cleanup}$ seconds, it will delete the member from the list.
  3. N heartbeats take:
    • O(log(n)) time to propagate if bandwith allowed per node is O(n)
    • O(Nlog(n)) time to propagate if bandwith allowed per node is O(1)
  4. Multi-level Gossip
  5. All-to-all and gossip-based heartbeating are in fact suboptimal because they have in fact they are O(Nlog(N)) for the gossip-based heartbeating. The key here is to realize that these two protocols mix up the failure detection and the dissemination components. Essentially they are trying to have all the processes in the system detect the failure by themselves and not really using dissemination component separately.

Swim Failure Detection

  • Two choice for the $P_j$(failure process)
  • Directed ping to $P_j$ and indirected ping to $P_j$ (Randomly select another process and then send ping to $P_j$)
  • Constant time => $O(1)$


  • Multicast Dissemination(Hardware/IP)
    • unreliable
  • Point-to-Point
    • expensive
  • Infection style Dissemination

Suspicion Mechanism

Suspect a process before declaring it as failed in the group

Member Summary

  • 在数据中心中,出错是常态,并不是意外
  • 每一个分布式系统都会使用错误检测器
  • 很多分布式系统使用了成员关系服务
  • 使用环形错误检测的有
    – IBM SP2和很多其他相似的集群/机器
  • 使用流言式的错误检测的有
    – 亚马逊Amazon EC2/S3


src: https://www.zhihu.com/question/20773707/answer/16583447


two level scheduling infrastructure

  • Inter-site protol
  • Globus
  • No single entity controls the entire infrastructure(federate)


Reference from some slides from Coursera course Cloud Computing