M Mukund, K Narayan Kumar and M Sohoni

*Theoretical Computer Science*, 290(1), (2003), 221-239.

Consider a distributed system running a protocol in which
processes exchange information by passing messages. The
*gossip problem* for the protocol is the following:
Whenever a process *q* receives a message from another
process *p*, *q* must be able to decide which
of *p* and *q* has more recent information
about *r*, for every other process *r* in the
system. With this data, *q* is in a position to
update its knowledge about the global state of the system.

We propose a solution wherein to each message of the
protocol, the sender adds information about its current state
of knowledge about other processes. We do not add any
*new* messages to the underlying computation. The
additional information tagged onto each message is
*uniformly* bounded if the channels are bounded. This
means that for systems with bounded channels, the overhead of
maintaining the latest gossip is a constant, independent of
the length of the underlying computation. Moreover, gossip
information can be used to implement bounded channels by
inhibiting the sending of new messages over channels that are
potentially full.

Our solution to the gossip problem has several applications in the analysis of distributed systems. Many distributed algorithms rely, either explicitly or implicitly, on the local information available at a process about the global state of the system. Using our scheme, each process can ensure that during a computation it always maintains the best possible information about every other process. At a theoretical level, the gossip problem plays an important role in formal characterizations of finite-state message-passing systems.