Maintaining Latest Information beyond Channel Bounds

Consider distributed systems consisting of a number of processes communicating with each other asynchronously by sending messages via FIFO channels. It is crucial for such systems that every process can maintain deterministically the latest information about other processes. To do so, any process $p$, upon receiving a message from a process $q$, should determine for every process $r$, whether the latest event on $r$ that $p$ knows of is more recent than the latest event on $r$ that $q$ knows of. Solving this problem, while storing and exchanging only a bounded amount of information, is extremely challenging and not always possible. This is known as the gossip problem. A solution to this is the key to solving numerous important problems on distributed systems. So far, gossip has been solved only for channel bounded systems. We solve the gossip problem for a much richer class, going beyond a priori channel bounds. Joint work with Paul Gastin (LSV, ENS Cachan, France) and K. Narayan Kumar (Chennai Mathematical Institute, India).

Authors

• C. Aiswarya

Keywords

No keywords are indexed for this paper.