Record Details

Bounded time-stamping in message-passing systems

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Bounded time-stamping in message-passing systems
 
Creator MUKUND, MADHAVAN
NARAYAN KUMARA, K
SOHONI, MILIND
 
Subject message passing
bounded time stamping
labeled partial orders
finite-state systems
 
Description 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.
 
Publisher Elsevier
 
Date 2009-09-26T07:14:15Z
2011-11-25T15:47:43Z
2011-12-26T13:05:07Z
2011-12-27T05:51:12Z
2009-09-26T07:14:15Z
2011-11-25T15:47:43Z
2011-12-26T13:05:07Z
2011-12-27T05:51:12Z
2003
 
Type Article
 
Identifier Theoretical Computer Science 290(1), 221-239
0304-3975
http://dx.doi.org/10.1016/S0304-3975(01)00329-2
http://hdl.handle.net/10054/1674
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1674
 
Language en