M Mukund, K Narayan Kumar and M Sohoni

*Proc. STRICT '95*, Workshops in Computing, Springer-Verlag
(1995) 249-263.

Consider a distributed system in which processes exchange
information by passing messages. The *gossip problem*
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 where each message between
processes carries information about the current state of
knowledge of the sender. This information is
*uniformly* bounded if we make reasonable assumptions
about the number of undelivered messages present at any time
in the system. This means that the overhead of maintaining
the latest gossip is a constant, independent of the length of
the underlying computation.