Keeping Track of the Latest Gossip in a Distributed System^{∗}

Madhavan Mukund SPIC Mathematical Institute 92 G.N. Chetty Road, Madras 600 017, India E-mail: madhavan@smi.ernet.in

Milind Sohoni Department of Computer Science and Engineering Indian Institute of Technology, Bombay 400 076, India E-mail: sohoni@cse.iitb.ernet.in

Abstract

We tackle a natural problem from distributed computing, involving time-stamps. Let P = {p_{1}, p_{2}, …, p_{N}} be a set of computing agents or processes which synchronize with each other from time to time and exchange information about themselves and others. The gossip problem is the following: Whenever a set P ⊆ 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.

Keywords: Distributed algorithms, synchronous communication, bounded timestamps, asynchronous automata

∗This paper appears in Distributed Computing, 10, 3, (1997) 117-127. A preliminary version of this paper appeared in [22]. The first author was partially supported by IFCPAR Project 502-1. This work was done while the second author was with the School of Mathematics, SPIC Science Foundation, now known as the SPIC Mathematical Institute.

Introduction

The aim of this paper is to tackle a natural problem from distributed computing, involving time-stamps. Let P = {p_{1}, p_{2}, …, p_{N}} be a set of computing agents or processes which synchronize with each other from time to time and exchange information about themselves and others. The gossip problem is the following: Whenever a set P ⊆ 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 ⊆ 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 ⊆ 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 P 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.

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 [30]. 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.

(Calling these automata asynchronous is misleading. The automata communicate synchronously. Zielonka used the term “asynchronous” to emphasize that different components of the network can proceed independently while processing the input. We continue to use this rather inappropriate terminology for historical reasons.)

A preview of the algorithm

Our algorithm proceeds by having each process maintain different levels of information about the rest of the system. At the primary level, a process p records the latest information that it has heard from every other process. Thus, the primary information of process p regarding process q corresponds to the most recent event performed by q which p is aware of, either directly or indirectly.

The secondary information of a process consists of its knowledge about the primary information of other processes. Thus, for processes p, q and r, p’s secondary information would refer to events of the form “the latest that p knows about what q knows about r”. Similarly, the tertiary information of a process consists of its knowledge about the secondary information of every other process.

Events are identified by labels assigned to them when they occur—the label of each event is assigned jointly by all the processes that take part in the event. (An event involving only one process corresponds to an internal event.) These labels are best thought of as time-stamps. The goal of the algorithm is to correctly compare and update the primary information of all processes which participate in each synchronization, with the constraint that only a bounded number of labels are used to time-stamp events, regardless of the length of the overall computation.

Let p and q be processes that synchronize. We prove that p’s primary information about r is more recent (and therefore better) than q’s primary information about r if and only if the event corresponding to r recorded in q’s primary information is also present in p’s secondary information. In other words, the primary information of p and q can be compared by just checking for equality of labels within their primary and secondary information—we do not have to maintain any order between the labels. This feature is crucial for designing an algorithm which uses only a bounded number of time-stamps: reusing a label will, in general, destroy any a priori order on the set of labels.

It then follows that we can reuse time-stamps provided we maintain the following invariant across the system: At any stage of the computation, if the same label is present in the primary or secondary information of two different processes, then the labels actually point to the same event. In other words, two different instances of the same time-stamp should never simultaneously be present in the primary and secondary information of the system. This invariant is difficult to maintain because the processes which take part in an event and assign a time-stamp to it will not, in general, have access to the primary and secondary information of all processes across the system. So, they have no way of knowing precisely which labels are “in use” across the system when the event occurs.

It turns out that tertiary information can be used to resolve the problem of deciding when a time-stamp can be reused. We prove that a time-stamp previously assigned by a process p is currently “in use”—i.e., it currently belongs to the primary or secondary information of some other process q—only if it also belongs to the tertiary information of p. From this, it follows that labels which are not in the tertiary information of a process can be reused. Since the number of events in the tertiary information of each process is bounded, processes in the system can always work with a bounded set of labels large enough to permit each event to be assigned a fresh time-stamp which does not clash with the set of time-stamps currently “in use” across the system.

As we remarked earlier, our algorithm can be described as an asynchronous automaton, where each process is locally a finite-state machine. The automaton that we construct to solve the gossip problem can be effectively presented in space polynomial in the number of processes in the system. This means that the automaton can be embedded in other distributed algorithms without sacrificing efficiency.

In this paper, we solve the gossip problem for systems with multi-party synchronization. Surpisingly, the problem appears no easier when restricted to systems with pairwise synchronization. Though systems with pairwise synchronization are perhaps more representative of “real world” systems, we have chosen to describe our solution in the general setting because it has important applications in theoretical studies of distributed systems based on the asynchronous automaton model [13, 14, 23].

The technique we describe for analyzing synchronizing systems is also applicable to more general classes of distributed systems. For instance, we can adapt our algorithm for maintaining primary, secondary and tertiary information to solve the gossip problem for “well behaved” classes of message-passing systems [21].

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 problem we set out to tackle.

Section 6 briefly examines extensions of the basic gossip automaton and possibilities for optimizing the construction. We also look at applications of the gossip automaton in logic and the theory of asynchronous automata [13, 14, 23, 27].

In the concluding Discussion, we place our results in perspective. We discuss similarities and differences with other work on “gossiping” and bounded time-stamps [1, 2, 3, 5, 8, 9, 12].

1 Preliminaries

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

We model a computation of the system as a sequence of communications—that is, a word u ∈ C^{∗}. Let u be of length m. It is convenient to think of u as a function u : [1..m] → C, 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 ∅ → C.

Events With u : [1..m] → C, we associate a set of events E_{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, E_{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 ε, E_{u} = {0}.

Usually, we will write E for E_{u}. For p ∈ P and e ∈ E, we write p ∈ e to denote that p ∈ u(i) when e = (i, u(i)). Thus, p ∈ e implies that process p participated in the

[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: A typical computation of a system of synchronizing processes

synchronization e. For the initial event 0, we define p ∈ 0 to hold for all p ∈ P. If p ∈ e, then we say that e is a p-event.

Ordering relations on E The word u imposes a total order on events in E: 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.

However, the temporal order < does not accurately reflect the cause and effect relationship between events in E. Clearly, 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. To record information about causality and independence, we define a partial order ⊑^{∗} on E.

To begin with, we observe that each process p orders the events in which it participates: define ◁_{p} to be the relation

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

The set of all p-events in E 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.

It is not difficult to see that the causality relation ⊑^{∗} accurately models the cause and effect relationship between events in E. In particular, all rearrangements of the letters in u which arise out of permuting adjacent independent synchronizations will give rise to isomorphic structures (E, ⊑^{∗}).

Example: Let P = {p, q, r, s} and C = {a, b, c} where a = {p, q}, b = {r, s} and c = {q, r, s}. Figure 1 shows the events E 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 ∈ P, the set of all p-events in E is totally ordered by ⊑^{∗} since ◁_{p}^{∗} is contained in ⊑^{∗}.

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

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

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

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

For any processes p, p′, q ∈ P, the events latest_{p→q}(E) and latest_{p′→q}(E) are both qevents and are thus always comparable with respect to ⊑^{∗}. Our goal is to design a scheme whereby each process p maintains a bounded amount of information locally, so that whenever a set c ⊆ P synchronizes, the processes in c can decide amongst themselves which of them has heard most recently from every process in the system. More formally, for every q ∈ P, all the processes in c should be able to jointly compute which of the events {latest_{p→q}(E)}_{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 P be a finite set of processes as before. A distributed alphabet is a pair (Σ, θ) where Σ is a finite set of actions and θ : Σ → (2^{P} − {∅}) assigns a non-empty set of processes to each a ∈ Σ.

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

Asynchronous automaton An asynchronous automaton A over (Σ, θ) is of the form ({S_{p}}_{p∈P}, {→_{a}}_{a∈Σ}, S_{0}, S_{F}), where →_{a} ⊆ S_{θ(a)} ×S_{θ(a)} is the local transition relation for a, and S_{0}, S_{F} ⊆ S_{P} 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. Processes outside θ(a) do not change their state when a occurs. Thus we define the global

transition relation ⇒ ⊆ S_{P} × Σ × S_{P} by s⃗ ⟹^{a} s⃗′ if s⃗_{θ(a)} →_{a} s⃗ ′_{θ(a)} and s⃗_{P−θ(a)} = s⃗ ′_{P−θ(a)}.

A is called deterministic if the global transition relation ⟹ of A is a function from S_{P} × Σ to S_{P} and the set of initial states S_{0} is a singleton. Notice that ⟹ is a function iff each local transition relation →_{a}, a ∈ Σ, is a function from S_{θ(a)} to S_{θ(a)}. We shall only deal with deterministic asynchronous automata in this paper.

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

The word u is accepted by A if there is a run ρ of A on u such that ρ(m) ∈ S_{F}. L(A), the language recognized by A, is the set of words accepted by A. In this paper, we will not look at asynchronous automata as language recognizers. Instead, we shall 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_{Σ} = {f_{a} : Σ^{∗} → Val}_{a∈Σ}. So, F_{Σ} contains a function f_{a} for each letter a ∈ Σ.

F_{Σ} is locally computable if we can find a deterministic asynchronous automaton A = ({S_{p}}_{p∈P}, {→_{a}}_{a∈Σ}, S_{0}, S_{F}) and a family of local functions G_{Σ} = {g_{a} : S_{θ(a)} → Val}_{a∈Σ}, such that for each word u : [1..m] → Σ, f_{a}(u) = g_{a}(s⃗_{θ(a)}), where s⃗ = ρ_{u}(m) and ρ_{u} is the unique run of A 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 P can now be formalized in terms of asynchronous automata.

Given C ⊆ (2^{P} − {∅}), let Σ = {ĉ}_{c∈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 ∈ C and the corresponding letter ĉ ∈ Σ and refer to both as just c. Thus, we will use S_{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 ⊆ P. For each q ∈ P, 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}(E_{u}) ⊑^{∗} latest_{p→q}(E_{u})}.

Let Val = (2^{P} − {∅})^{P}. So, each member of Val is a function from P to non-empty subsets of P. Our 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∈P}.

2 Ideals and Frontiers

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

The main source of difficulty in solving the gossip problem is the fact that the processes in P 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 E, not every subset of E arises from such a partial view. Those subsets of E which do correspond to partial views of u are called ideals.

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

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.

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. Since 0 lies below every event in E, 0 ∈ I for every non-empty ideal I. We shall assume that every ideal we consider is non-empty.

Clearly the entire set E is an ideal, as is e↓ for any e ∈ 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 ideal e_{5} ↓, whereas {0, e_{1}, e_{2}, e_{3}, e_{4}, e_{5}} is an ideal which is not of the form e↓ for any e ∈ E.

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

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 ⊆ P, the P -view of I, denoted I|_{P}, is ⋃_{p∈P} I|_{p}, which is also an ideal. In particular, we have I|_{P} = 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|_{P}.

For an ideal I, the views I|_{p} and I|_{q} seen by two processes p, q ∈ P 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 ∈ P. 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 ∈ P. e is an r-sentry for p with respect to q}

1In 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.

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 ∈ P, we have already defined latest_{p→q}(E), 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 ∈ P. 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∈P}. 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 ⊆ P, primary_{P} (I) = ⋃_{p∈P} primary_{p}(I).

As we have already remarked, for all q ∈ P, 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∈P} 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 ∈ P. Once again, for P ⊆ 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 ∈ P. 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 ∈ P 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 ∈ P 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, (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′′ ∈ P 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 ∈ P and e ∈ frontier_{pq}(I) an r-sentry for p with respect to q. Then e = latest_{p→r}(I). Also, for some r′ ∈ P, 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′. Since e′ ∈ I|_{p}, this means that f ∈ I|_{p} as well, which is a contradiction.

Next, we must show that e = latest_{q→r′→r}(I) for some r′ ∈ P. 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 ∈ P. 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. For r ∉ {p, q}, if the event latest_{p→r}(E_{u}) is also present in q’s set of secondary events secondary_{q}(E_{u}), both p and q know that q’s latest r-event latest_{q→r}(E_{u}) is at least as recent as latest_{p→r}(E_{u}). So, after the synchronization, latest_{q→r}(E_{ua}) is the same as latest_{q→r}(E_{u}), whereas p inherits this information from q— i.e., latest_{p→r}(E_{ua}) = latest_{q→r}(E_{u}). In this way, for each r ∈ P, p and q locally update their primary information about r in E_{ua}. Clearly latest_{p→q}(E_{ua}) = latest_{q→p}(E_{ua}) = e_{a}, where e_{a} is the new event—i.e., E_{ua} − E_{u} = {e_{a}}.

This procedure generalizes to any arbitrary set P ⊆ 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 −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 ⊆ 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., E_{w} − E_{u} = {e_{a}}. Then:

• e_{a} ∈ primary_{P}(E_{w}).

• primary_{P}(E_{w}) ⊆ {e_{a}} ∪ primary_{P}(E_{u}).

• secondary_{P}(E_{w}) ⊆ {e_{a}} ∪ secondary_{P}(E_{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′′ ∈ P. This can be checked locally provided events in E_{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 E_{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

[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: At e_{7}, e_{1} ∈ secondary_{p}(e_{7}↓), but r and s cannot “see” e_{1} in secondary_{{r,s}}(e_{7}↓).

occurrence of a.^{2} In this manner, the processes in P 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 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 E_{u}. Since the cardinality of secondary_{P}(E_{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_{P−a}(E_{u}) − secondary_{a}(E_{u}).

Example: Let P = {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 E corresponding to the word cbadecc.

2Recall that for each action â ∈ Σ, θ(â) = a, and we use a to denote both the action and the subset of processes which synchronize at that action (see page 7).

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

secondary_{s}(E) = \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}(E) = max_{s}(E), secondary_{r}(E) = secondary_{s}(E) when viewed as sets of events. So, e_{1} ∉ secondary_{r}(E) either. Thus, e_{1} is a c-event which belongs to secondary_{P}(E) − secondary_{c}(E).

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

Tertiary information The tertiary information of p after I, tertiary_{p}(I), is the (indexed) set ⋃_{q∈P} 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 ∈ P. As before, for P ⊆ 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 ∈ P. 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 ∈ 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′′ ∈ 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′ ∈ E and some r ∈ P 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 ∈ P. 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 ∈ P and e a p-event in I. If e ∉ tertiary_{p}(I) then e ∉ primary_{P}(I) ∪ secondary_{P}(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 P 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_{P}(I) ∪ secondary_{P}(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. The processes in the automaton maintain this information in terms of time-stamps: when an event e occurs, it is assigned a time-stamp τ(e) by the processes which take part in e.

For p ∈ P, a local state of p is defined by three associative arrays prim_{p}, sec_{p} and ter_{p}, indexed by P, P × P and P × P × P respectively. Each entry in these arrays is a pair of the form ⟨P, ℓ⟩, where P is a subset of P and ℓ is a label drawn from a finite set L—it is sufficient for L to have N^{3}+1 entries, where N is the number of processes in P.

After reading a word u, each entry ⟨P, ℓ⟩ in the arrays prim_{p}, sec_{p} and ter_{p} corresponds to the time-stamp τ(e) of some event e ∈ E_{u}. We shall show that for all q, r, s ∈ P, the values stored in prim_{p}(q), sec_{p}(q, r) and ter_{p}(q, r, s) are, in fact, the time-stamps of the events latest_{p→q}(E_{u}), latest_{p→q→r}(E_{u}) and latest_{p→q→r→s}(E_{u}), respectively.

The initial state is the global state in which, for each process p, all entries in prim_{p}, sec_{p} and ter_{p} are set to ⟨P, ℓ_{0}⟩, where ℓ_{0} is an arbitrary but fixed label from L. In other words, the processes jointly assign the time-stamp τ(0) = ⟨P, ℓ_{0}⟩ to the initial event 0.

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

(i) When an a-event e_{a} occurs, the processes in a first choose a time-stamp τ(e_{a}) = ⟨a, ℓ⟩ such that for some p ∈ a, ⟨a, ℓ⟩ does not appear in ter_{p}

(Recall that L has N^{3}+1 labels. Since there are at most N^{3} labels in ter_{p} for each p, we will always be able to find an unused label in L to assign to e_{a}. In general, we have to choose ⟨a, ℓ⟩ in a canonical way. One possibility is to linearly order the sets P and L. Let p_{a} be the smallest process in a with respect to the ordering on P. To fix the time-stamp ⟨a, ℓ⟩ assigned to e_{a}, choose ℓ such that it is the smallest label with respect to the ordering on L which does not appear in ter_{p_{a}}.)

(ii) Let a = {p_{1}, p_{2}, …, p_{k}}. Corresponding to each process r ∉ a, fix a process π_{r} ∈ a as follows. π_{r} := p_{1}; for each i in {2, 3, …, k} do

if the value stored in prim_{π_{r}}(r) appears in sec_{p_{i}} then π_{r} := p_{i};

od

(iii) For each p ∈ a, update prim_{p}, sec_{p} and ter_{p} in phases.

• First, update {prim_{p}}_{p∈a} as follows.

For each q ∈ a, prim_{p}(q) := ⟨a, ℓ⟩.
For each r ∈ P − a , prim_{p}(r) := prim_{π_{r}}(r).

• Next, update {sec_{p}}_{p∈a} as follows.

For each q, r ∈ P such that q ∈ a, sec_{p}(q, r) := prim_{q}(r).
For each q, r ∈ P such that q ∉ a, sec_{p}(q, r) := sec_{π_{q}}(q, r).

• Finally, update {ter_{p}}_{p∈a} as follows.

For each q, r, s ∈ P such that q ∈ a, ter_{p}(q, r, s) := sec_{q}(r, s).
For each q, r, s ∈ P such that q ∉ a, ter_{p}(q, r, s) := ter_{π_{q}}(q, r, s).

We now verify that the arrays maintained by each process p in the gossip automaton always record the time-stamps of the primary, secondary and tertiary information of p.

Proposition 6 Let u ∈ Σ^{∗}. For all processes p ∈ P, the values stored in prim_{p}, sec_{p} and ter_{p} after reading u satisfy the following properties.

• For all q ∈ P, prim_{p}(q) = τ(latest_{p→q}(E_{u})).
• For all q, r ∈ P, sec_{p}(q, r) = τ(latest_{p→q→r}(E_{u})).
• For all q, r, s ∈ P, ter_{p}(q, r, s) = τ(latest_{p→q→r→s}(E_{u})).

Moreover, for all processes p, q ∈ P and events e ∈ primary_{p}(E_{u}) ∪ secondary_{p}(E_{u}) and f ∈ primary_{q}(E_{u}) ∪ secondary_{q}(E_{u}), if τ(e) = τ(f) then e = f.

Proof The proof is by induction on n, the length of u. (n = 0)

The base case is when u is the empty string. We know that for each p ∈ P, all entries in prim_{p}, sec_{p} and ter_{p} are initially set to ⟨P, ℓ_{0}⟩, where ⟨P, ℓ_{0}⟩ is the time-stamp assigned to the initial event 0. Clearly, these values satisfy all the conditions specified in the statement of the proposition. (n > 0)

Suppose u = wa. The time-stamp ⟨a, ℓ⟩ assigned to the new a-event e_{a} in step (i) of the transition does not appear in ter_{p} for some p ∈ a. By the induction hypothesis, the values stored in ter_{p} after reading w are the time-stamps of the corresponding events in tertiary_{p}(E_{w}). Lemma 4 then guarantees that no event in primary_{P}(E_{w})∪secondary_{P}(E_{w}) is time-stamped ⟨a, ℓ⟩—if there were such an event, it would be in the tertiary information tertiary_{q}(E_{w}) of every process q ∈ a as a result of which, by the induction hypothesis, the label ⟨a, ℓ⟩ would be in ter_{q} after reading w for every q ∈ a.

By the induction hypothesis, we also know that no two distinct events in primary_{P}(E_{w}) ∪secondary_{P}(E_{w}) are assigned the same time-stamp. Since primary_{P}(E_{u}) ⊆ {e_{a}}∪ primary_{P}(E_{w}) and secondary_{P}(E_{u}) ⊆ {e_{a}} ∪ secondary_{P}(E_{w}) (Proposition 3), it follows that the time-stamps assigned to primary_{P}(E_{u}) ∪ secondary_{P}(E_{u}) are also distinct. In other words, for all processes p, q ∈ P and events e ∈ primary_{p}(E_{u}) ∪ secondary_{p}(E_{u}) and f ∈ primary_{q}(E_{u}) ∪ secondary_{q}(E_{u}), if τ(e) = τ(f) then e = f.

We now have to verify that the updated values in prim_{p}, sec_{p} and ter_{p} for each p ∈ a are the time-stamps of the corresponding events in the primary, secondary and tertiary information of p after u.

By the induction hypothesis, for each p ∈ a, the values in prim_{p} and sec_{p} after reading w are the time-stamps assigned to the corresponding events in primary_{p}(E_{w}) and secondary_{p}(E_{w}) respectively. By the induction hypothesis, we also know that for all p, q, r, s, s′ ∈ P, if the value stored in prim_{p}(r) after reading w is the same as the value stored in sec_{q}(s, s′) after reading w then, in fact, the event latest_{p→r}(E_{w}) is the same as the event latest_{q→s→s′}(E_{w}).

It then follows that for r ∉ a, the process π_{r} ∈ a identified in step (ii) of the transition is one of the processes in a which has the best primary information about r after w—by Lemma 2, for p, q ∈ a and r ∉ a, latest_{p→r}(E_{w}) ⊑^{∗} latest_{q→r}(E_{w}) iff the event latest_{p→r}(E_{w}) appears in secondary_{q}(E_{w}), which is equivalent to checking that the timestamp τ(latest_{p→r}(E_{w})) stored in prim_{p}(r) appears in sec_{q}.

From this, it is easy to see that for all p ∈ a, the updates made to prim_{p}, sec_{p} and ter_{p} in step (iii) ensure that for all q, r, s ∈ P, prim_{p}(q) = τ(latest_{p→q}(E_{u})), sec_{p}(q, r) = τ(latest_{p→q→r}(E_{u})) and ter_{p}(q, r, s) = τ(latest_{p→q→r→s}(E_{u})). □

The gossip 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^{P} − {∅})^{P} which checks the arrays prim_{p} and sec_{p} of each process p in a and computes for each q ∈ P, 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∈P}.)

This immediately yields the result we set out to establish.

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

The size of the gossip automaton

Lemma 8 In the gossip automaton, the local state of each process p ∈ P can be described using O(N^{3} log N) bits, where N = |P|.

Proof A local state for p consists of the arrays prim_{p}, sec_{p} and ter_{p}. 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 in the array ter_{p}. By fixing an ordering of P × P × P, these events can be stored as a list with N^{3} entries.

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

We have already seen that it suffices to have O(N^{3}) labels in L. As a result, each label ℓ ∈ L can be written down using O(log N) bits.

To write down P ⊆ 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 L 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 fix a linear order on P, it suffices to label e by ⟨p_{e}, ℓ⟩ where, among the processes participating in e, p_{e} is the smallest with respect to the ordering on P. It is easy to verify that Proposition 6 continues to hold with respect to these modified labels.

Thus, we can modify our automaton so that the processes label each event by a pair ⟨p, ℓ⟩, where p ∈ P and ℓ ∈ L. 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. □ The preceding lemma implies that the number of local states of a process could be exponential in N, the number of processes in the system. In general, this would mean that we require an exponential amount of space to specify the entire automaton (though each state can be described using a polynomial number of bits) since the transition table of the automaton would have an exponential number of entries.

However, in this case, we do not need to exhaustively enumerate the entire state space and transition table to completely describe the automaton. Since the states are structured entities and the transition function is presented as an algorithm which manipulates the data in these structured states, the gossip automaton can in fact be effectively presented in space polynomial in N. This ability to build the gossip automaton efficiently “on the fly” is crucial for embedding it in other distributed algorithms.

6 Extensions and Applications

Beyond tertiary information

The gossip automaton consistently labels all primary and secondary events. In other words, at any point, distinct primary and secondary events have distinct time-stamps. By Lemma 2, this is sufficient to correctly compare and update primary information.

However, we may want to keep track of events which are older than secondary events. We can generalize the definition of secondary and tertiary information and inductively define the k-ary information of a process p with respect to an ideal I, for any natural number k.

The case k = 1 corresponds to primary information. For k > 1, the k-ary information of p after I, k-ary_{p}(I), is the (indexed) set ⋃_{q∈P} (k−1)-ary_{p}(latest_{p→q}(I) ↓). In other words, this is the latest information that p has in I about the (k−1)-ary information of q, for all q ∈ P.

It is not difficult to see that the argument in Lemma 4 can be extended to yield the following result, proved formally in [15].

Lemma 9 Let I be an ideal and p ∈ P. If e ∈ k-ary_{p}(I) then for every q ∈ e, e ∈ (k+1)-ary_{q}(I).

Together with Lemma 2, this implies that the gossip automaton can be modified to maintain consistent time-stamps for all events upto depth k, for any natural number k.

Optimizing the automaton

If we are only concerned with comparing and updating primary information, the gossip automaton can be made more concise. To achieve this, each process maintains its primary information as a directed graph which reflects the underlying ⊑^{∗}-order between primary events, rather than storing the information as a simple array of labels as we have described here. It turns out that processes can compare and update these primary graphs without recourse to secondary information. Secondary information is then required only to ensure that new events get unused labels. Tertiary information is dispensed with altogether. This leads to the following result (details can be found in [15]).

Lemma 10 The gossip automaton can be modified so that the local state of each process p ∈ P is describable using O(N^{2} log N) bits, where N = |P|.

It is important to note that this optimized automaton consistently labels only primary events. Secondary events could get inconsistent labels. This becomes relevant when we come to applications of the gossip automaton.

Further optimizations are possible if the structure of the alphabet (Σ, θ) is such that synchronizations are “well-behaved”. One example is when the processes are located on the vertices of an d-dimensional hypercube (i.e., |P| = 2^{d}), with synchronizations taking place along faces of the hypercube. Once again, details can be found in [15].

Applications

Building the gossip automaton is a basic step in tackling many problems in the theory of asynchronous automata.

Asynchronous automata play an important role in the theory of distributed systems because of their close connection to trace theory. Trace theory, initiated by Mazurkiewicz [19], is a language-theoretic approach to the study of concurrent systems. Traditionally, formal language theory models computations of sequential systems as strings over an abstract alphabet. Instead, trace theory describes computations of concurrent systems in terms of equivalence classes of strings, called traces. All strings in a trace are equivalent upto permutation of adjacent letters which belong to an underlying independence relation on the alphabet. Thus, the different elements of a trace correspond to different sequential observations of the same concurrent computation.

A deep theorem of Zielonka [30] shows that asynchronous automata are a natural distributed machine model for recognizing trace languages. Zielonka’s original proof of the connection between these automata and recognizable trace languages is widely accepted to be difficult to assimilate. In [23], we show that the gossip automaton can be used to provide a more structured proof of Zielonka’s theorem. Overall, the construction we present is quite similar to the one described in Zielonka’s original paper. However, we feel that by separating out clearly the role played by the gossip automaton, our proof is much easier to digest. (Other new proofs of Zielonka’s theorem exist [2], but these are based on asynchronous cellular automata [31], a slightly different—and, in our opinion, less intuitive—machine model.)

In [13], 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 key problem to be tackled in the determinization construction is to estimate the amount of information that can be safely “forgotten” by the subset automaton without sacrificing global consistency. It turns out that it is sufficient for each process to maintain “histories” upto the level of secondary events. This is accomplished by using the gossip automaton presented here to assign consistent time-stamps to all secondary events. Notice that the optimized gossip automaton of [15] cannot be used in the determinization construction since it only guarantees consistent time-stamps upto primary events.

In the past few years, there has been a lot of interest in extending asynchronous automata to process infinite inputs. Analogous to Büchi automata on infinite strings, Gastin and Petit [7] have defined Büchi asynchronous automata which operate on infinite traces. Although it has been known for a while that these automata are closed under complementation for algebraic reasons, the only direct complementation construction provided so far has been for Büchi asychronous cellular automata [24]. Safra’s determinization construction for Büchi automata [26] has recently been extended to Büchi asynchronous automata [14]. This provides a natural procedure for complementing these automata. Once again, the gossip automaton plays a crucial role in the construction.

Automata on infinite strings have always been closely linked to logic [28]. This connection holds for Büchi asynchronous automata as well. Recently, Thiagarajan [27] 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 [18]). The decision procedure for this logic is automata-theoretic, in the style of Vardi and Wolper [29], 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.

Asynchronous communication

In this paper, we have only dealt with synchronous communication. Synchronous communication achieves coördination among independent agents by periodically permitting subsets of agents to pool information together to make a decision.

Another standard way for agents to exchange information is through message-passing. This mode of exchanging information is usually referred to as asynchronous communication, since there may be an arbitrary delay between the time when a message is sent and the time when it is received.

Synchronous communication is easier to handle, both from a theoretical standpoint as well as from the point of view of programming. It is no coincidence that languages like CCS [20] and CSP [11] which have been developed for specifying communicating systems assume synchronous communication as the basic means of exchanging information.

However, when agents are widely separated in space, asynchronous communication is generally the only practical way of achieving coördination. So, there is a considerable body of literature devoted to distributed algorithms and protocols for asynchronous systems

We have extended our approach to deal with message-passing systems where the communication medium is reliable, subject to certain restrictions on the number of unacknowledged messages that can be present in the system at any given time [21]. This shows that our analysis based on primary, secondary and tertiary information is applicable to a much wider range of distributed systems than the purely synchronous systems discussed in this paper.

7 Discussion

We now discuss the connections between our results and other work in related areas.

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 [9]. The main aim is to find an optimal sequence of communications to distribute data for a given network topology.

Israeli and Li [12] 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”[17]. Their results have been extended and considerably simplified by a number of others [3, 5, 6, 8]. However, this line of work is based on a shared memory model, which is quite different in spirit from the asynchronous automaton model. Though it may be possible to formally translate their results to our framework, we feel that the intuition underlying their time-stamping algorithms is quite different from ours. In general, solutions to time-stamping problems seem to depend heavily on the underlying model of a distributed system that is used and it is difficult to compare such algorithms across models.

More closely connected to our work are the bounded time-stamping algorithms implemented using asynchronous cellular automata in the study of recognizable trace languages [1, 2]. The synchronization mechanism of asynchronous cellular automata is quite different from that of asynchronous automata. Asynchronous cellular automata correspond more closely to shared memory systems than to systems that communicate by direct interprocess communication. Thus, though the overall goal of the constructions in [1, 2] is closely related to the gossip problem which we have studied here, the two time-stamping algorithms appear to be incomparable since they are based on fundamentally different assumptions about how processes interact.

Our definition of locally computable functions is closely linked to the notion of asynchronous mappings which is fundamental to the constructions used in [2]. It would be interesting to formally characterize the class of locally computable functions and develop a methodology for automatically synthesizing an asynchronous automaton to compute a given locally computable function, as is done for asynchronous mappings in [2].

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. Thus, any distributed algorithm which needs to keep track of the flow of information between processes can incorporate the gossip automaton as a “background” routine. Moreover, since the gossip automaton can be constructed efficiently “on the fly”, embedding it in another algorithm does not involve a very significant computational overhead.

Since our algorithm does not add any extra messages to the underlying computation, it is automatically resilient to failures—even if some processes stop functioning, our algorithm will continue to update primary information correctly for those parts of the system which are still active in the underlying computation. This in-built fault-tolerance is also present in the shared memory time-stamping protocols of [1, 2, 3, 5, 8, 12] and others.

In an asynchronous automaton, each move is simultaneously performed by all participating processes. This strong atomicity assumption is not crucial for our algorithm. Notice that the label of an event is uniquely fixed by the primary, secondary and tertiary information of the participating processes. Thus, we could implement each multi-way synchronization as a series of synchronous communications where processes exchange their local information pairwise and then proceed independently. The deterministic nature of our algorithm guarantees that each process which participates in an event will locally choose the same time-stamp for the new event, since all processes taking part in the event base their choice of time-stamp on identical shared information. Similarly, once each process has collected the primary, secondary and tertiary information of every other participating process, it can update its local information unambiguously. Moreover, it can also compute the updated information of every other process which took part in the event.

The construction of the gossip automaton establishes a non-obvious property for all systems with synchronous communication. 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}.

There are obvious parallels between the notion of primary, secondary and tertiary information we use in this paper and the concept of levels of knowledge about events in a distributed system [10, 25]. It would be interesting to formally work out how our approach fits in with knowledge-theoretic techniques for analyzing distributed systems. As far as we are aware, none of the work in knowledge theory has addressed the synchronizing model that we consider here, so establishing a precise connection between the two approaches is not straightforward.

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. Finally, we thank the referees for several useful comments.

References

[1] R. Cori, Y. Metivier: Approximations of a trace, asynchronous automata and the ordering of events in a distributed system, Proc. ICALP ’88, LNCS 317 (1988) 147–161.

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

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

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

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

[6] C. Dwork, O. Waarts: Simple and efficient bounded concurrent timestamping or bounded concurrent time-stamps are comprehensible, Proc. 24th ACM STOC (1992) 655– 666.

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

[8] R. Gawlick, N. Lynch, N. Shavit: Concurrent time stamping made simple, Proc. ISTCS ’92, LNCS 601 (1992) 171–183.

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

[10] J. Halpern, Y. Moses: Knowledge and common knowledge in a distributed environment, J. Assoc. Comput. Mach., 37 (1990) 549–578.

[11] C.A.R. Hoare: Communicating Sequential Processes, Prentice-Hall, London (1984).

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

[13] N. Klarlund, M. Mukund, M. Sohoni: Determinizing asynchronous automata, Proc. ICALP 1994, LNCS 820 (1994) 130–141.

[14] N. Klarlund, M. Mukund, M. Sohoni: Determinizing Büchi asynchronous automata, Proc. FST&TCS 1995, LNCS 1026 (1995) 456–470.

[15] R. Krishnan, S. Venkatesh: Optimizing the gossip automaton, Report TCS-94-3, School of Mathematics, SPIC Science Foundation, Madras, India (1994).

[16] L. Lamport, N. Lynch: Distributed Computing: Models and Methods, in: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science: Volume B, North-Holland, Amsterdam (1990) 1157–1200.

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

[18] K. Lodaya, R. Parikh, R. Ramanujam, P.S. Thiagarajan: A logical study of distributed transition systems, Inform. and Comput., 119 (1995) 91–118.

[19] 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.

[20] R. Milner: Communication and Concurrency, Prentice-Hall, London (1989).

[21] M. Mukund, K. Narayan Kumar, M. Sohoni: Keeping track of the latest gossip in message-passing systems, Proc. Structures in Concurrency Theory (STRICT), Berlin 1995, Workshops in Computing Series, Springer-Verlag (1995) 249–263.

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

[23] M. Mukund, M. Sohoni: Gossiping, asynchronous automata and Zielonka’s theorem, Report TCS-94-2, School of Mathematics, SPIC Science Foundation, Madras, India (1994).

[24] A. Muscholl: On the complementation of Büchi asynchronous cellular automata, Proc. ICALP 1994, LNCS 820 (1994) 142–153.

[25] R. Parikh, R. Ramanujam: Distributed processes and the logic of knowledge, Proc. Logics of Programs ’85, LNCS 193 (1985) 256–268.

[26] S. Safra: On the complexity of ω-automata, Proc. 29th IEEE FOCS (1988) 319–327.

[27] P.S. Thiagarajan: TrPTL: A trace based extension of linear time temporal logic, Proc. 9th IEEE LICS (1994) 438–447.

[28] W. Thomas: Automata on infinite objects, in J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Volume B, North-Holland, Amsterdam (1990) 133–191.

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

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

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