Internal Report  TCS-94-2

February, 1994

Gossiping, Asynchronous Automata and Zielonka’s Theorem

Madhavan Mukund and Milind Sohoni

School of Mathematics SPIC Science Foundation 92 G.N. Chetty Road, T. Nagar Madras 600 017, INDIA

        E-mail: {madhavan,sohoni}@ssf.ernet.in

Abstract

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 𝒫 = {p_{1}, p_{2}, …, p_{N}} 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 set P ⊆ 𝒫 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 (Σ, 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.

Introduction

This paper has two main aims. 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 a fundamental result in the theory of concurrent systems—Zielonka’s theorem that asynchronous automata accept precisely the class of recognizable trace languages [Zie1].

Let 𝒫 = {p_{1}, p_{2}, …, p_{N}} 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 set P ⊆ 𝒫 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.

This is easily accomplished if the agents decide to “time-stamp” every synchronization and pass these time-stamps along with each exchange of information. This does not require that all their clocks be synchronized. For example, each process can use an independent counter. When a set P ⊆ 𝒫 meets, the processes in P jointly agree on a new value for their counters which exceeds the maximum of the counter values currently held by them. Thus, for any process p, the time-stamps assigned to synchronization events involving p form a strictly increasing sequence (albeit with gaps between successive timestamps). So, the problem of deciding who has the latest information about p reduces to that of checking for the largest time-stamp.

This scheme has the following drawback: As the computation progresses these counter values increase without bound and most of the agents’ time would be taken up in passing on large numbers, as opposed to actual gossip.

We propose an algorithm using counters which take on values from a bounded, finite set. We assign an independent counter to each subset of processes which can potentially synchronize. These counters are updated when the corresponding sets of processes meet. The update is performed jointly by the processes which meet.

Since our set of counter values is bounded, time-stamps have to be reused and, in general, different synchronizations involving a particular set of processes will acquire the same time-stamp during a computation. Despite this, our algorithm guarantees that whenever a set P ⊆ 𝒫 meets, the processes in P can decide correctly which of them has the best information about any other agent p in the system. Thus, in essence, the processes in 𝒫 may be finite state machines and yet manage to keep track of the latest information about other agents. Further, the algorithm itself does not induce any additional communications.^{1}

We formalize the gossip problem and our solution to it in terms of asynchronous automata. These machines were first introduced by Zielonka and are a natural generalization of finite-state automata for modelling concurrent systems [Zie1]. An asynchronous automaton consists of a set of finite-state agents which synchronize to process their input. Each letter a in the input alphabet Σ is assigned a subset θ(a) of processes which jointly update their state when reading a. The processes outside θ(a) remain unchanged during this move—in fact, they are oblivious to the occurrence of a.

A distributed alphabet (Σ, θ) of this type gives rise to an independence relation I between letters: (a, b) ∈ I iff a and b are processed by disjoint sets of components—i.e., θ(a) ∩ θ(b) = ∅.

1An earlier proof of this result appeared in [MS]. However, the proof we provide here is new, more concise and more uniform with respect to different underlying patterns of synchronization.

An alphabet with an independence relation is also called a concurrent alphabet. These were introduced in the theory of concurrent systems by Mazurkiewicz as a technique for studying such systems from the viewpoint of formal language theory [Maz]. Given a concurrent alphabet (Σ, I), I induces a natural equivalence relation ∼ on Σ^{∗}: two words u and u′ are related by ∼ iff u′ can be obtained from u by a sequence of permutations of adjacent independent letters. The equivalence class [w] containing w is called a trace. Thus, the trace [w] describes all possible ways of interleaving independent actions in w without affecting the overall computation.

A language L ⊆ Σ^{∗} is said to be a trace language over (Σ, I) if L is closed under ∼. In other words, for each w ∈ Σ^{∗}, if w ∈ L then [w] ⊆ L. A trace language is recognizable if it is accepted by a conventional finite-state automaton over Σ.

However, since conventional automata are sequential, it is quite awkward to precisely characterize the class of automata which recognize trace languages. Asynchronous automata, on the other hand, are natural acceptors for these languages. If we distribute Σ in such a way that the induced independence relation is I, we are guaranteed that the set of strings accepted by the automaton is recognizable and closed under ∼.

Despite this obvious connection, it is not easy to prove that the class of languages accepted by asynchronous automata coincides with the class of recognizable trace languages. This fundamental result was first established by Zielonka [Zie1]. Given a conventional finite automaton recognizing a trace language over (Σ, I), he demonstrated how to construct directly a deterministic asynchronous automaton over a distributed alphabet (Σ, θ) which accepts the same language, such that the independence relation induced by θ is precisely I.

Zielonka’s original proof of this theorem is quite intricate and difficult to grasp. It turns out that our algorithm for keeping track of the latest information can be exploited to provide a simple, “operational” proof of this theorem. The states of the automaton we construct are highly structured. As a result, the transition function which updates the information in the states can be described in an “algorithmic” manner. This is in contrast to the automaton yielded by Zielonka’s construction, where the set of states is just an enormous collection of names and the transition relations are specified by exhaustively listing out all the entries in the transition table. So, though both constructions yield state spaces of the same order of magnitude, the automaton we construct can be effectively presented much more concisely than the one Zielonka constructs.

Our proof is not the first attempt to simplify Zielonka’s argument. Given that the statement of his theorem is at once both fundamental and elegant, both he and others have worked on alternative, more accessible proofs [CMZ, Die]. However, all of these new proofs have been based on a different machine model called asynchronous cellular automata. The drawback is that, unlike asynchronous automata, these new machines are not easy to visualize and do not correspond to any natural framework of distributed computation. We shall discuss the connections between our construction and these proofs based on asynchronous cellular automata in greater detail in the concluding section of the paper, where it will be easier to point out the similarities and differences between the two approaches. For the moment, we just note that the construction we give here is, to the best of our knowledge, the first simplified proof of Zielonka’s theorem based directly on asynchronous automata.

The paper is organized as follows. In the next section, we introduce asynchronous automata and formalize the gossip problem in terms of these automata. To do this, we define a natural partial order on events in the system. In Section 2 we introduce ideals and frontiers, both of which play a crucial role in the rest of the paper. Sections 3 and 4 describe how to maintain, compare and update in a local manner the latest information about other processes. The next section puts all these ideas together and formally describes the “gossip automaton” which solves the first problem we set out to tackle.

We then move to recognizable trace languages and Zielonka’s theorem. Section 6 provides the necessary background on traces. (We restrict ourselves to the notions we need. We ensure, however, that the presentation is self-contained.) In Section 7 we then introduce the notion of residues and use it to provide our proof of Zielonka’s theorem. We compare our construction with Zielonka’s original construction in Section 8.

In the concluding Discussion, we place our results in perspective. We discuss similarities and differences with other work on “gossiping” and bounded time-stamps [HHL, IL, DS, CS]. We also compare our proof with those based on asynchronous cellular automata [CMZ, Die]. Finally, we discuss other applications of the gossip automaton in logic and the theory of asynchronous automata [KMS, Thi].

1 Preliminaries

Let 𝒫 be a finite set of processes which synchronize periodically and let the set of possible synchronizations permitted in the system be denoted 𝒞, where 𝒞 ⊆ (2^{𝒫} − {∅}). So, each element c ∈ 𝒞 is a non-empty subset of 𝒫. When c occurs, the processes in c share all information about their local states and update their states accordingly.

We model a computation of the system as a sequence of communications—that is, a word u ∈ 𝒞^{∗}. Let u be of length m. It is convenient to think of u as a function u : [1..m] → 𝒞, where for natural numbers i and j, [i..j] abbreviates the set {i, i+1, …, j} if i ≤ j and [i..j] = ∅ otherwise. By this convention, the empty word ε is denoted by the unique function ∅ → 𝒞.

Events With u : [1..m] → 𝒞, we associate a set of events ℰ_{u}. Each event e is of the form (i, u(i)), where i ∈ [1..m]. In addition, it is convenient to include an initial event denoted 0. Thus, ℰ_{u} = {0} ∪ {(i, u(i)) | i ∈ [1..m]}.

The initial event marks an implicit synchronization of all the processes before the start of the actual computation. So, if u is the empty word ε, ℰ_{u} = {0}.

Usually, we will write ℰ for ℰ_{u}. For p ∈ 𝒫 and e ∈ ℰ, we write p ∈ e to denote that p ∈ u(i) when e = (i, u(i)); for the initial event 0, we define p ∈ 0 to hold for all p ∈ 𝒫. If p ∈ e, then we say that e is a p-event.

Ordering relations on ℰ The word u imposes a total order on events in ℰ: define e < f if e ≠ f and either e = 0 or e = (i, u(i)), f = (j, u(j)), and i < j. We write e ≤ f if e = f or e < f. Moreover, each process p orders the events in which it participates: define ◁_{p} to be the strict ordering

e ◁_{p} f =^{△} e < f, p ∈ e ∩ f and for all e < g < f, p ∉ g.

[figure: •; •; •; •; •; •; b; •; •; a; •; •; •; c; •; •; a; •; •; b; •; •; b; •; •; a; p; q; r; s; 0; e_{1}; e_{2}; e_{3}; e_{4}; e_{5}; e_{6}; e_{7}]

Figure 1: An example

The set of all p-events in ℰ is totally ordered by ◁_{p}^{∗}, the reflexive, transitive closure of ◁_{p}.

Define e ⊏ f if for some p, e ◁_{p} f and e ⊑ f if e = f or e ⊏ f. Let ⊑^{∗} denote the transitive closure of ⊑. If e ⊑^{∗} f then we say that e is below f. The causality relation ⊑^{∗} is a partial order which models the cause and effect relationship between events in ℰ more accurately than the temporal order <. Synchronizations between disjoint sets of processes can be performed independently—in particular, if two such synchronizations occur consecutively in u, they could also be transposed without affecting the outcome of the computation. Thus, many different rearrangements of the letters is u will, in general, give rise to isomorphic structures (ℰ, ⊑^{∗}).

Example: Let 𝒫 = {p, q, r, s} and 𝒞 = {a, b, c} where a = {p, q}, b = {r, s} and c = {q, r, s}. Figure 1 shows the events ℰ corresponding to the word bacabba. The dashed box corresponds to the “mythical” event 0, which we insert at the beginning for convenience.

In the figure, the arrows between the events denote the relations ◁_{p}, ◁_{q}, ◁_{r} and ◁_{s}. From these, we can compute ⊏ and ⊑^{∗}. Thus, for example, we have e_{1} ⊑^{∗} e_{4} since e_{1} ◁_{r} e_{3} ◁_{q} e_{4}.

Note that 0 is below every event. Also, for each p ∈ 𝒫, the set of all p-events in ℰ is totally ordered by ⊑^{∗} since ◁_{p}^{∗} is contained in ⊑^{∗}.

The set of events below e is denoted e↓. These represent the only synchronizations in ℰ which are “known” to the processes in e when e occurs.

Latest information Let ℰ be the set of events of the communication sequence u : [1..m] → 𝒞. The ⊑^{∗}-maximum p-event in ℰ is denoted max_{p}(ℰ). max_{p}(ℰ) is the last event in ℰ in which p has taken part. Since p ∈ 0 ∈ ℰ and all p-events are totally ordered by ⊑^{∗}, max_{p}(ℰ) is well-defined.

Let p, q ∈ 𝒫. The latest information p has about q in ℰ corresponds to the ⊑^{∗}- maximum q-event in the subset of events max_{p}(ℰ)↓. We denote this event by latest_{p→q}(ℰ). Since all q-events are totally ordered by ⊑^{∗} and q ∈ 0 ⊑^{∗} max_{p}(ℰ), latest_{p→q}(ℰ) is welldefined.

Example: Continuing with our example, in Figure 1, max_{p}(ℰ) = e_{7} whereas max_{s}(ℰ) = e_{6}. latest_{p→q}(ℰ) = e_{7}, but latest_{p→s}(ℰ) = e_{3}. On the other hand, latest_{s→p}(ℰ) = e_{2}.

For any processes p, p′, q ∈ 𝒫, the events latest_{p→q}(ℰ) and latest_{p′→q}(ℰ) are both q-events and are thus always comparable with respect to ⊑^{∗}. Our first goal is to design a scheme whereby each process p maintains a bounded amount of information locally, so that whenever a set of processes c ⊆ 𝒫 synchronizes they can decide amongst themselves which of them has heard most recently from every process in the system. More formally, for every q ∈ 𝒫, all the processes in c should be able to jointly compute which of the events {latest_{p→q}(ℰ)}_{p∈c} is maximum with respect to ⊑^{∗}.

We make precise the notions of bounded and local information using asynchronous automata.

Asynchronous automata

Distributed alphabet Let 𝒫 be a finite set of processes as before. A distributed alphabet is a pair (Σ, θ) where Σ is a finite set of actions and θ : Σ → (2^{𝒫} − {∅}) assigns a non-empty set of processes to each a ∈ Σ.

State spaces With each process p, we associate a finite set of states denoted V_{p}. Each state in V_{p} is called a local state. For P ⊆ 𝒫, we use V_{P} to denote the product ∏_{p∈P} V_{p}. An element v⃗ of V_{P} is called a P -state. A 𝒫-state is also called a global state. Given v⃗ ∈ V_{P}, and P′ ⊆ P, we use v_{P′} to denote the projection of v⃗ onto V_{P′}.

Asynchronous automaton An asynchronous automaton 𝔄 over (Σ, θ) is of the form ({V_{p}}_{p∈𝒫} , {→_{a}}_{a∈Σ}, 𝒱_{0}, 𝒱_{F}), where →_{a} ⊆ V_{θ(a)} ×V_{θ(a)} is the local transition relation for a, and 𝒱_{0}, 𝒱_{F} ⊆ V_{𝒫} are sets of initial and final global states. Intuitively, each local transition relation →_{a} specifies how the processes θ(a) that meet on a may decide on a joint move. Other processes do not change their state. Thus we define the global transition relation

⇒ ⊆ V_{𝒫} × Σ × V_{𝒫} by v⃗ ⟹^{a} v′ if v⃗_{θ(a)} →_{a} v′_{θ(a)} and v⃗_{𝒫−θ(a)} = v′_{𝒫−θ(a)} .

𝔄 is called deterministic if the global transition relation ⟹ of 𝔄 is a function from V_{𝒫} × Σ to V_{𝒫} and the set of initial states 𝒱_{0} is a singleton. Notice that ⟹ is a function iff each local transition relation →_{a}, a ∈ Σ, is a function from V_{θ(a)} to V_{θ(a)}. All the asynchronous automata we deal with in this paper will be deterministic.

Runs Given a word u : [1..m] → Σ, a run of 𝔄 on u is a function ρ : [0..m] → V_{𝒫} such that ρ(0) ∈ 𝒱_{0} and for i ∈ [1..m], ρ(i−1) ⟹^{u(i)} ρ(i). If 𝔄 is deterministic, each word u gives rise to a unique run which we denote ρ_{u}.

The word u is accepted by 𝔄 if there is a run ρ of 𝔄 on u such that ρ(m) ∈ 𝒱_{F}. L(𝔄), the language recognized by 𝔄, is the set of words accepted by 𝔄.

For the moment, we will not look at asynchronous automata as language recognizers. Instead, we want to treat them as devices for locally computing families of functions.

Locally computable functions Let Val be a set (of values). A Σ-indexed family of functions is a set ℱ_{Σ} = {f_{a} : Σ^{∗} → Val}_{a∈Σ}. So, ℱ_{Σ} contains a function f_{a} for each letter a ∈ Σ.

ℱ_{Σ} is locally computable if we can find a deterministic asynchronous automaton 𝔄 = ({V_{p}}_{p∈𝒫} , {→_{a}}_{a∈Σ}, 𝒱_{0}, 𝒱_{F}) and a family of local functions 𝒢_{Σ} = {g_{a} : V_{θ(a)} → Val}_{a∈Σ}, such that for each word u : [1..m] → Σ, f_{a}(u) = g_{a}(v⃗_{θ(a)}), where v⃗ = ρ_{u}(m) and ρ_{u} is the unique run of 𝔄 over u.

In other words, the processes in θ(a) can locally compute the value f_{a}(u) for any u ∈ Σ^{∗} by applying the function g_{a} to the (unique) θ(a)-state reached by the automaton after reading u.

Our problem involving the latest information of processes in 𝒫 can now be formalized in terms of asynchronous automata.

Given 𝒞 ⊆ (2^{𝒫} − {∅}), let Σ = {ĉ}_{c∈𝒞}. The distribution function θ is defined in the obvious way—for each ĉ ∈ Σ, θ(ĉ) = c. For convenience, henceforth we shall drop the distinction between a subset c ∈ 𝒞 and the corresponding letter ĉ ∈ Σ and refer to both as just c. Thus, we will use V_{c} to denote the set of θ(ĉ)-states and →_{c} to denote the local transition function for ĉ.

Let u : [1..m] → Σ be a communication sequence and c ⊆ 𝒫. For each q ∈ 𝒫, we denote by best_{c}(u, q) the set of processes in c which have the most recent information about q at the end of u—i.e.,

best_{c}(u, q) = {p ∈ c | ∀p′ ∈ c. latest_{p′→q}(ℰ_{u}) ⊑^{∗} latest_{p→q}(ℰ_{u})}.

Let Val = (2^{𝒫} − {∅})^{𝒫} . So, each member of Val is a function from 𝒫 to non-empty subsets of 𝒫. Our first goal is to show that the family of functions {latest-gossip_{c} : Σ^{∗} → Val}_{c∈Σ} is locally computable, where:

∀u ∈ Σ^{∗}. ∀c ∈ Σ. latest-gossip_{c}(u) is the function {p ↦ best_{c}(u, p)}_{p∈𝒫} .

2 Ideals and Frontiers

For the moment, let us fix a communication sequence u : [1..m] → Σ and the corresponding set of events ℰ.

The main source of difficulty in solving the gossip problem is the fact that the processes in 𝒫 need to compute global information about the communication sequence u while each process only has access to a local, “partial” view of u. Although partial views of u correspond to subsets of ℰ, not every subset of ℰ arises from such a partial view. Those subsets of ℰ which do correspond to partial views of u are called ideals.

Ideals A set of events I ⊆ ℰ is called an order ideal if I is closed with respect to ⊑^{∗}— i.e., e ∈ I and f ⊑^{∗} e implies f ∈ I as well [Sta]. We shall always refer to order ideals as just ideals.^{2}

The requirement that an ideal be closed with respect to ⊑^{∗} guarantees that the observation it represents is “consistent”—whenever an event e has been observed, so have all the events in the computation which necessarily precede e.

2In the theory of partial orders, order ideals and ideals are distinct concepts. Ideals are normally assumed to be subsets which are ⊑^{∗}-closed and directed. We shall, however, deal only with order ideals in this paper and so our terminology should cause no confusion.

Intuitively, the minimum possible partial view of a word u is the ideal {0}. This is because of our interpretation of 0 as an event which takes place before the actual computation begins. Hence, we shall assume that every ideal we consider is non-empty. Since 0 lies below every event in ℰ, 0 ∈ I for every non-empty ideal I.

Clearly the entire set ℰ is an ideal, as is e↓ for any e ∈ ℰ. Ideals of the form e↓ are special ideals, called principal ideals—e↓ is the principal ideal generated by e. It is not difficult to show that any ideal I is the union of the principal ideals generated by the set of events E = {e | e is ⊑^{∗}-maximal in I}. In general, if E is a set of events such that I = ⋃_{e∈E} e↓, we say that I is generated by E. It is easy to see that if I and J are ideals, so are I ∪ J and I ∩ J.

Example: Let us look once again at Figure 1. {0, e_{2}} is an ideal, but {0, e_{2}, e_{3}} is not, since e_{1} ⊑^{∗} e_{3} but e_{1} ∉ {0, e_{2}, e_{3}}. {0, e_{1}, e_{2}, e_{3}, e_{5}} is the principal ideal e_{5} ↓, whereas {0, e_{1}, e_{2}, e_{3}, e_{4}, e_{5}} is a non-principal ideal generated by {e_{4}, e_{5}}.

We need to generalize the notion of max_{p}(ℰ), the maximum p-event in ℰ, to all ideals I ⊆ ℰ.

P -views For an ideal I, the ⊑^{∗}-maximum p-event in I is denoted max_{p}(I). The p-view of I is the set I|_{p} = max_{p}(I)↓. So, I|_{p} is the set of all events in I which p can “see”. For P ⊆ 𝒫, the P -view of I, denoted I|_{P}, is ⋃_{p∈P} I|_{p}, which is also an ideal. In particular, we have I|_{𝒫} = I.

Example: In Figure 1, let I denote the ideal {0, e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}}. max_{q}(I) = e_{4} and hence I|_{q} = {0, e_{1}, e_{2}, e_{3}, e_{4}}. On the other hand, though max_{r}(I) = e_{6}, I|_{r} ≠ I; I|_{r} = I − {e_{4}}. The joint view I|_{{q,r}} = I = I|_{𝒫} .

For an ideal I, the views I|_{p} and I|_{q} seen by two processes p, q ∈ 𝒫 are, in general, incomparable. The events in I where these two views begin to diverge—the frontier of I|_{p} ∩ I|_{q}—play a crucial role in our analysis.

Frontiers Let I be an ideal and p, q, r ∈ 𝒫. We say that an event e is an r-sentry for p with respect to q if e ∈ I|_{p} ∩ I|_{q} and e ◁_{r} f for some f ∈ I|_{q} − I|_{p}. Thus e is an event known to both p and q whose r-successor is known only to q. Notice that there need not always be an r-sentry for p with respect to q.

The pq-frontier at I, frontier_{pq}(I) is defined as follows:

frontier_{pq}(I) = {e ∈ I | ∃r ∈ 𝒫. e is an r-sentry for p with respect to q}

Observe that this definition is asymmetric—in general, frontier_{pq}(I) ≠ frontier_{qp}(I).

Example: As before, in Figure 1, let I denote the ideal {0, e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}}. I|_{q}∩I|_{r} = {0, e_{1}, e_{2}, e_{3}}. frontier_{rq}(I) = {e_{2}, e_{3}}—e_{2} is a p-sentry for r with respect to q whereas e_{3} is a q-sentry. On the other hand, frontier_{qr}(I) = {e_{3}}. e_{3} is both an r-sentry as well as an s-sentry for q with respect to r.

As the example demonstrates, an event e ∈ frontier_{pq}(I) could simultaneously be an rsentry for p for several different processes r. However, it is not difficult to show that for any process r, there is at most one r-sentry for p with respect to q.

3 Primary and secondary information

For a word u and processes p, q ∈ 𝒫, we have already defined latest_{p→q}(ℰ), the latest information that p has about q after u. We now extend this definition to arbitrary ideals.

Primary information Let I be an ideal and p, q ∈ 𝒫. Then latest_{p→q}(I) denotes the ⊑^{∗}-maximum q-event in I|_{p}. So, latest_{p→q}(I) is the latest q-event in I that p knows about.

The primary information of p after I, primary_{p}(I), is the set {latest_{p→q}(I)}_{q∈𝒫} . More precisely, primary_{p}(I) is an indexed set of events—each event e = latest_{p→q}(I) in primary_{p}(I) is represented as a triple (p, q, e). As usual, for P ⊆ 𝒫, primary_{P} (I) = ⋃_{p∈P} primary_{p}(I).

As we have already remarked, for all q ∈ 𝒫, the set of q-events in I|_{p} is always nonempty, since q ∈ 0 ∈ I|_{p}. Further, since all q-events are totally ordered by ◁_{q}^{∗} and hence by ⊑^{∗}, the maximum q-event in I|_{p} is well-defined. Notice that latest_{p→p}(I) = max_{p}(I).

To compare primary events, processes need to maintain additional information. It turns out that it is sufficient for each process to keep track of all the other processes’ primary information.

Secondary information The secondary information of p after I, secondary_{p}(I), is the (indexed) set ⋃_{q∈𝒫} primary_{q}(latest_{p→q}(I)↓). In other words, this is the latest information that p has in I about the primary information of q, for each q ∈ 𝒫. Once again, for P ⊆ 𝒫, secondary_{P} (I) = ⋃_{p∈P} secondary_{p}(I).

Each event in secondary_{p}(I) is of the form latest_{q→r}(latest_{p→q}(I)↓) for some q, r ∈ 𝒫. This is the latest r-event which q knows about upto the event latest_{p→q}(I). We abbreviate latest_{q→r}(latest_{p→q}(I)↓) by latest_{p→q→r}(I).

Just as we represented events in primary_{p}(I) as triples of the form (p, q, e), where p, q ∈ 𝒫 and e ∈ I, we represent each secondary event e = latest_{p→q→r}(I) in secondary_{p}(I) as a quadruple (p, q, r, e).

However, we will often ignore the fact that primary_{p}(I) and secondary_{p}(I) are indexed sets of events and treat them, for convenience, as just sets of events. Thus, for an event e ∈ I, we shall write e ∈ primary_{p}(I) to mean that there exists a process q ∈ 𝒫 such that (p, q, e) ∈ primary_{p}(I)—i.e., e = latest_{p→q}(I). Similarly, e ∈ secondary_{p}(I) will indicate that for some q, r ∈ 𝒫, (p, q, r, e) ∈ secondary_{p}(I). We extend this to other settheoretic operations as well. So, for instance, if we say e ∈ primary_{p}(I) ∩ secondary_{q}(I), we mean that we can find p′, q′, q′′ ∈ 𝒫 such that (p, p′, e) ∈ primary_{p}(I) and (q, q′, q′′, e) ∈ secondary_{q}(I).

Notice that each primary event latest_{p→q}(I) is also a secondary event latest_{p→p→q}(I) (or, equivalently, latest_{p→q→q}(I)). So, following our convention that primary_{p}(I) and secondary_{p}(I) be treated as sets of events, we write primary_{p}(I) ⊆ secondary_{p}(I).

Comparing primary information

Our goal is to compare and update the primary information of processes whenever they meet. For this, we need the following observation regarding the significance of events lying on frontiers.

Lemma 1 Let I be an ideal, p, q ∈ 𝒫 and e ∈ frontier_{pq}(I) an r-sentry for p with respect to q. Then e = latest_{p→r}(I). Also, for some r′ ∈ 𝒫, e = latest_{q→r′→r}(I). So, e ∈ primary_{p}(I) ∩ secondary_{q}(I).

Proof Since e is an r-sentry, for some f ∈ I|_{q} − I|_{p}, e ◁_{r} f. Suppose that latest_{p→r}(I) = e′ ≠ e. Since all r-events are totally ordered by ◁_{r}^{∗}, we must have e ◁_{r}^{+} e′ (where ◁_{r}^{+} is the transitive closure of the irreflexive relation ◁_{r}). However, e ◁_{r} f as well, so we have e ◁_{r} f ◁_{r}^{∗} e′. This means that f ∈ I|_{p}, which is a contradiction.

Next, we must show that e = latest_{q→r′→r}(I) for some r′ ∈ 𝒫. We know that there is a path e ⊏ f_{1} ⊏ ⋯ ⊏ max_{p}(I), since e ∈ I|_{p}. This path starts inside I|_{p} ∩ I|_{q}.

If this path never leaves I|_{p} ∩ I|_{q} then max_{p}(I) ∈ I|_{q}. Since max_{p}(I) is the maximum p-event in I, it must be the maximum p-event in I|_{q}. So, e = latest_{q→p→r}(I) and we are done.

If this path does leave I|_{p} ∩ I|_{q}, we can find an event e′ along the path such that e ⊑^{∗} e′ ◁_{r′} f′ ⊑^{∗} max_{p}(I), where e′ ∈ I|_{p} ∩ I|_{q}, f′ ∈ I|_{p} − I|_{q} and r′ ∈ e′ ∩ f′. In other words, e′ is an r′-sentry for q with respect to p. We know by our earlier argument that e′ = latest_{q→r′}(I). It must be the case that e = latest_{r′→r}(e′ ↓). For, if latest_{r′→r}(e′ ↓) = e′′ ≠ e, then e ◁_{r}^{+} e′′ ⊑^{∗} e′ ⊑^{∗} max_{p}(I). Since e′′ ∈ I|_{p} and e ◁_{r}^{+} e′′, e ≠ latest_{p→r}(I), which is a contradiction. So, e = latest_{r′→r}(e′↓) = latest_{q→r′→r}(I) and we are done. □

Our observation about frontier events immediately gives us a way to compare primary information using both primary and secondary information.

Lemma 2 Let I be an ideal and p, q, r ∈ 𝒫. Let e = latest_{p→r}(I) and f = latest_{q→r}(I). Then e ⊑^{∗} f iff e ∈ secondary_{q}(I).

Proof

(⇐) Suppose e ∈ secondary_{q}(I). Then r ∈ e ∈ I|_{q} and so e ⊑^{∗} f ∈ I|_{q} by the definition of latest_{q→r}(I).

(⇒) If e = f, e ∈ primary_{q}(I) ⊆ secondary_{q}(I), and there is nothing to prove. If e ≠ f, then there exists an event e′ such that e ◁_{r} e′ ◁_{r}^{∗} f and so e ∈ I|_{p} ∩ I|_{q}. We know that e′ ∈ I|_{q} − I|_{p}, so e is an r-sentry in frontier_{pq}(I). But then, by our previous lemma, e ∈ primary_{p}(I) ∩ secondary_{q}(I) and we are done. □

Suppose p and q synchronize at an action a after u. At this point they “share” their primary and secondary information. If q can find the event latest_{p→r}(ℰ_{u}) in its set of secondary events secondary_{q}(ℰ_{u}), q knows that its latest r-event latest_{q→r}(ℰ_{u}) is at least as recent as latest_{p→r}(ℰ_{u}). So, after the synchronization, latest_{q→r}(ℰ_{ua}) is the same as latest_{q→r}(ℰ_{u}), whereas p inherits this information from q—i.e., latest_{p→r}(ℰ_{ua}) = latest_{q→r}(ℰ_{u}). In this way, for each r ∈ 𝒫, p and q locally update their primary information about r in ℰ_{ua}. Clearly latest_{p→q}(ℰ_{ua}) = latest_{q→p}(ℰ_{ua}) = e_{a}, where e_{a} is the new event— i.e., ℰ_{ua} − ℰ_{u} = {e_{a}}.

This procedure generalizes to any arbitrary set P ⊆ 𝒫 which synchronizes after u. The processes in P share their primary and secondary information and compare this information pairwise. Using Lemma 2, for each q ∈ 𝒫−P they decide who has the “latest information” about q. Each process then comes away with the best primary information from P.

Once we have compared primary information, updating secondary information is straightforward. Clearly, if latest_{q→r}(I) is better than latest_{p→r}(I), then every secondary event latest_{q→r→r′}(I) must also be better than the corresponding event latest_{p→r→r′}(I). So, secondary information can be locally updated too. In other words, to consistently update primary and secondary information, it suffices to correctly compare primary information, which is achieved by Lemma 2.

After a synchronization involving P ⊆ 𝒫, notice that all processes in P will come away with the same set of primary and secondary events.

From the preceding argument, it is clear that the new event belongs to the primary (and hence secondary) information of the processes which synchronize at that event. Further, the update procedure reveals that if an event disappears from the secondary information of all the processes, it will never reappear as secondary information at some later stage. This is captured formally in the following proposition.

Proposition 3 Let u, w ∈ Σ^{∗} such that w = ua for some a ∈ Σ. Let e_{a} denote the new event in w—i.e., ℰ_{w} − ℰ_{u} = {e_{a}}. Then:

• e_{a} ∈ primary_{𝒫} (ℰ_{w}).

• primary_{𝒫} (ℰ_{w}) ⊆ {e_{a}} ∪ primary_{𝒫} (ℰ_{u}).

• secondary_{𝒫} (ℰ_{w}) ⊆ {e_{a}} ∪ secondary_{𝒫} (ℰ_{u}).

4 Locally updating primary/secondary information

To make Lemma 2 effective, we must make the assertions “locally checkable”—e.g., if e = latest_{p→r}(I), processes p and q must be able to decide if e ∈ secondary_{q}(I).

Recall that e is represented in primary_{p}(I) as a triple of the form (p, r, e). So, to check if e ∈ secondary_{q}(I), q has to look for a quadruple of the form (q, r′, r′′, e) ∈ secondary_{q}(I), where r′, r′′ ∈ 𝒫. This can be checked locally provided events in ℰ_{u} are labelled unambiguously while u is being read.

Clearly, labelling each event e as a pair (i, u(i)) is impossible since, in general, there is no agent which can consistently supply all processes with the “correct” value of i. Instead, we may naïvely assume that events in ℰ_{u} are locally assigned distinct labels—in effect, at each action a, the processes in a together assign a (sequential) time-stamp to the new occurrence of a. In this manner, the processes in 𝒫 can easily assign consistent local time-stamps for each action which will let them compute the relations ◁_{p}^{∗} between events.

The problem with this approach is that we will need an unbounded set of time-stamps, since u could get arbitrarily large. Instead we would like a scheme which uses only a finite set of labels to distinguish events. This means that several different occurrences of the same action will eventually get the same label. Since the update of primary and secondary information relies on comparing labels, we must ensure that this reuse of labels does not lead to any confusion.

However, from Lemma 2, we know that to compare primary information, we only need to look at the events which are currently in the primary and secondary sets of each

[figure: •; •; •; •; •; •; c; •; •; b; •; •; a; •; •; d; •; •; e; •; •; c; •; •; c; p; q; r; s; 0; e_{1}; e_{2}; e_{3}; e_{4}; e_{5}; e_{6}; e_{7}]

Figure 2: Another example

process. So, it is sufficient if the labels assigned to these sets are consistent across the system—i.e., if the same label appears in the current primary or secondary information of different processes, the corresponding event is actually the same.

Notice that we do not need to maintain a global temporal order on labels across the system. Lemma 2 assures us that to compare events of interest to us, it suffices to check for equality of labels assigned to the events.

Suppose we have such a labelling on u and we want to extend this to a consistent labelling on w = ua—i.e., we need to assign a label to the new a-event. By Proposition 3, it suffices to use a label which is distinct from the labels of all the a-events currently in the secondary information of ℰ_{u}. Since the cardinality of secondary_{𝒫} (ℰ_{u}) is bounded, such a new label must exist. The catch is to detect which labels are currently in use and which are not.

Unfortunately, the processes in a cannot directly see all the a-events which belong to the secondary information of the entire system. An a-event e may be part of the secondary information of processes outside a—i.e., e ∈ secondary_{𝒫−a} (ℰ_{u}) − secondary_{a}(ℰ_{u}).

Example: Let 𝒫 = {p, q, r, s} and Σ = {a, b, c, d, e} where a = {p, q}, b = {q, r}, c = {r, s}, d = {p, s} and e = {q, s}. Figure 2 shows the events ℰ corresponding to the word cbadecc.

At the end of this word, e_{1} = latest_{p→q→s}(ℰ). However, e_{1} ∉ secondary_{s}(ℰ);

secondary_{s}(ℰ) = \begin{aligned}\{ & (s, p, p, e_{4}), (s, p, q, e_{3}), (s, p, r, e_{2}), (s, p, s, e_{4}), \\ & (s, q, p, e_{4}), (s, q, q, e_{5}), (s, q, r, e_{2}), (s, q, s, e_{5}), \\ & (s, r, p, e_{4}), (s, r, q, e_{5}), (s, r, r, e_{7}), (s, r, s, e_{7}), \\ & (s, s, p, e_{4}), (s, s, q, e_{5}), (s, s, r, e_{7}), (s, s, s, e_{7}) \}. \end{aligned}

Since max_{r}(ℰ) = max_{s}(ℰ), secondary_{r}(ℰ) = secondary_{s}(ℰ) when viewed as sets of events. So, e_{1} ∉ secondary_{r}(ℰ) either. Thus, e_{1} is a c-event which belongs to secondary_{𝒫} (ℰ) − secondary_{c}(ℰ).

To enable the processes in a to know about all a-events in secondary_{𝒫} (ℰ_{u}), we need to maintain tertiary information.

Tertiary information The tertiary information of p after I, tertiary_{p}(I), is the (indexed) set ⋃_{q∈𝒫} secondary_{q}(latest_{p→q}(I)↓). In other words, this is the latest information that p has in I about the secondary information of q, for all q ∈ 𝒫. As before, for P ⊆ 𝒫, tertiary_{P} (I) = ⋃_{p∈P} tertiary_{p}(I).

Each event in tertiary_{p}(I) is of the form latest_{q→r→s}(latest_{p→q}(I)↓) for some q, r, s ∈ 𝒫. We abbreviate latest_{q→r→s}(latest_{p→q}(I)↓) by latest_{p→q→r→s}(I). We represent each event e = latest_{p→q→r→s}(I) as a quintuple (p, q, r, s, e) in tertiary_{p}(I). However, for convenience we will work with tertiary_{p}(I) as though it were simply a set of events, rather than an indexed set, just as we have been doing with primary and secondary information.

Just as primary_{p}(I) ⊆ secondary_{p}(I), clearly secondary_{p}(I) ⊆ tertiary_{p}(I) since each secondary event latest_{p→q→r}(I) is also a tertiary event latest_{p→p→q→r}(I) (or, equivalently, latest_{p→q→q→r}(I) and so on).

Lemma 4 Let I be an ideal and p ∈ 𝒫. If e ∈ secondary_{p}(I) then for every q ∈ e, e ∈ tertiary_{q}(I).

Proof Let e ∈ secondary_{p}(I) and q ∈ e. Concretely, let e = latest_{p→p′→p′′}(I) for some p′, p′′ ∈ 𝒫. We know that e ∈ I|_{p} ∩ I|_{q} and there is a path e ⊏ f_{1} ⊏ ⋯ ⊏ max_{p}(I) leading from e to max_{p}(I) which passes through e′ = latest_{p→p′}(I).

Suppose this path never leaves I|_{p} ∩ I|_{q}. Then max_{p}(I) ∈ I|_{q} and so max_{p}(I) = latest_{q→p}(I). This means that e ∈ secondary_{p}(latest_{q→p}(I)↓) ⊆ tertiary_{q}(I) and we are done.

Otherwise, the path from e to max_{p}(I) does leave I|_{p} ∩ I|_{q} at some stage.

If e′ ∉ I|_{p} ∩ I|_{q} then for some f, f′ ∈ ℰ and some r ∈ 𝒫 we have f ∈ I|_{p} ∩ I|_{q}, f′ ∈ I|_{p} − I|_{q} and e ⊑^{∗} f ◁_{r} f′ ⊑^{∗} e′. This means that f ∈ frontier_{qp}(I) is an r-sentry and by our earlier argument we know that f = latest_{q→r}(I). So e = latest_{q→r→p′′}(I) = latest_{q→q→r→p′′}(I) ∈ tertiary_{q}(I).

On the other hand, if e′ ∈ I|_{p} ∩ I|_{q} we can find an r-sentry f ∈ frontier_{qp}(I) on the path from e′ to max_{p}(I), for some r ∈ 𝒫. We once again get f = latest_{q→r}(I) and so e = latest_{q→r→p′→p′′}(I) ∈ tertiary_{q}(I).

□

We shall use this lemma in the following form.

Corollary 5 Let I be an ideal, p ∈ 𝒫 and e a p-event in I. If e ∉ tertiary_{p}(I) then e ∉ primary_{𝒫} (I) ∪ secondary_{𝒫} (I).

So, a process p can keep track of which of its labels are “in use” in the system by maintaining tertiary information. Each p-event e initially belongs to primary_{e}(I), and hence to secondary_{e}(I) and tertiary_{e}(I) as well. (Recall that for an event e, we also use e to denote the subset of 𝒫 which meets at e). As the computation progresses, e gradually “recedes” into the background and disappears from the primary and secondary sets of the system. Eventually, when e disappears from tertiary_{p}(I), p can be sure that e no longer belongs to primary_{𝒫} (I) ∪ secondary_{𝒫} (I).

Since tertiary_{p}(I) is a bounded set, p knows that only finitely many of its labels are in use at any given time. So, by using a sufficiently large finite set of labels, each new event can always be assigned an unambiguous label by the processes which take part in the event.

5 The “gossip” automaton

Using our analysis of primary, secondary and tertiary information of processes, we can now design a deterministic asynchronous automaton to keep track of the “latest gossip”—i.e., to consistently update primary information whenever a set of processes synchronizes.

For p ∈ 𝒫, each local state of p will consist of its primary, secondary and tertiary information, stored as indexed collections or arrays. Each event in these arrays is represented as a pair ⟨P, ℓ⟩, where P is the subset of processes that synchronized at the event and ℓ ∈ ℒ, a finite set of labels. We shall establish a bound on |ℒ| shortly.

The initial state is the global state where for all processes p, all entries in these arrays correspond to the initial event 0. The event 0 is denoted by ⟨𝒫, ℓ_{0}⟩ for an arbitrary but fixed label ℓ_{0} ∈ ℒ.

The local transition functions →_{a} modify the local states for processes in a as follows.

(i) When a new a-labelled event e occurs after u, the processes in a assign a label ⟨a, ℓ⟩ to e which does not appear in tertiary_{a}(ℰ_{u}). Corollary 5 guarantees that this new label does not appear in primary_{𝒫} (ℰ_{u}) or secondary_{𝒫} (ℰ_{u}).

Proposition 3 guarantees that all new primary and secondary events—i.e., events in primary_{𝒫} (ℰ_{ua}) and secondary_{𝒫} (ℰ_{ua})—are assigned distinct labels.

Let N = |𝒫|. Since each process keeps track of N^{3} tertiary events and at most N processes can synchronize at an event, there need be only N^{4} labels in ℒ. (In fact, in Lemma 7 below, we show that it suffices to have N^{3} labels in ℒ.)

(ii) The processes participating in e now compare their primary information about each process q ∉ e by checking labels of events across their primary and secondary sets as described in Lemma 2.

(iii) Each process then updates its primary, secondary and tertiary information according to the new information it receives. Tertiary information, like secondary information, can be locally updated once the processes have decided who has the best primary information—if p, q ∈ a and latest_{p→r}(ℰ_{u}) is better than latest_{q→r}(ℰ_{u}) for r ∈ 𝒫, then any tertiary information of the form latest_{p→r→r′→r′′}(ℰ_{u}) must necessarily be better than the corresponding information latest_{q→r→r′→r′′}(ℰ_{u}), for r′, r′′ ∈ 𝒫.

This automaton does not have any final states, since we do not need to accept any language. Instead, we define for each a ∈ Σ a function g_{a} : V_{a} → (2^{𝒫} − {∅})^{𝒫} which checks the primary and secondary information of processes in a and computes for each q ∈ 𝒫, the set of processes in a which have the most recent information about q.

(A small technical point: g_{a} must be defined for all states in V_{a}. However, not all combinations of local states may be “meaningful”. We can easily assemble local states to form an a-state for which the inductive assertions do not hold, as a result of which our procedure for comparing primary information breaks down. However, since such a-states are unreachable, we can ignore this problem and simply assign a default value to g_{a} in these cases—for instance, the default value could be the function {p ↦ a}_{p∈𝒫} .)

This immediately yields the first result we set out to establish.

Theorem 6 Let (Σ, θ) be the distributed alphabet corresponding to 𝒞 ⊆ (2^{𝒫} − {∅}). The family of functions {latest-gossip_{c} : Σ^{∗} → (2^{𝒫} − {∅})^{𝒫} }_{c∈Σ} is locally computable.

So far, we have been working with a special distributed alphabet (Σ, θ), where θ is an injective function from Σ to 2^{𝒫} − {∅}. In general, we could have a, b ∈ Σ such that θ(a) = θ(b). However, in the construction of the gossip automaton, the “name” of the action attached to each event is irrelevant. For any word u, the structure of (ℰ_{u}, ⊑^{∗}) depends only on the sets of processes which synchronize at each event. So, if θ(a) = θ(b), we have latest-gossip_{a}(u) = latest-gossip_{b}(u) for all words u and, correspondingly, the local functions g_{a} and g_{b} are the same.

So, to construct the gossip automaton for a distributed alphabet (Σ, θ) where θ is not injective, we can ignore the distinction between letters which have the same distribution. In other words, we set the communication alphabet 𝒞 ⊆ (2^{𝒫} − {∅}) to the range of θ and proceed as we have done here.

The size of the gossip automaton

Lemma 7 In the gossip automaton, the number of local states of each process p ∈ 𝒫 is at most 2^{O(N^{3} log N)}, where N = |𝒫|.

Proof A local state for p consists of its primary, secondary and tertiary information. We estimate how many bits are required to store this.

Recall that for any ideal I, each event in primary_{p}(I) is also present in secondary_{p}(I). Similarly, each event in secondary_{p}(I) is also present in tertiary_{p}(I). So it suffices to store just the labels of tertiary events. These events are stored in an array with N^{3} entries, where each entry is implicitly indexed by a triple from 𝒫 × 𝒫 × 𝒫.

Each new event e was assigned a label of the form ⟨P, ℓ⟩, where P was the set of processes that participated in e and ℓ ∈ ℒ.

We argued earlier that it suffices to have N^{4} labels in ℒ. Actually, we can make do with N^{3} labels by modifying our transition function slightly. When a letter a is read, instead of immediately labelling the new event, the processes in a first compare and update their primary, secondary and tertiary information about processes from 𝒫 − a. These updates concern events which have already been labelled, so the fact that the new event has not yet been labelled is not a problem. Once this is done, all the processes in a will have the same primary, secondary and tertiary information. At this stage, there are (less than) N^{3} distinct labels present in tertiary_{a}(I). So, if |ℒ| = N^{3} the processes are guaranteed to find a label they can use for the new event. Regardless of which update strategy we choose, ℓ ∈ ℒ can be written down using O(log N) bits.

To write down P ⊆ 𝒫, we need, in general, N bits. This component of the label is required to guarantee that all secondary events in the system have distinct labels, since the set ℒ is common across all processes. However, we do not really need to use all of P in the label for e to ensure this property. If we order 𝒫 as {p_{1}, p_{2}, …, p_{N}}, it suffices to label e by ⟨p_{i}, ℓ⟩ where, among the processes in P, p_{i} has the least index with respect to our ordering of 𝒫.

Thus, we can modify our automaton so that the processes label each event by a pair ⟨p, ℓ⟩, where p ∈ 𝒫 and ℓ ∈ ℒ. This pair can be written down using O(log N) bits. Overall there are N^{3} such pairs in the array of tertiary events, so the whole state can be described using O(N^{3} log N) bits. Therefore, the number of distinct local states of p is bounded by 2^{O(N^{3} log N)}. □

6 Recognizable trace languages

We now apply the gossip automaton to establish the second major result of this paper—an “algorithmic” proof of Zielonka’s theorem that asynchronous automata accept precisely the class of recognizable trace languages. We begin by providing a brief introduction to recognizable trace languages.

Concurrent alphabet A distributed alphabet (Σ, θ) gives rise to a natural independence relation I_{θ} between letters: (a, b) ∈ I_{θ} iff θ(a) ∩ θ(b) = ∅. Thus, a and b are independent when processed by disjoint sets of agents in the system. Clearly, the relation I_{θ} is irreflexive and symmetric. Such a relation is called an independence relation.

An alphabet equipped with an independence relation is also called a concurrent alphabet. This notion was introduced by Mazurkiewicz as a technique for studying concurrent systems from the viewpoint of formal language theory [Maz].

Traces and trace languages Given a concurrent alphabet (Σ, I), I induces a natural equivalence relation ∼ on Σ^{∗}: two words w and w′ are related by ∼ iff w′ can be obtained from w by a sequence of permutations of adjacent independent letters. More formally, w ∼ w′ if there is a sequence of words v_{1}, v_{2}, …, v_{k} such that w = v_{1}, w′ = v_{k} and for each i ∈ [1..k−1], there exist words u_{i}, u′_{i} and letters a_{i}, b_{i} satisfying

v_{i} = u_{i}a_{i}b_{i}u′_{i}, v_{i+1} = u_{i}b_{i}a_{i}u′_{i} and (a_{i}, b_{i}) ∈ I.

Actually, ∼ defines a congruence on Σ^{∗} with respect to concatenation: If u ∼ u′ then for any words w_{1} and w_{2}, w_{1}uw_{2} ∼ w_{1}u′w_{2}. Also, both right and left cancellation preserve ∼-equivalence: wu ∼ wu′ implies u ∼ u′ and uw ∼ u′w implies u ∼ u′.

The quotient of Σ^{∗} by the congruence ∼ is the free partially commutative monoid induced by I. We denote this quotient monoid ℳ(Σ, I). The elements of ℳ(Σ, I) correspond to equivalence classes of words of Σ^{∗} under ∼ and are called traces. Let [w] denote the ∼-equivalence class corresponding to the word w. Since the relation ∼ is a congruence, the composition operation in ℳ(Σ, I) is given by

∀u, v ∈ Σ^{∗}. [u][v] = [uv].

Subsets of the trace monoid ℳ(Σ, I) are called trace languages. To define recognizable trace languages we need to define monoid automata.

Monoid automaton Let (M, ·, ε) be a monoid, where ε is the unit. A monoid automaton over M is a structure 𝔐 = (S, M, δ, s_{0}, S_{F}) where S is a finite set of states, s_{0} ∈ S is the initial state, S_{F} ⊆ S is the set of final states and δ : S × M → S is the transition function such that:

• ∀s ∈ S. δ(s, ε) = s.

• ∀s ∈ S. ∀m_{1}, m_{2} ∈ M. δ(s, m_{1} · m_{2}) = δ(δ(s, m_{1}), m_{2}).

𝔐 is said to recognize the subset T = {m ∈ M | δ(s_{0}, m) ∈ S_{F} }.

Recognizable trace languages So, a trace language T is recognizable iff we can find a monoid automaton over the trace monoid ℳ(Σ, I) which recognizes T. (More formally, recognizability is defined in terms of homomorphisms into a finite monoid, but for our purposes, this definition suffices.)

We prefer to treat trace languages as string languages which satisfy a closure condition rather than as subsets of the trace monoid ℳ(Σ, I). We say that L ⊆ Σ^{∗} is a trace language if L is ∼-consistent—i.e., for each w ∈ Σ^{∗}, w is in L iff every word in [w] is in L. Since traces correspond to equivalence classes of strings, there is a 1-1 correspondence between subsets of ℳ(Σ, I) and ∼-consistent languages over Σ^{∗}.

In the string framework, we say a trace language L is recognizable if it is accepted by a conventional finite state automaton. Once again, it is not difficult to show that there is a 1-1 correspondence between recognizable subsets of ℳ(Σ, I) and recognizable ∼-consistent languages over Σ^{∗} (see, for instance, [CMZ]).

Henceforth, whenever we use the terms trace language and recognizable trace language, we shall be referring to the definitions in terms of ∼-consistent subsets of Σ^{∗} rather than in terms of subsets of ℳ(Σ, I).

Given a concurrent alphabet (Σ, I), there are several ways to construct a distributed alphabet (Σ, θ) so that the independence relation I_{θ} induced by θ coincides with I.

We begin by building the dependence graph for (Σ, I). Let 𝒟 = (Σ × Σ) − I. 𝒟 is called the dependence relation. Construct a graph G_{𝒟} whose vertices are labelled by Σ. Draw an edge between vertices labelled a and b provided (a, b) ∈ 𝒟.

One way to distribute Σ is to create a process p_{e} for every edge e in G_{𝒟} . For each letter a, we then set θ(a) to be the set of processes corresponding to edges incident on the vertex labelled a.

Alternately, we can create a process p_{C} for each maximal clique C in G_{𝒟} . Then, for each letter a and each clique C, p_{C} ∈ θ(a) iff the vertex labelled a belongs to C.

In both cases, it is easy to see that I_{θ} = I. So, we can go back and forth between a concurrent alphabet (Σ, I) and a distributed alphabet (Σ, θ) whose induced independence relation I_{θ} is I.

It is not difficult to see that any language accepted by an asynchronous automaton over (Σ, θ) is a recognizable trace language over the corresponding concurrent alphabet (Σ, I_{θ}). The distributed nature of the automaton guarantees that it is a trace language. To see that the language is recognizable, we note that for a given asynchronous automaton 𝔄 = ({V_{p}}_{p∈𝒫} , {→_{a}}_{a∈Σ}, 𝒱_{0}, 𝒱_{F}), we can construct a conventional finite state automaton 𝔅 accepting the same language as 𝔄. The states of 𝔅 are the global states of 𝔄 and the transition relation of 𝔅 is given by the global transition relation ⟹ of 𝔄. Since the initial and accepting states of 𝔄 are specified as global states, they can directly serve as the initial and final states of 𝔅. It is straightforward to verify that 𝔅 accepts the same language as 𝔄.

On the other hand, the converse is difficult to show. For a given recognizable trace language L over a concurrent alphabet (Σ, I), does there exist an asynchronous automaton 𝔄 over a distributed alphabet (Σ, θ) such that 𝔄 accepts L and the independence relation I_{θ} induced by θ is exactly I?

Zielonka’s fundamental result is that this is indeed the case [Zie1]. In other words, asynchronous automata accept precisely the set of recognizable trace languages and thus constitute a natural distributed machine model for this class of languages.

However, Zielonka’s original proof of this theorem is extremely intricate and difficult to follow. Here we provide a “algorithmic” proof of the theorem which crucially uses the local computability of the latest gossip function. We first present our proof in detail and then discuss the connections with Zielonka’s original proof.

7 Residues and Zielonka’s theorem

Fix a recognizable trace language L over a concurrent alphabet (Σ, I), as well as a distribution θ : Σ → (2^{𝒫} −{∅}) such that the induced independence relation I_{θ} is the same as I. We shall construct a deterministic asynchronous automaton 𝔄 = ({V_{p}}_{p∈𝒫} , {→_{a}}_{a∈Σ}, 𝒱_{0}, 𝒱_{F}) over (Σ, θ) recognizing L.

Let 𝔅 be the finite state automaton accepting L. Without loss of generality, we can assume that 𝔅 is the minimal deterministic finite automaton (DFA) for L, as given by the Myhill-Nerode theorem [HU]. Let 𝔅 be of the form (S, Σ, δ, s_{0}, S_{F}) where S denotes the set of states of 𝔅, δ : S × Σ → S the transition function, s_{0} ∈ S the initial state and S_{F} ⊆ S the set of accepting states. As usual, we shall extend δ to a transition function S × Σ^{∗} → S describing state transitions for input words rather than just single letters. For convenience, we denote this extended transition function also by δ.

The main hurdle in constructing our asynchronous automaton 𝔄 from the original DFA 𝔅 is the following: On reading an input word u, we must be able to compute whether δ(s_{0}, u) ∈ S_{F}. Unfortunately, after reading u each process in 𝔄 only has partial information about δ(s_{0}, u)—a process p only “knows about” those events from ℰ_{u} which lie in the p-view max_{p}(ℰ_{u})↓. So, we have to devise a scheme to recover the state δ(s_{0}, u) from the partial information available with each process after reading u.

Another complication is that processes can only maintain a finite amount of information. So, we need a way of representing arbitrary words in a bounded, finite way. This can be done quite easily—the idea is to record for each word w, its “effect” as dictated by our minimal automaton 𝔅.

We first recall a basic fact about recognizable languages. Any language L̂ defines a syntactic congruence ≡L̂ on Σ^{∗} as follows:

For u, u′ ∈ Σ^{∗}, u ≡L̂ u′ provided for all w_{1}, w_{2} ∈ Σ^{∗}, w_{1}uw_{2} ∈ L̂ iff w_{1}u′w_{2} ∈ L̂.

By the Myhill-Nerode theorem, if L̂ is recognizable, ≡L̂ is of finite index [HU].

Now, consider the relation ≡_{L} defined by the language L we are looking at. We can associate with each word u a function f_{u} : S → S, where S is the set of states of 𝔅, such that f_{u}(s) = s′ iff δ(s, u) = s′. So, f_{u} is a representation of the word u as a “state transformer”. The following observations follow from the fact that 𝔅 is the minimal DFA recognizing L.

Proposition 8 Let u, w ∈ Σ^{∗}. Then:

(i) f_{u} = f_{w} iff u ≡_{L} w.

(ii) δ(s_{0}, u) = f_{u}(s_{0}).

(iii) f_{uw} = f_{w} ∘ f_{u}, where ∘ denotes function composition.

Clearly the function f_{w} : S → S corresponding to a word w has a bounded representation. So, if we could compute the function f_{u} corresponding to the input u, we would be able to determine whether δ(s_{0}, u) ∈ S_{F} —by part (ii) of the preceding proposition, δ(s_{0}, u) = f_{u}(s_{0}).

However, we still have the original problem arising from the distributed nature of 𝔄— each process p ∈ 𝒫 will only see a part of u. Even if p were to maintain the entire p-view of ℰ_{u}, the only information that we could reasonably hope to extract from the combined view of all the processes is the structure (ℰ_{u}, ⊑^{∗}). From this labelled partial order, we cannot always recover u uniquely—in general, we can only reconstruct a word u′ which is ∼-equivalent to u.

For the same reason, if we attempt to piece together f_{u} from the information available with each process about u, we can at best hope to recover f_{u′} for some u′ ∼ u.

Fortunately, this is not a bottleneck. From the definition of a trace language, it follows that all words that are ∼-equivalent are also ≡_{L}-equivalent.

Proposition 9 Let L̂ be a trace language over a concurrent alphabet (Σ, I). For any u, u′ ∈ Σ^{∗}, if u ∼ u′ then u ≡L̂ u′.

Proof Suppose u ∼ u′ but u ≢L̂ u′. Then, without loss of generality, we can find words w_{1} and w_{2} such that w_{1}uw_{2} ∈ L̂ but w_{1}u′w_{2} ∉ L̂. Since w_{1}uw_{2} ∼ w_{1}u′w_{2}, this contradicts the assumption that L̂ is ∼-consistent. □

So, to determine whether δ(s_{0}, u) ∈ S_{F}, it is sufficient to compute the function f_{u′} corresponding to some word u′ ∼ u. By Propositions 8 and 9, δ(s_{0}, u) = f_{u′}(s_{0}).

This, then, is our new goal: for any input word u, we want to compute in 𝔄 the function f_{u′} : S → S for some representative u′ of the trace [u]. This still involves finding a scheme to combine the partial views of processes in a sensible way.

We begin by formally defining a partial view of a word. Let u : [1..n] → Σ and X ⊆ ℰ_{u} where X − {0} = {(i_{1}, u(i_{1})), (i_{2}, u(i_{2})), …, (i_{k}, u(i_{k}))} and i_{1} < i_{2} < ⋯ < i_{k}. Let u[X] denote the word u(i_{1})u(i_{2}) ⋯ u(i_{k}). If X − {0} = ∅ then u[X] = ε, the empty string.

Ideals revisited So far, we have implicitly assumed that all ideals are non-empty. However, to construct the asynchronous automaton 𝔄 it will be convenient to work with the empty ideal as well. So, henceforth, whenever we encounter an ideal I, unless we explicitly say that I is non-empty we do not rule out the possibility that I = ∅.

Clearly, if I = ∅, the notions max_{p}(I), primary_{p}(I), secondary_{p}(I) and tertiary_{p}(I) are not defined and we shall apply these operators only to non-empty ideals.

We also adopt a convention regarding P -views of an ideal. Recall that for P ⊆ 𝒫, the P -view I|_{P} of a non-empty ideal I is the set of events ⋃_{p∈P} max_{p}(I)↓. If P = ∅, we shall define I|_{P} = ∅.

We begin with a basic result about the equivalence relation ∼, which we state without proof (see, for instance, [AR]). We need some notation: For w ∈ Σ^{∗} and A ⊆ Σ, let w↓_{A} denote the word formed by deleting all letters from w except those in A.

Proposition 10 Let w, w′ ∈ Σ^{∗}. Then w ∼ w′ iff for each pair of dependent letters (a, b) ∈ 𝒟, w↓_{{a,b}}= w′↓_{{a,b}}.

We apply this result to derive the following fact, which is crucial in our construction of 𝔄.

Lemma 11 Let u be a word and I, J ⊆ ℰ_{u} be ideals such that I ⊆ J. Then u[J] ∼ u[I]u[J − I].

Proof We shall show that u[J]↓_{{a,b}}= (u[I]u[J − I])↓_{{a,b}} for each pair of dependent letters (a, b) ∈ 𝒟. The result then follows from Proposition 10.

Suppose (a, b) ∈ 𝒟 and u[J] ↓_{{a,b}}≠ (u[I]u[J − I]) ↓_{{a,b}}. Then there must be an occurrence of a and an occurrence of b in u[J] ↓_{{a,b}} which have been transposed in (u[I]u[J − I])↓_{{a,b}}. Let e_{a} = (i, a) and e_{b} = (j, b) be the events from J corresponding to these occurrences of a and b in u. Without loss of generality, we assume that i < j.

It must be the case that e_{a} ∉ I and e_{b} ∈ I, since the only rearrangement we have performed is to send letters not in u[I] to the right. Since (a, b) ∉ I, we can find a process p ∈ θ(a) ∩ θ(b). But then e_{a} ◁_{p}^{∗} e_{b} and so e_{a} ⊑^{∗} e_{b}. Since I is an ideal, e_{b} ∈ I and e_{a} ∈ e_{b}↓, we must have e_{a} ∈ I as well, which is a contradiction. □

Corollary 12 Let u be a word and I_{1} ⊆ I_{2} ⊆ ⋯ ⊆ I_{k} ⊆ ℰ_{u} a sequence of nested ideals. Then u[I_{k}] ∼ u[I_{1}]u[I_{2} − I_{1}] ⋯ u[I_{k} − I_{k−1}].

Proof Applying Lemma 11 once, we get u[I_{k}] ∼ u[I_{k−1}]u[I_{k} − I_{k−1}]. We then apply the lemma to each of u[I_{k−1}], u[I_{k−2}], …, u[I_{2}] in turn to obtain the required expression. □

Let us return to our problem: We want to compute in 𝔄, on any input u, the function f_{u′} corresponding to some u′ ∼ u. We order the processes in 𝒫 so that 𝒫 = {p_{1}, p_{2}, …, p_{N}} and construct subsets {Q_{j}}_{j∈[1..N]}, where Q_{1} = {p_{1}} and for j ∈ [2..N], Q_{j} = Q_{j−1} ∪ {p_{j}}.

Let ℰ be the set of events corresponding to u. Construct ideals I_{0}, I_{1}, …, I_{N} ⊆ ℰ where I_{0} = ∅ and for j ∈ [1..N], I_{j} = I_{j−1} ∪ ℰ|_{p_{j}}. Clearly I_{j} = ℰ|_{Q_{j}} for j ∈ [1..N].

Since ℰ = ℰ|_{𝒫} = ℰ|_{Q_{N}} = I_{N} and I_{0} ⊆ I_{1} ⊆ ⋯ ⊆ I_{N}, we can write down the following expression based on Corollary 12.

u = u[I_{N}] ∼ u[I_{0}]u[I_{1} − I_{0}] ⋯ u[I_{N} − I_{N−1}]

For j ∈ [2..N], I_{j} − I_{j−1} = ℰ|_{Q_{j}} − ℰ|_{Q_{j−1}} is the same as ℰ|_{p_{j}} − ℰ|_{Q_{j−1}}. So, we can rewrite our earlier expression in a more useful form as:

u = u[ℰ|_{Q_{N}}] ∼ u[∅]u[ℰ|_{p_{1}} − ∅]u[ℰ|_{p_{2}} − ℰ|_{Q_{1}}] ⋯ u[ℰ|_{p_{N}} − ℰ|_{Q_{N−1}}] (♢)

The word u[ℰ|_{p_{j}} − ℰ|_{Q_{j−1}}] is the portion of u that p_{j} has seen but which the processes in Q_{j−1} have not seen. This is a special case of what we call a residue.

Residues Let u ∈ Σ^{∗} be a word, I ⊆ ℰ_{u} an ideal and p ∈ 𝒫 a process. ℛ(u, p, I) denotes the word u[ℰ_{u}|_{p} − I] and is called the residue of u at p with respect to I.

For ideals X and Y, recall that X − Y = X − (X ∩ Y), where X ∩ Y is also an ideal. So any residue ℛ(u, p, I) can equivalently be written as ℛ(u, p, ℰ_{u}|_{p} ∩ I). We will often make use of this fact.

Using our new notation, we can write u[ℰ|_{p_{j}} − ℰ|_{Q_{j−1}}] as ℛ(u, p_{j}, ℰ|_{Q_{j−1}}). Let us give a special name to residues of this form: ℛ(u, p, I) is a process residue if ℛ(u, p, I) = ℛ(u, p, ℰ|_{P}) for some P ⊆ 𝒫. We say that ℛ(u, p, ℰ|_{P}) is the P -residue of u at p.

Notice that ℛ(u, p, ∅) is also a process residue, corresponding to the empty set of processes (by our convention that ℰ|_{∅} = ∅.) Further, ℛ(u, p, ∅) = u[ℰ|_{p}], the partial word corresponding to the p-view of ℰ.

Example: Consider our old example—the word bacabba depicted in Figure 1. Let I = {0, e_{1}, e_{2}, e_{3}}. ℰ|_{s} − I = {e_{5}, e_{6}}, so ℛ(u, s, I) = bb. Moreover, ℛ(u, s, I) = ℛ(u, s, ℰ|_{p}), so it is the p-residue of u at s.

Suppose that along every input word u, each process p maintains all its P -residues ℛ(u, p, ℰ|_{P}), P ⊆ 𝒫, as functions from S to S. As we remarked earlier, each of these functions can be represented in a finite, bounded manner. Since each process needs to keep track of only 2^{N} P -residues, where N = |𝒫|, all these functions can be incorporated into the local state of the process.

Going back to the expression (♢), we can compute the function f_{u[ℰ|_{p_{N}} −∅]} corresponding to u[ℰ|_{p_{N}} − ∅] by composing the functions corresponding to the residues ℛ(u, p_{1}, ∅), ℛ(u, p_{2}, ℰ|_{Q_{1}}), …, ℛ(u, p_{N}, ℰ|_{Q_{N−1}}) (Proposition 8 (iii)). Notice that u[ℰ|_{p_{N}} − ∅] = u. So, by Proposition 8 (ii), we can then compute the state δ(s_{0}, u) by applying the function f_{u[ℰ|_{p_{N}} −ℰ|_{p_{1}}]} to s_{0}.

Thus, our automaton 𝔄 will accept u if δ(s_{0}, u) as computed using the process residues corresponding to the expression (♢) lies in S_{F}.

(Recall that the accepting states of 𝔄 are specified as global states. So, at the end of the word u, we are permitted to observe “externally”, as it were, the states of all the processes in 𝔄 before deciding whether to accept u.)

The only hitch now is with computing process residues “on line”, as 𝔄 reads u. The problem is the following: Let p ∈ 𝒫 and P ⊆ 𝒫. If we extend u to ua where p ∉ θ(a), it could well happen that ℰ_{ua}|_{p} − ℰ_{ua}|_{P} ≠ ℰ|_{p} − ℰ|_{P}, even though ℰ|_{p} = ℰ_{ua}|_{p}.

Example: Consider the word bacabba shown in Figure 1. After the subword bac, the p-residue at s is bc, corresponding to {e_{1}, e_{3}}. However, when this word is extended to baca, the p-residue at s becomes ε, though s does not participate in the final a.

So, process residues at p could change without p being aware of it. This means that we cannot hope to directly maintain and update process residues locally as 𝔄 reads u. To remedy this we need the following observation.

Lemma 13 For any non-empty ideal I, and p, q ∈ 𝒫, I|_{p} ∩ I|_{q} is generated by the set primary_{p}(I) ∩ primary_{q}(I).

Proof We only deal with the interesting case, where max_{p}(I) and max_{q}(I) are incomparable with respect to ⊑^{∗}. Let e be a maximal event in the ideal I|_{p} ∩ I|_{q}. e has no successors in I|_{p} ∩ I|_{q} but e ⊑^{∗} max_{p}(I) and e ⊑^{∗} max_{q}(I). So, for some r, s ∈ 𝒫, e must be an r-sentry for p with respect to q as well as an s-sentry for q with respect to p. By Lemma 1, e = latest_{p→r}(I) = latest_{q→s}(I) and so e ∈ primary_{p}(I) ∩ primary_{q}(I).

Therefore, the set of maximal events in I|_{p}∩I|_{q} is contained in primary_{p}(I)∩primary_{q}(I), whence I|_{p} ∩ I|_{q} ⊆ (primary_{p}(I) ∩ primary_{q}(I))↓.

On the other hand, let e ∈ primary_{p}(I) ∩ primary_{q}(I). Then e ∈ I|_{p} ∩ I|_{q} and so e↓⊆ I|_{p} ∩ I|_{q}, since I|_{p} ∩ I|_{q} is an ideal. So (primary_{p}(I) ∩ primary_{q}(I))↓⊆ I|_{p} ∩ I|_{q}.

The degenerate case where max_{p}(I) and max_{q}(I) are ordered with respect to ⊑^{∗} is straightforward and we omit the argument. □

Let us call ℛ(u, p, I) a primary residue if I is generated by a subset E of primary_{p}(ℰ). Clearly, for p, q ∈ 𝒫, ℛ(u, p, ℰ|_{q}), can be rewritten as ℛ(u, p, ℰ|_{p} ∩ℰ|_{q}). So, by the previous result the q-residue ℛ(u, p, ℰ|_{q}) is a primary residue ℛ(u, p, E↓) for some E ⊆ primary_{p}(ℰ). Further, p can effectively determine the set E given the primary information of both p and q. In fact, it will turn out that all process residues can be effectively described in terms of primary residues.

Example: In the word u = bacabba shown in Figure 1, ℛ(u, s, ℰ|_{p}) corresponds to the primary residue ℛ(u, s, {latest_{s→q}(ℰ)}↓).

So, our strategy will be to maintain primary residues rather than process residues for each process p. The useful property we exploit is that the primary residues at p change only when p participates in an event.

(Notice that this does not contradict our earlier observation that process residues at p can change independent of p. Even if a synchronization not involving p happens to modify the P -residue at p, the new P -residue remains a primary residue of p, albeit for a different subset of p’s primary events.)

Further, we show that when p participates in an event, it can recompute its primary residues using just the information it receives during the synchronization. At the end of the word u, the expression (♢) written in terms of process residues, which is used to compute δ(s_{0}, u), can be effectively rewritten in terms of primary residues. These residues will be available with each process in 𝒫, thereby enabling us to calculate δ(s_{0}, u).

We first spell out some consequences of Lemma 13.

Corollary 14 Let u ∈ Σ^{∗} and p ∈ 𝒫.

(i) For ideals I, J ⊆ ℰ, let ℛ(u, p, I) and ℛ(u, p, J) be primary residues such that ℛ(u, p, I) = ℛ(u, p, E_{I} ↓) and ℛ(u, p, J) = ℛ(u, p, E_{J} ↓) for E_{I}, E_{J} ⊆ primary_{p}(ℰ). Then ℛ(u, p, I ∪J) is also a primary residue and ℛ(u, p, I ∪J) = ℛ(u, p, (E_{I} ∪E_{J})↓).

(ii) Let Q ⊆ 𝒫. Then ℛ(u, p, ℰ|_{Q}) is a primary residue ℛ(u, p, E ↓) for p. Further, p can effectively compute the set E ⊆ primary_{p}(ℰ) from the information in primary_{{p}∪Q}(ℰ).

(iii) Let q, r ∈ 𝒫 such that latest_{p→r}(ℰ) ⊑^{∗} latest_{q→r}(ℰ). Then ℛ(u, p, (ℰ|_{q})|_{r}) is a primary residue ℛ(u, p, E↓) for p. Further, p can effectively compute the set E ⊆ primary_{p}(ℰ) from the information in primary_{p}(ℰ) and secondary_{q}(ℰ).

Proof

(i) We can rewrite ℛ(u, p, I ∪ J) as ℛ(u, p, ℰ|_{p} ∩ (I ∪ J)). But ℰ|_{p} ∩ (I ∪ J) = (ℰ|_{p} ∩ I) ∪ (ℰ|_{p} ∩J). Since ℛ(u, p, I) = ℛ(u, p, ℰ|_{p} ∩I), we know that ℰ|_{p} ∩I is generated by E_{I}. Similarly, ℰ|_{p} ∩J is generated by E_{J}. So (E_{I} ∪E_{j})↓= (ℰ|_{p} ∩I)∪(ℰ|_{p} ∩J). Therefore E_{I} ∪E_{J} generates ℰ|_{p} ∩(I ∪J) and so the residue ℛ(u, p, I ∪J) = ℛ(u, p, (E_{I} ∪E_{J})↓).

(ii) Let Q = {q_{1}, q_{2}, …, q_{k}}. We can rewrite ℛ(u, p, ℰ|_{Q}) as ℛ(u, p, ⋃_{i∈[1..k]} ℰ|_{q_{i}}). From Lemma 13 it follows that for each i ∈ [1..k], p can compute a set E_{i} ⊆ primary_{p}(ℰ) from the information in primary_{{p,q_{i}}}(ℰ) such that ℛ(u, p, ℰ|_{q_{i}}) = ℛ(u, p, E_{i}↓). From part (i) of this Corollary, it then follows that ℛ(u, p, ℰ|_{Q}) = ℛ(u, p, ⋃_{i∈[1..k]} ℰ|_{q_{i}}) = ℛ(u, p, E↓) where E = ⋃_{i∈[1..k]} E_{i}.

(iii) Let J = ℰ|_{p} ∪ (ℰ|_{q})|_{r}. J is an ideal. By the construction of J, max_{p}(J) = max_{p}(ℰ). From the assumption that latest_{p→r}(ℰ) ⊑^{∗} latest_{q→r}(ℰ), we have max_{r}(J) = latest_{q→r}(ℰ). So, J|_{p} = ℰ|_{p} and J|_{r} = (ℰ|_{q})|_{r}. Since ℛ(u, p, (ℰ|_{q})|_{r}) = ℛ(u, p, ℰ|_{p} ∩ (ℰ|_{q})|_{r}) = ℛ(u, p, J|_{p} ∩ J|_{r}), it suffices to find a subset E ⊆ primary_{p}(ℰ) which generates J|_{p} ∩ J|_{r}.

By Lemma 13, J|_{p}∩J|_{r} is generated by primary_{p}(J)∩primary_{r}(J). Since max_{p}(J) = max_{p}(ℰ), primary_{p}(J) = primary_{p}(ℰ).

On the other hand, primary_{r}(J) = primary_{r}(latest_{q→r}(ℰ)↓). By definition, this is the set {latest_{q→r→s}(ℰ)}_{s∈𝒫} .

So the set E ⊆ primary_{p}(ℰ) generating J|_{p} ∩ J|_{r} is given by E = primary_{p}(J) ∩ primary_{r}(J) = primary_{p}(ℰ) ∩ {latest_{q→r→s}(ℰ)}_{s∈𝒫} and can be computed from primary_{p}(ℰ) and secondary_{q}(ℰ).

□

Part (ii) of the preceding Corollary makes explicit our claim that every process residue ℛ(u, p, ℰ|_{Q}), Q ⊆ 𝒫, can be effectively rewritten as a primary residue ℛ(u, p, E↓), E ⊆ primary_{p}(ℰ), based on the information available in primary_{p∪{Q}}(ℰ). In case Q = ∅, ℛ(u, p, ℰ|_{Q}) is given by the primary residue corresponding to ∅ ⊆ primary_{p}(ℰ).

Computing primary residues locally

We now describe how, while reading a word u, each process p maintains the functions f_{w} for each primary residue w of u at p.

Initially, at the empty word u = ε, every primary residue from {ℛ(u, p, E↓)}_{p∈𝒫,E⊆primary_{p}(ℰ_{u})} is just the empty word ε. So, all primary residues are represented by the identity function Id : S → S.

Let u ∈ Σ^{∗} and a ∈ Σ. Assume inductively that every p ∈ 𝒫 has computed at the end of u the function f_{w} for each primary residue w ∈ {ℛ(u, p, E↓)}_{E⊆primary_{p}(ℰ_{u})} . We want to compute for each p the corresponding functions after the word ua.

For processes not involved in a, these values do not change.

Proposition 15 If p ∉ θ(a) then every subset E ⊆ primary_{p}(ℰ_{ua}) is also a subset of primary_{p}(ℰ_{u}) and the primary residue ℛ(ua, p, E ↓) is the same as the primary residue ℛ(u, p, E↓).

Proof This follows immediately from the fact that ℰ_{ua}|_{p} = ℰ_{u}|_{p} and primary_{p}(ℰ_{ua}) = primary_{p}(ℰ_{u}). □

So, the interesting case is when p participates in a. We show how to calculate all the new primary residues for p using the information available with the processes in θ(a) after u.

Lemma 16 Let p ∈ θ(a) and E ⊆ primary_{p}(ℰ_{ua}). The function f_{w} corresponding to the primary residue w = ℛ(ua, p, E↓) can be computed from the primary residues at u of the processes in θ(a) using the information in primary_{θ(a)}(ℰ_{u}) and secondary_{θ(a)}(ℰ_{u}).

Proof Let e_{a} be the event corresponding to the new letter a—i.e., ℰ_{ua} − ℰ_{u} = {e_{a}}. There are two cases to consider.

Case 1: (e_{a} ∈ E) Since E↓= e_{a}↓= ℰ_{ua}|_{p}, the residue ℛ(ua, p, E↓) = ℛ(ua, p, e_{a}↓) is the empty word ε. So the corresponding function is just the identity function Id : S → S.

Case 2: (e_{a} ∉ E) We want to compute the function f_{w} corresponding to the word w = ua[ℰ_{ua}|_{p} − E↓]. By Lemma 11, we know that

ua[ℰ_{ua}|_{p}] ∼ ua[E↓]ua[ℰ_{ua}|_{p} − E↓].  (1)

But ua[ℰ_{ua}|_{p}] = u[ℰ_{u}|_{θ(a)}]a and so we have

ua[ℰ_{ua}|_{p}] = u[ℰ_{u}|_{θ(a)}]a ∼ u[E↓]u[ℰ_{u}|_{θ(a)} − E↓]a.  (2)

Since e_{a} ∉ E ↓, ua[E ↓] = u[E ↓]. Thus, cancelling u[E ↓] from the right hand sides of (1) and (2) above, we have u[ℰ_{u}|_{θ(a)} − E ↓]a ∼ ua[ℰ_{ua}|_{p} − E ↓]. So, by Propositions 8 and 9, to compute the function f_{w}, it suffices to compute the function corresponding to u[ℰ_{u}|_{θ(a)} − E↓]a.

Let θ(a) = {p_{1}, p_{2}, …, p_{k}}, where p = p_{1}. Construct sets of processes {Q_{i}}_{i∈[1..k]} such that Q_{1} = {p_{1}} and Q_{i} = Q_{i−1} ∪ {q_{i}} for i ∈ [2..k].

Construct ideals {I_{j}}_{j∈[0..k]} as follows: I_{0} = E↓ and for j ∈ [1..k], I_{j} = I_{j−1} ∪ ℰ_{u}|_{p_{j}}. Clearly, I_{0} ⊆ I_{1} ⊆ ⋯ ⊆ I_{k} ⊆ ℰ_{u}.

By Corollary 12, u[I_{k}] ∼ u[I_{0}]u[I_{1} − I_{0}] ⋯ u[I_{k} − I_{k−1}]. Since u[I_{k}] = u[ℰ_{u}|_{θ(a)}] and u[I_{0}] = u[E↓], from (2) above it follows that the word u[ℰ_{u}|_{θ(a)} − E↓]a which we seek is ∼-equivalent to the word u[I_{1} − I_{0}] ⋯ u[I_{k} − I_{k−1}]a.

Claim: For each j ∈ [1..k], u[I_{j} − I_{j−1}] is a primary residue ℛ(u, p_{j}, F_{j}↓), where F_{j} ⊆ primary_{p_{j}}(ℰ_{u}). Further, p_{j} can determine F_{j} from the information in primary_{p_{j}}(ℰ_{u}) and secondary_{θ(a)}(ℰ_{u}).

Assuming the claim, for each word w_{j} = u[I_{j} − I_{j−1}], we can find the corresponding function f_{w_{j}} : S → S among the primary residues stored by p_{j} after u. The composite function f_{a} ∘ f_{w_{k}} ∘ f_{w_{k−1}} ∘ ⋯ ∘ f_{w_{1}} then gives us the function corresponding to the word u[I_{1} − I_{0}] ⋯ u[I_{k} − I_{k−1}]a, which is what we need.

Proof of Claim: The way that primary events are updated guarantees that each event e ∈ E was a primary event in ℰ_{u}, before a occurred, for one of the processes in θ(a); i.e., E ⊆ primary_{θ(a)}(ℰ_{u}). For i ∈ [1..k], let E_{i} = E ∩ primary_{p_{i}}(ℰ_{u}).

First consider u[I_{1} − I_{0}].

Let E′ = E − E_{1}. I_{1} − I_{0} is the same as ℰ_{u}|_{p_{1}} − (E_{1} ∪ E′)↓, which is the same as ℰ_{u}|_{p_{1}} − (E_{1}↓ ∪ E′↓). We want to compute u[I_{1} − I_{0}] = ℛ(u, p_{1}, E_{1}↓ ∪ E′↓).

Each event e ∈ E′ is a primary event of the form latest_{p_{1}→q_{e}}(ℰ_{ua}) for some q_{e} ∈ 𝒫. Further, for some i ∈ [2..k], e was also the primary event latest_{p_{i}→q_{e}}(ℰ_{u}) before e_{a} occurred. Since p_{1} has inherited this information from p_{i}, it must have been the case that latest_{p_{1}→q_{e}}(ℰ_{u}) ⊑^{∗} latest_{p_{i}→q_{e}}(ℰ_{u}). So, by part (iii) of Corollary 14, the residue ℛ(u, p_{1}, e↓) = ℛ(u, p_{1}, (ℰ_{u}|_{p_{i}})|_{q_{e}}) corresponds to a primary residue ℛ(u, p_{1}, G_{e}↓), where p_{1} can determine G_{e} ⊆ primary_{p_{1}}(ℰ_{u}) from primary_{p_{1}}(ℰ_{u}) and secondary_{p_{i}}(ℰ_{u}).

So, by part (i) of Corollary 14, ℛ(u, p_{1}, E′↓) = ℛ(u, p_{1}, ⋃_{e∈E′} e↓) is a primary residue ℛ(u, p_{1}, G_{1}↓) where G_{1} = ⋃_{e∈E′} G_{e}.

ℛ(u, p_{1}, E_{1} ↓) is a primary residue since E_{1} ⊆ primary_{p}(ℰ_{u}). Applying part (i) of Corollary 14 again, ℛ(u, p_{1}, (E_{1}↓ ∪ E′↓)) corresponds to the primary residue ℛ(u, p_{1}, F_{1}↓), where F_{1} = E_{1} ∪ G_{1}.

Now consider u[I_{j} − I_{j−1}] for j ∈ [2..k].

I_{j} − I_{j−1} is the same as ℰ_{u}|_{p_{j}} − (E↓ ∪ ℰ_{u}|_{Q_{j−1}}) so we want to compute the residue ℛ(u, p_{j}, E↓ ∪ ℰ_{u}|_{Q_{j−1}}).

By a similar argument to the one for u[I_{1}−I_{0}], p_{j} can compute a set G_{j} ⊆ primary_{p_{j}}(ℰ_{u}) such that ℛ(u, p_{j}, E↓) corresponds to the primary residue ℛ(u, p_{j}, G_{j}↓).

By part (ii) of Corollary 14, p_{j} can compute from primary_{Q_{j}}(ℰ_{u}) a set H_{j} ⊆ primary_{p_{j}}(ℰ_{u}) such that ℛ(u, p_{j}, ℰ_{u}|_{Q_{j−1}}) corresponds to the primary residue ℛ(u, q, H_{j}↓).

We now use part (i) of Corollary 14 to establish that ℛ(u, p_{j}, E↓ ∪ ℰ_{u}|_{Q_{j−1}}) corresponds to the primary residue ℛ(u, p_{j}, F_{j}↓), where F_{j} = G_{j} ∪ H_{j}.

□

An asynchronous automaton for L

Our analysis of process residues and primary residues immediately yields a deterministic asynchronous automaton 𝔄 = ({V_{p}}_{p∈𝒫} , {→_{a}}_{a∈Σ}, 𝒱_{0}, 𝒱_{F}) which accepts the language L. Recall that 𝔅 = (S, Σ, δ, s_{0}, S_{F}) is the minimal DFA recognizing L.

For p ∈ 𝒫, each local state of p will consist of the following:

• Primary, secondary and tertiary information for p, as stored by the gossip automaton.

• For each subset E of the primary events of p, a function f_{E} : S → S recording the (syntactic congruence class of the) primary residue ℛ(u, p, E ↓) at the end of any word u.

At the initial state, for each process p, all the primary, secondary and tertiary information of p points to the initial event 0. For each subset E of primary events, the function f_{E} is the identity function Id : S → S.

The transition functions →_{a} modify the local states of θ(a) as follows:

• Primary, secondary and tertiary information is updated as in the gossip automaton.

• The functions corresponding to primary residues are updated as described in the proof of Lemma 16.

Other than comparing primary information, the only operation used in updating the primary residues at p (Lemma 16) is function composition. This is easily achieved using the data available in the states of the processes which synchronized.

The final states of 𝔄 are those where the value jointly computed from the primary residues in 𝒫 yields a state in S_{F}. More precisely, order the processes as 𝒫 = {p_{1}, p_{2}, …, p_{N}}. Construct subsets of processes {Q_{i}}_{i∈[1..N]} such that Q_{1} = {p_{1}} and for i ∈ [2..N], Q_{i} = Q_{i−1} ∪ {p_{i}}.

Let v⃗ = {v_{1}, v_{2}, …, v_{N}} be a global state of 𝔄 such that 𝔄 is in v⃗ after reading an input word u.

By Corollary 14 (ii), for each i ∈ [2..N], we can compute from {v_{1}, v_{2}, …, v_{i}} a subset E_{i} of the primary information of p_{i} such that the Q_{i−1}-residue of p_{i} is also the primary residue of p_{i} with respect to E_{i}. Let f_{i} denote this primary residue. In addition, from the state v_{1}, we can extract the function f_{1} corresponding to the primary residue ℛ(u, p, ∅).

From the expression (♢), we know that the composite function f_{N} ∘ f_{N−1} ∘ ⋯ ∘ f_{1} is exactly the function f_{u} associated with the input word u leading to the global state v⃗. So, we put v⃗ in the set of accepting states 𝒱_{F} of 𝔄 iff f_{N} ∘ f_{N−1} ∘ ⋯ ∘ f_{1}(s_{0}) ∈ S_{F}.

Notice that it does not matter how we order the states in v⃗ when we try to decide whether v⃗ ∈ 𝒱_{F}. We keep track of residues in all processes in a symmetric fashion, and the expression (♢) holds regardless of how we order 𝒫. So, if v⃗ is a valid (i.e., reachable) global state, the composite function f_{N} ∘f_{N−1} ∘⋯∘f_{1} which we compute from v⃗ is always the same, no matter how we order 𝒫.

Of course, we have the same minor complication here which we came across when defining the local functions g_{a} which computed the latest gossip function: We have not bothered to verify whether v⃗ is a “meaningful” global state in 𝔄. However, as we argued then, those states which are not “meaningful” are also unreachable, so it does not matter if we accidentally add such states to 𝒱_{F}.

From our analysis of residues in this section, we have the following result.

Theorem 17 The language accepted by 𝔄 is exactly L.

The size of 𝔄

Proposition 18 Let M = |S| and N = |𝒫|, where S is the set of states of 𝔅, the minimal DFA recognizing L, and 𝒫 is the set of processes in the corresponding asynchronous automaton 𝔄 which we construct to accept L. Then, the number of local states of each process p ∈ 𝒫 is at most 2^{O(2^{N} M log M)}.

Proof We estimate the number of bits required to store a local state of a process p.

From Lemma 7, we know that the primary, secondary and tertiary information that we require to keep track of the latest gossip can be stored in O(N^{3} log N) bits.

The new information we store in each local state of p is the collection of primary residues. Each residue, which is a function from S to S, can be written down as an array with M entries, each of log M bits; i.e., M log M bits in all. Each primary residue corresponds to a subset of primary events. There are N primary events and so, in general, we need to store 2^{N} residues. Thus, all the residues can be stored using 2^{N}M log M bits.

So, the entire state can be written down using O(2^{N}M log M) bits, whence the number of distinct local states of p is bounded by 2^{O(2^{N} M log M)}. □

8 Comparison with Zielonka’s construction

Let us compare our construction of 𝔄 with Zielonka’s original proof [Zie1]. Zielonka starts by defining an equivalence relation ≈ on words (actually traces) which we can describe in our terminology as follows.

For sets X and Σ, a Σ-labelled graph over X is a pair (G, λ) where G(X, E) is a directed graph whose vertex set is X and λ : X → Σ is a labelling function.

Let 𝒫 be the set of processes in the asynchronous automaton we want to construct and Σ′ = Σ ∪ {†}, for some † ∉ Σ. With each word u ∈ Σ^{∗}, associate a Σ′-labelled graph Last(u) over 𝒫 × 𝒫 where Last(u) = (G(𝒫 × 𝒫, E_{u}), λ_{u}) is given as follows:

• For (p_{1}, q_{1}), (p_{2}, q_{2}) ∈ 𝒫×𝒫, (p_{1}, q_{1}) E_{u} (p_{2}, q_{2}) iff latest_{p_{1}→q_{1}}(ℰ_{u}) ⊑^{∗} latest_{p_{2}→q_{2}}(ℰ_{u}).

• For (p, q) ∈ 𝒫 × 𝒫, let e ∈ ℰ_{u} be the event corresponding to latest_{p→q}(ℰ_{u}). If e is the initial event 0, then λ_{u}((p, q)) = †. Otherwise e must be of the form (i, a), in which case λ_{u}((p, q)) = a.

So, the graph Last(u) of [Zie1] records the structure of the primary information after u. This is the first notion needed to specify the equivalence relation ≈.

The second ingredient present is a version of residues. For each word u and each subset P of processes, the suffix of u with respect to P is the word 𝒮_{P} (u) = u[ℰ_{u} − ℰ_{u}|_{P}].

We can now define ≈. For all u, u′ ∈ Σ^{∗}, u ≈ u′ iff the following conditions hold:

• Last(u) = Last(u′).

• For all P ⊆ 𝒫, 𝒮_{P} (u) ≡_{L} 𝒮_{P} (u′). (Recall that ≡_{L} is the syntactic congruence defined by the language L.)

It is easy to see that if u ∼ u′ then Last(u) = Last(u′). Similarly, if u ∼ u′ then for every P ⊆ 𝒫, 𝒮_{P} (u) ∼ 𝒮_{P} (u′) and so 𝒮_{P} (u) ≡_{L} 𝒮_{P} (u′). Thus, if u ∼ u′ then u ≈ u′ and so it does not matter that we have defined ≈ in terms of words rather than in terms of traces as Zielonka originally did. Clearly, ≈ is of finite index for any recognizable trace language L.

Let ⟨u⟩ denote the equivalence class of u with respect to ≈. In Zielonka’s construction, each process p keeps track of ⟨u[ℰ_{u}|_{p}]⟩, the equivalence class of the p-view of u. Thus, after reading u, the automaton is in the global state (⟨u[ℰ_{u}|_{p_{1}}]⟩, ⟨u[ℰ_{u}|_{p_{2}}]⟩, …, ⟨u[ℰ_{u}|_{p_{N}}]⟩), where 𝒫 = {p_{1}, p_{2}, …, p_{N}}. A global state of this form is an accepting state iff u ∈ L.

In general, the graph Last(u) as well as the set of suffixes {𝒮_{P} (u)}_{P ⊆𝒫} describe global properties of the word u. However, when we restrict our attention to the p-view u[ℰ_{u}|_{p}] of a process p ∈ 𝒫, they correspond to local notions which we have already encountered. The graph Last(u[ℰ_{u}|_{p}]) describes the structure of the secondary information of p after u. And each suffix 𝒮_{P} (u[ℰ_{u}|_{p}]), P ⊆ 𝒫, corresponds to the primary residue of u at p with respect to E = {latest_{p→q}(ℰ_{u})}_{q∈P}.

From this, it is clear that our construction is essentially a “disguised” version of Zielonka’s original construction. What have we achieved by adopting this disguise?

The main benefit is that our construction is significantly more transparent than Zielonka’s (which is generally acknowledged to be difficult to assimilate [CMZ, Pig].)

First of all, we clearly distinguish between process residues and primary residues. Process residues are used to compute the function f_{u} corresponding to the ≡_{L}-congruence class of a word u via the expression (♢) (page 19). However, since these residues cannot be maintained locally, each process keeps track of primary residues instead. Using primary information, process residues can be effectively rewritten in terms of primary residues and so it suffices to keep track of primary information and primary residues locally. This, essentially, is the intuition behind Zielonka’s construction and the reason the original construction is rather opaque is because these connections are not made explicit in [Zie1].

The second difference is that the local transition functions are defined much more “naturally” in our setup. We explicitly maintain primary information and information about residues in the local states of processes. Thus, we can define the local transition functions as “procedures” or “algorithms” which manipulate the information stored in the local states in a concrete way. This makes it easier to understand, overall, what the asynchronous automaton is computing. In addition, it also enables us to effectively describe the automaton much more concisely than if the transition functions are defined in terms of the equivalence classes of ≈, as in [Zie1]. In Zielonka’s construction, there is no structure to the names given to these equivalence classes. So, for specifying the transition functions, there is no alternative but to exhaustively list out all the entries in the form of an enormous table.

Let us now focus on the connection between the information maintained by the gossip automaton and the information present in the graphs {Last(u[ℰ_{u}|_{p}])}_{p∈𝒫} . It is clear that Zielonka’s construction provides us with an effective procedure for locally updating these graphs whenever a synchronization occurs. However, this update mechanism is “uninformative” in the following sense: When a set of processes c ⊆ 𝒫 synchronizes after u, we cannot directly extract the values of the functions {best_{c}(u, q)}_{q∈𝒫} (page 6) which we are interested in computing via the gossip automaton. (This is not to say that this information cannot be computed indirectly from the way these graphs are updated in [Zie1]—all that we claim is that the procedure, as it stands, does not compute the functions we seek.)

Even if Zielonka’s update procedure were modified to supply the values of {best_{c}(u, q)}_{q∈𝒫} when c ⊆ 𝒫 meets after u, the resulting automaton would be much larger, in real terms, than the gossip automaton. The first point to note is that the number of states generated by Zielonka’s construction would be slightly larger than the number of states in the gossip automaton. Let N = |𝒫| and K = |Σ|. Then there are 2^{O(N^{4}+N^{2} log K)} distinct Σ′-labelled graphs over 𝒫 × 𝒫 and hence at least the same number of possible local states in the hypothetical gossip automaton extracted from Zielonka’s construction. Compare this with the 2^{O(N^{3} log N)} states of our automaton.

More crucially, we again observe that the local transition functions of our automaton are simple procedures manipulating concrete information stored in the local states of processes. Thus our gossip automaton can be described in space polynomial in N. On the other hand, since the transition functions in Zielonka’s construction can only be described using a table spanning all possible choices from an (exponential) number of equivalence classes, we need space exponential in N to fully specify the corresponding automaton arising from Zielonka’s construction.

9 Discussion

We now discuss the connections between our results and other work in related areas. First, we would like to point out that both “gossiping” and “bounded time-stamps” have been studied in the literature, but in contexts very different from ours.

Studies of “gossiping” in networks have traditionally focussed on efficiently disseminating a fixed piece of information (or gossip) from one node to all other nodes in a network [HHL]. The main aim is to find an optimal sequence of communications to distribute data for a given network topology.

Israeli and Li [IL] introduced the notion of “bounded time-stamps” and argued that these were fundamental in solving many problems in distributed systems—notably that of creating what are called “atomic registers”[LV]. However, both their work and that of others in the area [DS, CS] is based on a shared-memory model, which is quite different in spirit from the asynchronous automaton model. Thus, the intuition underlying their notion of time-stamping is quite different from ours.

Though our algorithm can be implemented as an asynchronous automaton, it correctly computes the latest gossip function locally for any input word. In other words, the set of communication sequences generated by the underlying system need not be regular. Our algorithm will also work on sequences generated, for instance, by N communicating Turing machines.

From this point of view, the construction of the gossip automaton establishes a nonobvious property for all synchronous systems. Suppose an agent p_{1} has a private variable X which no other agent can modify, and agents {p_{2}, p_{3}, …, p_{N}} keep track of the latest value of X that they have heard of from p_{1} (either directly or indirectly). Then, along any run of the system, bounded time-stamps suffice for determining which of {p_{2}, p_{3}, …, p_{N}} have the most recent value of X. This is important, for example, for crash recovery. If the system crashes and p_{1} fails to come alive after the crash, the other agents can get together and synthesize an optimal “last-known” state of p_{1} by comparing their information about p_{1}.

Turning now to Zielonka’s theorem, as we mentioned in the Introduction, others have also come up with alternative proofs of this basic result [CMZ, Die]. However, all these new proofs are based on asynchronous cellular automata, introduced by Zielonka in [Zie2], and rely on the fact that asynchronous cellular automata can be converted into asynchronous automata in a relatively straightforward manner.

An asynchronous cellular automaton processes input strings over a concurrent alphabet (Σ, I). Each letter a in Σ gives rise to a process p_{a}. p_{a} makes a move on input a by examining its own state together with the states of the processes {p_{b} | (a, b) ∉ I}. However, when p_{a} moves, it can only change its own state. Thus, p_{a} looks at processes in the “neighbourhood” of a in the dependence graph G_{𝒟} associated with (Σ, I). In this sense, these automata generalize conventional cellular automata.

Asynchronous cellular automata, like asynchronous automata, have a built in notion of independence—if two letters do not appear in each other’s neighbourhoods, the corresponding components can move without interfering with each other. So, they are guaranteed to recognize ∼-consistent languages. From the point of view of trace theory their structure seems more closely related to the algebraic structure of traces, thus making them more “friendly” machines to work with in proving Zielonka’s theorem [CMZ, Die]. Loosely speaking, this can be ascribed to the fact that trace theory “concentrates” more on the alphabet Σ than on the processes 𝒫 in an asynchronous automaton.

The main feature of the construction in [CMZ] is that it provides a general “recipe” for constructing asynchronous cellular automata from special types of functions called asynchronous mappings. These mappings correspond, in a sense, to our notion of locally computable functions. Asynchronous mappings provide more intuition about the behaviour of these automata than transition functions based on equivalence relations do. Thus, they help clarify the general mystery surrounding constructions like those used by Zielonka in [Zie1]. However, the “mechanical” procedure for transforming asynchronous mappings into asynchronous (cellular) automata does not provide a concise specification of the resulting automaton. The transition functions of the final automaton still have to be defined in terms of an enormous table, and, in our view, the overall description of the automaton remains unsatisfactorily large.

Like our construction, the proof given in [CMZ] factors through a bounded timestamping argument. They keep track of what they call the first and second approximations of a trace. These are directed graphs which compare the partial views generated by maximal letters in a trace.

The first approximation of a trace [u] records the causal order between the maximum a-event and the maximum b-event in ℰ_{u}, for each pair of letters a, b ∈ Σ. The second approximation of [u] records the causal order between the maximum b-event in the a-view of ℰ_{u} and the maximum c-event in the d-view of ℰ_{u} for all a, b, c, d ∈ Σ, where for a ∈ Σ, the a-view of ℰ_{u} corresponds to the principal ideal generated by the maximum a-event in ℰ_{u}.

Roughly speaking, the first approximation of a trace corresponds to keeping track of the causal order between the maximum p-events of ℰ_{u} for all p ∈ 𝒫. Similarly, the second approximation of a trace is similar to the graph Last(u) (page 26) recording the global structure of the primary information in ℰ_{u}. It is not difficult to extract the causal order between primary events (i.e., the graph Last(u)) from the first and second approximations of a trace. However, recall that Zielonka’s procedure for updating {Last(u[ℰ_{u}|_{p})}_{p∈𝒫} does not immediately yield a complete solution to the gossip problem. Similarly, locally keeping track of the first and second approximations of the a-views of a trace falls short of directly providing the values of the functions {best_{c}(u, q)}_{q∈𝒫} when a subset c ⊆ 𝒫 of processes meets after u.

Notice that approximations of a trace deal with elements in Σ, whereas primary and secondary “gossip” information is concerned only with processes and ignores the alphabet Σ altogether. There is, in general, a mismatch between the size of Σ and the number of processes in 𝒫. So, it is not surprising that the gossip automaton as defined here does not keep track of the approximations of a trace. However, our automaton can easily be modified to keep track of primary, secondary and tertiary information with respect to letters rather than processes. So, the first and second approximation of a trace can be computed in our framework. (Observe that |Σ| could be exponential in |𝒫|. As a result, computing approximations of a trace, instead of just keeping track of primary and secondary information with respect to processes, could blow up the size of the gossip automaton tremendously.)

We can go back and forth between asynchronous cellular automata and asynchronous automata through polynomial-size transformations, as shown by Pighizzini [Pig]. So, for computing properties of traces, we can work with either model and then apply Pighizzini’s translation without incurring a significant cost in the state space.

However, at an operational level, asynchronous cellular automata and asynchronous automata are based on very different kinds of intuition. Thus, if we want to understand how to compute something using asynchronous automata, very little insight is gained by solving the problem on hand using asynchronous cellular automata and then translating that solution back to asynchronous automata. So, for instance, though bounded timestamping algorithms appear both in the construction of [CMZ] and in the construction of the gossip automaton, it is difficult to see how our algorithm can be derived from the one described in [CMZ].

We feel that it is important to have a clear understanding of what can be computed locally and directly in the framework of asynchronous automata since these automata are natural models of distributed systems. They correspond to a very intuitive notion of synchronizing finite state machines which exchange information whenever they meet. Asynchronous automata are closely connected to well-established formalisms for describing concurrent systems. For instance, an automaton of this type can easily be represented as a labelled 1-safe Petri net [Zie1]. These automata also generalize synchronization mechanisms which have been studied in process calculi like TCSP [BHR].

On the other hand, at the operational level, asynchronous cellular automata do not correspond to any standard model of distributed systems. We can view the distributed state space of these automata as a concurrent-read exclusive-write shared memory. However, distributed algorithms based on the shared memory model normally assume that the store is equally shared by all processes. Instead, in an asynchronous cellular automaton, the memory is shared in a localized manner.

Building the gossip automaton appears to be a basic step in tackling many problems in the theory of asynchronous automata. In addition to our new proof of Zielonka’s theorem, we have found other important applications of our solution to the gossip problem. In [KMS], a determinization construction is presented for asynchronous automata using a generalization of the classical subset construction for finite automata. This construction allows us to keep track of the global states which are currently valid at any stage of a computation by a non-deterministic asynchronous automaton. The data maintained by the gossip automaton plays a crucial role in determining how much information can be safely “forgotten” by the subset automaton without sacrificing global consistency.

We feel that this determinization construction will lead to a direct complementation construction for Büchi asynchronous automata [GP]. These automata recognize ω-regular trace languages, which are a natural trace-theoretic generalization of ω-regular string languages. Büchi asynchronous automata are beginning to play an important role in concurrency theory. They are known to be closed under complementation for algebraic reasons, but the only effective complementation construction provided so far has been for Büchi asychronous cellular automata [Mus]. There appears to be no straightforward way of applying this construction to Büchi asynchronous automata.

Recently, Thiagarajan [Thi] has developed an extension of propositional linear-time temporal logic which is interpreted over infinite traces rather than infinite linear sequences. This logic appears to be quite expressive, while remaining decidable (unlike several other partial-order logics studied in the literature [LPRT]). The decision procedure for this logic is automata-theoretic, in the style of Vardi and Wolper [VW], except that it makes use of Büchi asychronous automata rather than conventional Büchi automata. The gossip automaton plays a crucial role in this construction as well. In fact, this was the original motivation for constructing the gossip automaton.

Acknowledgments P.S. Thiagarajan suggested the gossip problem. We have benefited greatly from discussions with him. The reformulation of the gossip automaton in terms of ideals and frontiers emerged during work with Nils Klarlund on determinizing asynchronous automata. His suggestions have been a great help in cleaning up the presentation. We also thank Robert de Simone for pointing out some subtle technical errors. The first author was partially supported by IFCPAR Project 502-1.

References

[AR] I.J. Aalbersberg, G. Rozenberg: Theory of traces, Theoret. Comput. Sci., 60 (1988) 1–82.

[BHR] S.D. Brookes, C.A.R. Hoare, A.W. Roscoe: A theory of communicating sequential processes, J. ACM, 31 (1984) 560–599.

[CMZ] R. Cori, Y. Metivier, W. Zielonka: Asynchronous mappings and asynchronous cellular automata, Inform. and Comput., 106 (1993) 159–202.

[CS] R. Cori, E. Sopena: Some combinatorial aspects of time-stamp systems, Europ. J. Combinatorics, 14 (1993) 95–102.

[Die] V. Diekert: Combinatorics on traces, LNCS 454 (1990).

[DS] D. Dolev, N. Shavit: Bounded concurrent time-stamps are constructible, Proc. ACM STOC (1989) 454–466.

[GP] P. Gastin, A. Petit: Asynchronous cellular automata for infinite traces, Proc. ICALP ’92, LNCS 623 (1992) 583–594.

[HHL] S.M. Hedetniemi, S.T. Hedetniemi, A.L. Liestman: A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988) 319–349.

[HU] J. Hopcroft, J.D. Ullman: Introduction to automata, languages and computation, Addison-Wesley (1979).

[IL] A. Israeli, M. Li: Bounded time-stamps, Proc. 28th IEEE FOCS (1987) 371–382.

[KMS] N. Klarlund, M. Mukund, M. Sohoni: Determinizing asynchronous automata, to appear in Proc. ICALP 1994. A preliminary version appears as Report TCS-93-5, School of Mathematics, SPIC Science Foundation, Madras, India (1993).

[LV] M. Li, P. Vitanyi: How to share concurrent asynchronous wait free variables, Proc. ICALP ’89, LNCS 372 (1989) 488–507.

[LPRT] K. Lodaya, R. Parikh, R. Ramanujam, P.S. Thiagarajan: A logical study of distributed transition systems, to appear in Inform. and Comput. Also available as Report TCS-93-8, School of Mathematics, SPIC Science Foundation, Madras, India (1993).

[Maz] A. Mazurkiewicz: Basic notions of trace theory, in: J.W. de Bakker, W.- P. de Roever, G. Rozenberg (eds.), Linear time, branching time and partial order in logics and models for concurrency, LNCS 354 (1989) 285–363.

[MS] M. Mukund, M. Sohoni: Keeping track of the latest gossip: Bounded time-stamps suffice, Proc. FST&TCS ’93, LNCS 761 (1993) 388–399.

[Mus] A. Muscholl: On the complementation of Büchi asynchronous cellular automata, to appear in Proc. ICALP 1994.

[Pig] G. Pighizzini: Recognizable trace languages and asynchronous automata, Phd Thesis, Dip. Scienze dell’Informazione, Univ. di Milano (1993).

[Sta] R.P. Stanley: Enumerative combinatorics: Volume I, Wadsworth & Brookes/Cole (1986).

[Thi] P.S. Thiagarajan: TrPTL: A trace based extension of linear time temporal logic, to appear in Proc. IEEE LICS 1994. A preliminary version appears as Report TCS-93-6, School of Mathematics, SPIC Science Foundation, Madras (1993).

[VW] M. Vardi, P. Wolper: An automata theoretic approach to automatic program verification, Proc. 1st IEEE LICS (1986) 332–345.

[Zie1] W. Zielonka: Notes on finite asynchronous automata, R.A.I.R.O.—Inform. Théor. Appl., 21 (1987) 99–135.

[Zie2] W. Zielonka: Safe executions of recognizable trace languages, Proc. Logical Foundations of Computer Science, LNCS 363 (1989) 278–289.