M Mukund and M Sohoni

*Report TCS-94-2*,
School of Mathematics, SPIC Science Foundation, Madras,
India (1994)

In this paper, we first tackle a natural problem from distributed computing, involving time-stamps. We then show that our solution to this problem can be applied to provide a simplified proof of Zielonka's theorem---a fundamental result in the theory of concurrent systems.

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.

Solving the gossip problem appears to be a basic step in
tackling other problems involving asynchronous automata.
Here, we apply our solution to derive an alternative proof of
Zielonka's fundamental result that deterministic asynchronous
automata accept precisely the class of recognizable trace
languages. For a given recognizable trace language
*L* over a concurrent alphabet *(Sigma,I)*, we
show how to construct a deterministic asynchronous automaton
with the same underlying independence structure which accepts
*L*.

Zielonka's original proof of this theorem is quite intricate and hard to grasp. To the best of our knowledge, ours is the first simplified proof of this result which works directly with asynchronous automata.