Compositional Gossip Systems

Gossip protocols have a wide range of applications in distributed systems. They offer robust fault tolerance in exchange for probabilistic guarantees and convergence, and are characterized by elegance and simplicity. This body of research considers the problem of gossip protocol representation and composition; that is, how to use simple gossip protocols as building blocks to form more complex and powerful compound protocols. In doing so, we propose a novel formal representation of gossip, and use it to define the essential properties of gossip systems. We propose composition operators that combine protocols, and show how properties of operands protocols are (or are not) transferred to the resulting compound protocols. Choice among composition operators leads to trade-offs of performance and independence, while preserving semantics. The optimization afforded by what we call "correlated merge" operator enables constructions that would be quite difficult to implement on their own by opportunistically combining gossip messages from many constituent protocols. We discuss which practical syntactic features are helpful for gossip system implementation. A proof-of-concept implementation named MiCA is presented, consisting of Java-language runtime for gossip, a library of gossip primitives, a simulator for rapid development, and visualization and analysis tools that can be used to interpret the results of experiments