Group Communication, Atomic broadcast, Gossip Protocols Part 2 (A)


May 29, 2012


Robbert van Renesse


Cornell University


Communication primitives are an important consideration when developing distributed algorithms and systems. The logical and performance properties that they provide are assumptions used in the development of distributed systems. Moreover, many communication primitives are provided by subsystems that are themselves distributed algorithms built over lower-level communication primitives. Guided by invariant properties, we will look at three such communication subsystems.

Group Communication systems track both process membership and communication between the members within abstractions called groups. Each group is dynamic: processes can join, voluntarily leave, or involuntarily crash. We will look at properties that such groups provide and how one can quickly develop some basic replicated services and notification services using the group abstractions.

Atomic Broadcast is the workhorse of the state machine replication approach. Messages sent to the same group of replicas are delivered in the same order at each replica. We will look at protocols for doing so in the fail-stop model in which failures can be detected accurately, leaving the more general case of crash and Byzantine tolerant protocols for the Consensus lectures presented later in the Summer School.

While Group Communication and Atomic Broadcast provide strong consistency properties, Gossip Protocols focus on probabilistic liveness properties. We will look at two classes of gossip: rumor mongering and anti-entropy. Rumor mongering is useful for event dissemination, while anti-entropy is useful for eventual consistency—a popular notion of consistency in cloud computing. Even with such probabilistic protocols, we will see that it makes sense to reason using invariants.


Robbert van Renesse

I am a Principal Research Scientist in the Department of Computer Science at Cornell University in Ithaca, NY. I’m a member of the Systems and Networking group. I’m interested in distributed systems, particularly in their fault tolerance and scalability aspects. I’m an elected member on the Steering Committee of NSF PRObE (Parallel Reconfigurable Observational Environment). I also play guitar and do sound for the Ageless Jazz Band, play Dixieland banjo in The JazzHappensBand, am co-founder of and advisor to The Cornell Dutch Club, and co-founder of The Finger Lakes One Wheelers, a unicycling club. I’m the webmaster of The Ithaca High School PSTA web site. I’m also the designer and webmaster of, a site that helps with the management side of playing in bands.