M Mukund and M Sohoni
Proc. FSTTCS 13, Springer LNCS 761 (1993) 388-399.
© Springer-Verlag Berlin Heidelberg
Consider a distributed system consisting of N independent communicating agents. Periodically, agents synchronize and exchange information, both about each other and about agents they have talked to earlier. As a result, an agent a_i may receive indirect information about another agent a_j which is more recent than the information exchanged In the last direct synchronization between a_i and a_j. The problem is to ensure that agents always come away from a synchronization with the latest possible information about all other agents. This requires that when a_i and a_j meet, they should decide which of them has more recent information about any other agent a_k. We propose an algorithm to solve this problem which is finite-state and local. Formally, this means our algorithm can be implemented by an asynchronous automaton.