Keeping Track of the Latest Gossip in a Distributed System

M Mukund and M Sohoni

Distributed Computing, 10, 3, (1997) 137-148.

We tackle a natural problem from distributed computing, involving time-stamps. Let Proc = {p1,p2,...,pN} be a set of computing agents or processes which synchronize with each other from time to time and exchange information about themselves and others. The gossip problem is the following: Whenever a subset P of processes from Proc meets, the processes in P must decide amongst themselves which of them has the latest information, direct or indirect, about each agent p in the system. We propose an algorithm to solve this problem which is finite-state and local. Formally, this means that our algorithm can be implemented as an asynchronous automaton.

• Keeping Track of the Latest Gossip: Bounded Time-Stamps Suffice
  M Mukund and M Sohoni
  Proc. FSTTCS 13, Springer LNCS 761 (1993) 388-399.

• Gossiping, Asynchronous Automata and Zielonka's Theorem
  M Mukund and M Sohoni
  Report TCS-94-2, School of Mathematics, SPIC Science Foundation, Madras, India (1994)