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

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.