Keeping track of the latest gossip in message-passing systems

Mukund, Madhavan ; Narayan Kumar, K. ; Sohoni, Milind (1995) Keeping track of the latest gossip in message-passing systems In: Proceedings of the International Workshop on Structures in Concurrency Theory (STRICT),, 11-13 May 1995, Berlin, Germany.

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Transitive Closure; Primary Graph; Late Information; Primary Information; Message Complexity
ID Code:114228
Deposited On:25 May 2018 04:54
Last Modified:25 May 2018 04:54

Repository Staff Only: item control page