Keeping Track of the Latest Gossip in Shared Memory Systems

Bharat Adsul, Aranyak Mehta, Milind Sohoni

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


In this paper we present a solution to the `Latest Gossip Problem' for a shared memory distributed system. The Latest Gossip Problem is essentially one of bounded timestamping in which processes must locally keep track of the `latest' information, direct or indirect, about all other processes. A solution to the Latest Gossip Problem is fundamental to the understanding of information flow in a distributed computation, and has applications to problems such as global state detection or mutual exclusion. Our solution is along the lines of that for message passing systems in \cite{MNS1}, and for synchronously communicating systems \cite{MS1}. Our algorithm uses a modified version of the {\em consume} and {\em update} protocols of Dwork and Waarts \cite{DW}, where these were introduced to construct a `Bounded Concurrent Timestamping System'. As an application of our Gossip Protocol, we also indicate a solution to the BCTS problem. The solution in \cite{DW} requires, in addition to the read-write operations, special `garbage collection' operations to be performed from time to time so that timestamps can be reused. Our specialization eliminates the need for such an operation, and maintains timestamps and latest information `on-line'.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems