Bounded time-stamping in message-passing systems

Mukund, Madhavan ; Narayan Kumar, K. ; Sohoni, Milind (2003) Bounded time-stamping in message-passing systems Theoretical Computer Science, 290 (1). pp. 221-239. ISSN 0304-3975

[img] PDF - Other
5kB

Official URL: https://www.sciencedirect.com/science/article/pii/...

Related URL: http://dx.doi.org/https://www.sciencedirect.com/science/article/pii/S0304397501003292

Abstract

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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Message-Passing Systems; Bounded Time-Stamping; Labeled Partial Orders; Finite-State Systems
ID Code:114151
Deposited On:25 May 2018 04:56
Last Modified:25 May 2018 04:56

Repository Staff Only: item control page