Keeping track of the latest gossip: bounded time-stamps suffice

Mukund, Madhavan ; Sohoni, Milind (2005) Keeping track of the latest gossip: bounded time-stamps suffice In: 13th International Conference on Foundations of Software Technology and Theoretical Computer Science, 15-17 Dec 2003, Bombay, India.

Full text not available from this repository.

Official URL:

Related URL:


Consider a distributed system consisting of N independent communicating agents. Periodically, agents synchronize and exchange information, both about each other and about agents they have talked to earlier. As a result, an agent at may receive indirect information about another agent aj which is more recent than the information exchanged in the last direct synchronization between ai and aj. The problem is to ensure that agents always come away from a synchronization with the latest possible information about all other agents. This requires that when ai and aj meet, they should decide which of them has more recent information about any other agent ak . We propose an algorithm to solve this problem which is finite-state and local. Formally, this means our algorithm can be implemented by an asynchronous automaton.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Distributed Algorithms; Synchronous Communication; Bounded Time-stamping; Asynchronous Automata
ID Code:114252
Deposited On:25 May 2018 04:54
Last Modified:25 May 2018 04:54

Repository Staff Only: item control page