KEEPING TRACK OF THE LATEST GOSSIP IN A DISTRIBUTED SYSTEM

We tackle a natural problem from distributed computing, involving time -stamps. Let P = {p(1),p(2),...,p(N)} be a set of computing agents or processes which synchronize with each other from time to time and exch ange information about themselves and others. The gossip problem is th e following: Whenever a set P subset of or equal to P meets, the proce sses 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 l ocal. Formally, this means that our algorithm can be implemented as an asynchronous automaton.