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.