Foundations of Software Technology and Theoretical Computer Science, 13th Conference, Proceedings, R.K. Shyamasundar (Ed.), Lecture Notes in Computer Science 761, Springer-Verlag (1993) 388–399.

Keeping Track of the Latest Gossip: Bounded Time-Stamps Suffice

Madhavan Mukund and Milind Sohoni

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

                   Email: {madhavan,sohoni}@ssf.ernet.in

Abstract. Consider a distributed system consisting of N independent communicating agents. Periodically, agents synchronize and exchange information, both about each other and about agents they have talked to earlier. As a result, an agent a_{i} may receive indirect information about another agent a_{j} which is more recent than the information exchanged in the last direct synchronization between a_{i} and a_{j}. The problem is to ensure that agents always come away from a synchronization with the latest possible information about all other agents. This requires that when a_{i} and a_{j} meet, they should decide which of them has more recent information about any other agent a_{k}. We propose an algorithm to solve this problem which is finite-state and local. Formally, this means our algorithm can be implemented by an asynchronous automaton. Keywords: Distributed algorithms, synchronous communication, bounded time-stamping, asynchronous automata.

1 Introduction

Consider N agents a_{1}, …, a_{N} which synchronize with each other from time to time and exchange information about themselves and others. Whenever an agent a_{i} talks to another agent a_{j} the two of them must decide which of them has the latest information, direct or indirect, about every other agent a_{k}.

This is easily accomplished if the agents decide to locally time-stamp every call and pass these time-stamps along with each exchange of information. But as time progresses the time-stamp values increase without bound and most of the agents’ time would be consumed in passing on large numbers, as opposed to actual gossip.

We propose a time-stamping algorithm in which the values are bounded. Despite this restriction, any pair of agents can always decide which of them has better information about every other agent. Thus, in essence, the agents may be finite state machines. Further, the algorithm itself does not induce any additional communications, and thus works for all communication sequences. The algorithm is implemented using asynchronous automata [Z]—a powerful and natural model for concurrent systems. The algorithm implies that we can extend the range of systems modelled by these automata to include those which require us to keep track of the latest information flow between agents.

We point out that “bounded time-stamps” have been studied, but in contexts very different from ours. Israeli and Li [IL] introduced them for creating “atomic registers” which are fundamental for algorithms on distributed systems. However, their work and that of others [CS, DS] is based on a shared-memory model, which is quite different in spirit from the asynchronous automaton model.

The paper is organized as follows. Section 2 formalizes the problem and describes the automata which run our algorithm. Sections 3 and 4 analyse the problem and present our algorithm. We conclude with a discussion of our result.

2 Preliminaries

Let A = {a_{1}, a_{2}, …, a_{N}} be a set of agents. These agents communicate with each other synchronously. For simplicity, we assume that agents only synchronize in pairs. This restriction is not crucial: multi-way synchronizations are similarly handled. Details can be found in [MS].

Let a communication between agents a_{i} and a_{j} be denoted by c_{{i,j}}, abbreviated as c_{ij} or c_{ji}. Thus, if all pairs of agents can communicate with each other, we have a set of communication actions Σ = {c_{{i,j}} | i, j ∈ {1, 2, …, N} and i ≠ j}. For c_{ij} ∈ Σ, let dom(c_{ij}) (the domain of c_{ij}) denote the set {a_{i}, a_{j}}. A word α ∈ Σ^{∗} represents a finite sequence of communications between the agents.

2.1 Asynchronous automata

Associate a finite set (of local states) Q_{i} with each agent a_{i}, for i ∈ {1, 2, …, N}. Each Q_{i} contains a distinguished initial state q_{in}^{i}. Let Q_{G} = Q_{1} × Q_{2} × ⋯ × Q_{N}. Q_{G} represents the set of possible global states of the system. For q̄ = (q_{1}, q_{2}, …, q_{N}) ∈ Q_{G}, let q̄[i] denote the i^{th} component q_{i} of q̄. With each pair of agents a_{i} and a_{j}, we associate a deterministic transition function δ_{ij} : (Q_{i} × Q_{j}) → (Q_{i} × Q_{j}). Let δ = {δ_{ij} | i, j ∈ {1, 2, …, N}, i < j}.

An asynchronous automaton [Z] over Σ is a structure M = (Σ, Q_{1}, Q_{2}, …, Q_{N}, δ, (q_{in}^{1}, q_{in}^{2}, …, q_{in}^{N})).

We associate with M a global transition function Δ : Q_{G}×Σ → Q_{G} such that Δ ((q_{1}, q_{2}, …, q_{N}), c) = (q′_{1}, q′_{2}, …, q′_{N}) iff for a_{i}, a_{j} ∈ dom(c), δ_{ij}(q_{i}, q_{j}) = (q′_{i}, q′_{j}) and for all a_{k} ∉ dom(c), q_{k} = q′_{k}.

For α ∈ Σ^{∗}, let |α|, the length of α, be M. We may then regard α as a function α : {1, 2, …, M} → Σ. The n^{th} element of α, 1 ≤ n ≤ M, is denoted by α(n).

A run of M on α : {1, 2, …, M} → Σ is a function ρ : {0, 1, …, M} → Q_{G} such that ρ(0) = (q_{in}^{1}, q_{in}^{2}, …, q_{in}^{N}) and ρ(ℓ) = Δ(ρ(ℓ−1), α(ℓ)), 1 ≤ ℓ ≤ M. Since M is deterministic, each word α gives rise to a unique run, which we denote ρ_{α}.

Next we define when a function is locally computable by such automata.

Definition 2.1. Let Val be a set of values. A Σ-indexed family of functions is a set F_{Σ} = {f_{c} : Σ^{∗} → Val | c ∈ Σ}.

F_{Σ} is locally computable if we can find an asynchronous automaton M (as above) and a family of local functions G_{Σ} = {g_{c} | c ∈ Σ}, with each g_{c} of the form g_{c} : Q_{i_{1}} × Q_{i_{2}} → Val, where dom(c) = {a_{i_{1}}, a_{i_{2}}}, such that:

∀α : {1, 2, …, M} → Σ. f_{c}(α) = g_{c}(ρ_{α}(M)[i_{1}], ρ_{α}(M)[i_{2}])

In other words, for any α ∈ Σ^{∗} and c ∈ Σ, the agents in dom(c) can compute f_{c}(α) by synchronizing and checking their local states at the end of the run ρ_{α}.

2.2 The problem

Definition 2.2. Let α : {1, 2, …, M} → Σ. A path π from a_{i} to a_{j} in α is a sequence of pairs (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}) such that M ≥ k_{1} ≥ k_{2} ≥ ⋯ ≥ k_{n} ≥ 1 and ℓ_{m} ∈ {1, 2, …, N} for m ∈ {1, 2, …, n} satisfying:

(i) dom(α(k_{1})) = {a_{i}, a_{ℓ_{1}}}. (ii) ∀m ∈ {2, …, n}. dom(α(k_{m})) = {a_{ℓ_{m−1}}, a_{ℓ_{m}}}. (iii) a_{l_{n}} = a_{j}.

We say that source(π) = k_{1}, target(π) = k_{n} and that the length of π is n.

Note that k_{i} = k_{i+1} is expressly permitted. Let π_{1} = (k_{1}, a_{ℓ_{1}}) (k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}) be a path from a_{i} to a_{j} and π_{2} = (k′_{1}, a_{ℓ′_{1}})(k′_{2}, a_{ℓ′_{2}}) ⋯ (k′_{m}, a_{ℓ′_{m}}) be a path from a_{j} to a_{k}, such that k_{n} ≥ k′_{1}. Then we can concatenate the two paths to obtain a path π_{1}π_{2} = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}})(k′_{1}, a_{ℓ′_{1}}) ⋯ (k′_{m}, a_{ℓ′_{m}}) from a_{i} to a_{k}.

Definition 2.3. Let α : {1, 2, …, M} → Σ. A path π from a_{i} to a_{j} in α is good if for any other path π′ from a_{i} to a_{j}, target(π′) ≤ target(π).

Thus, a good path from a_{i} to a_{j} terminates at the latest communication that a_{j} took part in which a_{i} has heard about. If π and π′ are both good paths from a_{i} to a_{j}, then target(π) = target(π′).

With each a_{i} ∈ A we can associate a function latest_{a_{i}} : Σ^{∗} × A → N_{0} such that:

∀α ∈ Σ^{∗}. ∀a_{j} ∈ A. latest_{a_{i}}(α, a_{j}) = \{ \begin{matrix}k & if there is a good path π from \\ & a_{j} to a_{i} in α and target(π) = k \\ 0 & otherwise \end{matrix}

So, latest_{a_{i}}(α, a_{j}) indicates the most recent information a_{j} has about a_{i} after α.

Example 2.4. Let N = 5 and α be the communication sequence c_{12}c_{13}c_{14}c_{45}c_{25}c_{24}. So |α| = 6. Some paths from a_{2} to a_{1} are the following:

(1, a_{1}), (5, a_{5})(4, a_{4})(3, a_{1}), (6, a_{4})(4, a_{5})(4, a_{4})(3, a_{1}), (6, a_{4})(3, a_{1}).

Of these, all except the first are good paths. The paths (4, a_{4})(3, a_{1}) (2, a_{3}) from a_{5} to a_{3} and (2, a_{1})(1, a_{2}) from a_{3} to a_{2} may be concatenated to get (4, a_{4})(3, a_{1})(2, a_{3}) (2, a_{1})(1, a_{2}) from a_{5} to a_{2}. Note that this path traverses α(2) in both directions.

latest_{a_{1}}(α, a_{2}) = 3, whereas latest_{a_{1}}(α, a_{3}) = 2.

It is useful to draw the timing diagram of a communication sequence. Each agent’s history is represented by a horizontal line, with time increasing from left to right. Vertical edges connecting pairs of agents correspond to communications. In the diagram, to trace a path from a_{i} to a_{j}, we begin on the horizontal line for a_{i} and move vertically and/or left along lines in the diagram, to reach the line a_{j}, A good path from a_{i} to a_{j} terminates as far right as possible on the line a_{j}.

[figure: a_{1}; a_{2}; a_{3}; a_{4}; a_{5}; 1; c_{12}; •; •; 2; c_{13}; •; •; 3; c_{14}; •; •; 4; c_{45}; •; •; 5; c_{25}; •; •; 6; c_{24}; •; •]

Fig. 1. Timing diagram for Example 2.4, showing a good path

Let Val = (A ∪ {∗})^{N}. We define a family of functions F_{Σ} = {f_{c} | c ∈ Σ}, such that f_{c} = best_{c} : Σ^{∗} → Val as follows:

Let c ∈ Σ, with dom(c) = {a_{i}, a_{j}}. Then ∀α ∈ Σ^{∗}. best_{c}(α) = (a_{k_{1}}, a_{k_{2}}, …, a_{k_{N}}) where

∀m ∈ \{1, 2, …, N\}. a_{k_{m}} = \{ \begin{matrix}a_{i} & if latest_{a_{m}}(α, a_{j}) < latest_{a_{m}}(α, a_{i}) \\ a_{j} & if latest_{a_{m}}(α, a_{i}) < latest_{a_{m}}(α, a_{j}) \\ ∗ & otherwise \end{matrix}

So, if dom(c) = {a_{i}, a_{j}} and best_{c}(α)[m] = a_{i} (respectively a_{j}), then a_{i} (respectively, a_{j}) has heard from a_{m} more recently than a_{j} (respectively a_{i}) in the communication sequence α. best_{c}(α)[m] = ∗ signifies that both have exactly the same information about a_{m} after α. The main result of this paper is the following.

Theorem 2.5. The Σ-indexed family of functions F_{Σ} = {best_{c} | c ∈ Σ} is locally computable.

3 Global analysis

We will now analyse the “global” structure of good paths in the system. As we saw earlier, a communication sequence α ∈ Σ^{∗} may have several good paths from a_{i} to a_{j} in α. Let us fix a canonical good path as follows.

Definition 3.1. Let α : {1, 2, …, M} → Σ. Path π = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}) from a_{i} to a_{j} is an ideal path from a_{i} to a_{j} if the following conditions hold:

(i) π is a good path from a_{i} to a_{j}. (ii) For every m ∈ {1, 2, …, n−1}, the path π_{m} = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) … (k_{m}, a_{ℓ_{m}})

is a good path from a_{i} to a_{ℓ_{m}}.

We denote that π is an ideal path from a_{i} to a_{j} by π : a_{i} ⇝ a_{j}.

Example 3.2. Consider the communication sequence of Example 2.4 (see Figure 1.) The path marked in it is the ideal path a_{2} ⇝ a_{3} = (6, a_{4})(3, a_{1})(2, a_{3}). The prefixes (6, a_{4})(3, a_{1}) and (6, a_{4}) of this path constitute the ideal paths a_{2} ⇝ a_{1} and a_{2} ⇝ a_{4} respectively. The other ideal path from a_{2} is a_{2} ⇝ a_{5} = (5, a_{5}).

The following two observations are immediate.

Proposition 3.3. Let α : {1, 2, …, M} → Σ and a_{i}, a_{j} ∈ A. Let π = (k_{1}, a_{ℓ_{1}}) (k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}) be an ideal path from a_{i} to a_{j} in α. Then, for each m ∈ {1, 2, …, n−1}, π_{m} = (k_{1}, a_{ℓ_{1}}) (k_{2}, a_{ℓ_{2}}) ⋯ (k_{m}, a_{l_{m}}) is an ideal path from a_{i} to a_{ℓ_{m}}.

Proposition 3.4. Let α : {1, 2, …, M} → Σ and a_{i}, a_{j} ∈ A. If latest_{a_{j}}(α, a_{i}) ≠ 0 then there is a unique ideal path π : a_{i} ⇝ a_{j} in α.

A vertical edge in the timing diagram for α which lies on some ideal path is said to be live. Formally, we have:

Definition 3.5. Let α : {1, 2, …, M} → Σ and k ∈ {1, 2, …, M}. k is live in α for a_{i} ∈ A iff there exists a_{j} ∈ A such π = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{m}, a_{ℓ_{m}}) is the ideal path a_{i} ⇝ a_{j} and k = k_{n} for some n ∈ {1, 2, …, m}.

Let Live_{i}(α) = {k | k is live in α for a_{i}} and Live(α) = ⋃_{i∈{1,2,...,N}} Live_{i}(α).

Proposition 3.6. Let α : {1, 2, …, M} → Σ. ∀i ∈ {1, 2, …, N}. |Live_{i}(α)| ≤ N−1. So there are at most N(N−1) live communications in α.

Proof. Use Propositions 3.3 and 3.4. ⊓ ⊔

Lemma 3.7. Let α : {1, 2, …, M} → Σ and α′ : {1, 2, …, M+1} → Σ be communication sequences such that α′(M+1) = c for some c ∈ Σ and α′(m) = α(m) for m ∈ {1, 2, …, M}.

Let dom(c) = {a_{i}, a_{j}}. Then the following statements hold:

(i) For a_{k} ∉ {a_{i}, a_{j}}, for all a_{ℓ} ∈ A \ {a_{k}}, if π : a_{k} ⇝ a_{ℓ} is an ideal path in α, then π remains the ideal path a_{k} ⇝ a_{ℓ} in α′.

(ii) For a_{i} and a_{j}, the new ideal paths in α′ are computed as follows. Let a_{k} ∈ A \ {a_{i}, a_{j}} and let π_{ik} : a_{i} ⇝ a_{k} and π_{jk} : a_{j} ⇝ a_{k} be ideal paths in α. Then the ideal paths π′_{ik} : a_{i} ⇝ a_{k} and π′_{jk} : a_{j} ⇝ a_{k} in α′ are given as follows: Either π′_{ik} = π_{ik} and π′_{jk} = (M+1, a_{i})π_{ik}, or π′_{jk} = π_{jk} and π′_{ik} = (M+1, a_{j})π_{jk}.

Proof. Part (i) is immediate, since α′ has no new paths originating at a_{k} for a_{k} ∉ {a_{i}, a_{j}}.

To show part (ii), let a_{k} ∈ A \ {a_{i}, a_{j}}.

Case 1 Suppose that target(π_{jk}) < target(π_{ik}). Then clearly, π_{ik} remains the ideal path a_{i} ⇝ a_{k} in α′. It is also obvious that (M+1, a_{i})π_{ik} is a good path from a_{j} to a_{k}. It is not difficult to show that this is in fact the ideal path a_{j} ⇝ a_{k} in α′.

Case 2 The case target(π_{ik}) < target(π_{jk}) is symmetric to Case 1.

Case 3 The last case is when target(π_{ik}) = target(π_{jk}). Let π_{ik} = (k_{1}, a_{ℓ_{1}}) ⋯ (k_{m}, a_{ℓ_{m}}) and π_{jk} = (k′_{1}, a_{ℓ′_{1}}) ⋯ (k′_{m′}, a_{ℓ′_{m′}}). We know that dom(α(k_{m})) = {a_{ℓ_{m−1}}, a_{ℓ_{m}}} and dom(α(k′_{m′})) = {a_{ℓ′_{m′−1}}, a_{ℓ′_{m′}} }. Since target(π_{ik}) = target(π_{jk}), we have a_{ℓ_{m}} = a_{ℓ′_{m′}} = a_{k} and k_{m} = k′_{m′}. It follows that a_{ℓ′_{m′−1}} = a_{ℓ_{m−1}}.

We “step back” on both π_{ik} and π_{jk} and look at the paths π_{ik}^{m−1} = (k_{1}, a_{ℓ_{1}}) ⋯ (k_{m−1}, a_{ℓ_{m−1}}) and π_{jk}^{m′−1} = (k′_{1}, a_{ℓ′_{1}}) ⋯ (k′_{m′−1}, a_{ℓ′_{m′−1}}). Let a_{ℓ′′} = a_{ℓ_{m−1}} =

a_{ℓ′_{m′−1}}. Then the two paths π_{ik}^{m−1} and π_{jk}^{m′−1} are ideal paths a_{i} ⇝ a_{ℓ′′} and a_{j} ⇝ a_{ℓ′′} in α (by Proposition 3.3) and we induce on the length of the paths.

We argue for the base case, when we reach π_{ik}^{0} or π_{jk}^{0}—i.e., either π_{ik} or π_{jk} becomes empty. Without loss of generality, assume that π_{ik} becomes empty. At this point we have π_{jk}^{m′−m} : a_{j} ⇝ a_{i} in α. We replace the path π_{jk}^{m′−m} with the unit path (M+1, a_{i}) to get a new ideal path (M+1, a_{i})π_{ik} : a_{j} ⇝ a_{k} in α′.

⊓ ⊔

So, agents a_{i} and a_{j} can update their ideal paths purely locally provided they know which of them has the better path to each agent a_{k} ∉ {a_{i}, a_{j}}.

Corollary 3.8. Let α : {1, 2, …, M} → Σ and α′ : {1, 2, …, M+1} → Σ be communication sequences such that α′(M+1) = c for some c ∈ Σ and α′(m) = α(m) for m ∈ {1, 2, …, M}.

Then the following statements hold:

(i) M+1 is live in α′. (ii) Live(α′) ⊆ Live(α) ∪ {M+1}.

Proof. Immediate from Lemma 3.7. ⊓ ⊔

4 Local Analysis

The analysis of the previous section immediately gives us an (unbounded) timestamping algorithm by which agents may locally update ideal paths. Every communication c_{ij} is time-stamped by agents a_{i} and a_{j} with their local times. Each agent a_{i} maintains its ideal paths a_{i} ⇝ a_{k} as a sequence of communications distinguished by the time-stamps given to them. When a_{i} and a_{j} synchronize after α, they first time-stamp the new synchronization action c_{ij}. Let π_{i} : a_{i} ⇝ a_{k} and π_{j} : a_{j} ⇝ a_{k} in α. Both π_{i} and π_{j} end with a communication involving a_{k}. So, the time-stamps given by a_{k} to the last communications in the sequences π_{i} and π_{j} will reveal which is later. Once this is known, the new ideal paths π′_{i} : a_{i} ⇝ a_{k} and π′_{j} : a_{j} ⇝ a_{k} in α′ may be computed, as in the proof of Lemma 3.7.

Our algorithm is a modification of this procedure. When a_{i} and a_{j} synchronize, they label the current communication—this label is chosen from a sufficiently large, but finite, set L. Agents maintain mildly enhanced versions of ideal paths called primary paths (Definition 4.1). To detect if a_{i} has a better ideal path to a_{k} than a_{j}, it suffices to check if some label from the ideal path of a_{j} is present on the primary paths of a_{i} (Lemma 4.3). In other words, a_{i} and a_{j} have only to check for equality of labels along their primary paths to compare their ideal paths.

The main complication is for a_{i} and a_{j} to decide which labels from L are currently in use (i.e., appear along primary paths for other agents) and which may be reused. This is decided by secondary paths maintained by each agent (Definition 4.4, Lemma 4.5). The update of the primary and secondary paths is similar to that of ideal paths and needs no additional information.

Henceforth, we assume we have a set of labels L. Different occurrences of c ∈ Σ in a communication sequence α : {1, 2, …, M} → Σ will be assigned distinct labels from L. In other words, we regard α as an injective map from {1, 2, …, M} to Σ × L. We may regard the set Σ × L as a set of events E. Given an event e = (c, l) ∈ Σ × L, we shall say a_{i} ∈ dom(e) to mean a_{i} ∈ dom(c). Initially we assume that we have a infinite set of distinct labels L = {λ_{1}, λ_{2}, …}. Later we show that it suffices to use a finite set of labels which may be “recycled”.

We now represent a communication sequence α as a sequence of events, i.e., α : {1, 2, …, M} → E. Given a path π = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}), we let σ_{π} denote the sequence of events α(k_{1})α(k_{2}) … α(k_{n}).

Definition 4.1. Let α : {1, 2, …, M} → E be a communication sequence and a_{i} ∈ A. A primary path for a_{i} is a path π = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}) (k_{n+1}, a_{ℓ_{n+1}}) such that for some a_{j}, a_{k} ∈ A we have:

(i) a_{ℓ_{n}} = a_{j} and π_{n} = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}) is the ideal path a_{i} ⇝ a_{j} in α.

(ii) a_{ℓ_{n+1}} = a_{k} and for all m ∈ {k_{n+1}+1, k_{n+1}+2, …, k_{n}}, dom(α(m)) ≠ {a_{j}, a_{k}}.

We say that π is a primary path from a_{i} to a_{j} to a_{k} and denote this by a_{i} ⇝ a_{j} → a_{k}.

So, a primary path a_{i} ⇝ a_{j} → a_{k} is an ideal path π : a_{i} ⇝ a_{j} extended with the most recent c_{jk} communication before and including the point target(π). Notice that the definition above does not rule out the case k_{n+1} = k_{n}.

Example 4.2. In Example 2.4 (see Figure 1), a_{2} ⇝ a_{1} = (6, a_{4})(3, a_{1}). The primary path a_{2} ⇝ a_{1} → a_{3} is given by (6, a_{4})(3, a_{1})(2, a_{3}). On the other hand, a_{2} ⇝ a_{1} → a_{4} = (6, a_{4}) (3, a_{1})(3, a_{4}); i.e., the communication a_{1} → a_{4} in a_{2} ⇝ a_{1} → a_{4} is the same as the last communication in a_{2} ⇝ a_{1}.

Lemma 4.3. Let α : {1, 2, …, M} → E, with π_{i} : a_{i} ⇝ a_{k} and π_{j} : a_{j} ⇝ a_{k} two ideal paths in α, for a_{i}, a_{j}, a_{k} ∈ A. Let σ_{π_{i}} = e′_{1}e′_{2} … e′_{m} and σ_{π_{j}} = e′′_{1}e′′_{2} … e′′_{n}. Then:

(i) target(π_{i}) ≤ target(π_{j}) iff for some e′_{ℓ} ∈ σ_{π_{i}}, e′_{ℓ} also appears on some primary path for a_{j}.

(ii) target(π_{j}) ≤ target(π_{i}) iff for some e′_{ℓ} ∈ σ_{π_{j}}, e′_{ℓ} also appears on some primary path for a_{i}.

Proof. Since the cases (i) and (ii) are symmetric, we prove (i). (⇐): Suppose that for some e′_{ℓ} ∈ σ_{π_{i}}, e′_{ℓ} also appears on some primary path for a_{j}. Then, there is a path ẽ_{1}ẽ_{2} … ẽ_{m′} originating from a_{j} such that ẽ_{m′} = e′_{ℓ}. So, the sequence ẽ_{1}ẽ_{2} … ẽ_{m′−1}e′_{ℓ}e′_{ℓ+1} … e′_{m} corresponds to a path π̃ from a_{j} to a_{k} such that target(π̃) = target(π_{i}). target(π_{j}) must be at least as large as target(π̃) since it is an ideal path a_{j} ⇝ a_{k}. So target(π_{i}) ≤ target(π_{j}) as required. (⇒): Suppose target(π_{i}) ≤ target(π_{j}). We then have to show that for some e′_{ℓ} ∈ σ_{π_{i}}, e′_{ℓ} also appears on some primary path for a_{j}. We proceed by induction on m, the length of π_{i}.

m = 1: Then π_{i} = (k_{1}, a_{ℓ_{1}}). Let π_{j} = (k′_{1}, a_{ℓ′_{1}})(k′_{2}, a_{ℓ′_{2}}) ⋯ (k′_{n}, a_{ℓ′_{n}}). We know that a_{ℓ_{1}} = a_{ℓ′_{n}} and k_{1} ≤ k′_{n}. So, we have a path π′ = π_{j}(k_{1}, a_{i}) from a_{j} to a_{i} such that k_{1} = target(π′).

This means that the ideal path π̃ : a_{j} ⇝ a_{i} is such that k_{1} = target(π′) ≤ target(π̃). Then α(k_{1}) must be the most recent communication c_{ik} before target(π̃). So e′_{1} = α(k_{1}) appears on the primary path a_{j} ⇝ a_{i} → a_{k}.

m > 1: Let π_{i} = (k_{1}, a_{ℓ_{1}}) ⋯ (k_{m}, a_{ℓ_{m}}) and π_{j} = (k′_{1}, a_{ℓ′_{1}}) ⋯ (k′_{n}, a_{ℓ′_{n}}). Inductively assume that our claim holds for all ideal paths of length less than m which originate from a_{i}.

We know that a_{ℓ_{m}} = a_{ℓ′_{n}} = a_{k} and k_{m} ≤ k′_{n}. So, we have a path π′ = π_{j}(k_{m}, a_{ℓ_{m−1}}) from a_{j} to a_{ℓ_{m−1}}.

The timing diagram we have is somewhat like the one in Figure 2.

Let π̃ : a_{j} ⇝ a_{ℓ_{m−1}} in α. Then, we know that k_{m} = target(π′) ≤ target(π̃). Suppose target(π̃) ≤ k_{m−1}. Then, the communication α(k_{m}) must be the

most recent c_{ℓ_{m−1}k} communication before target(π̃)—if there were a more recent communication of this kind, it would appear on the ideal path π_{i}. So, the event e_{m} = α(k_{m}) appears on the primary path a_{j} ⇝ a_{ℓ_{m−1}} → a_{k}.

On the other hand, suppose k_{m−1} < target(π̃). We know that the path π_{i}^{m−1} = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{m−1}, a_{ℓ_{m−1}}) is the ideal path a_{i} ⇝ a_{ℓ_{m−1}}. But target(π_{i}^{m−1}) ≤ target(π̃) and the length of π_{i}^{m−1} is less than m. So, by the induction hypothesis, there is an event in the sequence e′_{1}e′_{2} … e′_{m−1} which occurs on some primary path for a_{j} and we are done.

⊓ ⊔

So, to compare π_{i} : a_{i} ⇝ a_{k} and π_{j} : a_{j} ⇝ a_{k}, we just have to look for events which are common to σ_{π_{i}} and σ_{π′}, for some primary path π′ of a_{j}, or common to σ_{π_{j}} and σ_{π′′}, for some primary path π′′ of a_{i}.

[figure: a_{k} = a_{ℓ_{m}}; a_{ℓ_{m−1}}; a_{i}; a_{j}; k_{m}; •; •; k′_{n}; •; k_{m−1}; •; ⋯; k_{1}; •; k′_{1}; •]

Fig. 2. Timing diagram for Lemma 4.3

In other words, to compare ideal paths, we need only test equality of events. The method works as long as communications in the primary paths are consistently labelled as distinct events. A slight extension of the arguments used in Lemma 3.7 and Corollary 3.8 establishes that communications which become dead (i.e., disappear from all primary paths in the system) do not become live again (i.e., reappear on some agent’s primary paths).

Suppose agents a_{i} and a_{j} can decide that a label λ ∈ L assigned to a previous c_{ij} action is no longer being used—i.e., the event (c_{ij}, λ) is not on a primary path for any agent. Then, λ can be re-used for a later synchronization. Since no “old” copy of (c_{ij}, λ) is present on any primary path, this re-use of λ will not introduce any inconsistency into the procedure for comparing ideal paths.

Definition 4.4. Let α : {1, 2, …, M} → E be a communication sequence and π = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}) a path in α. π is a secondary path for a_{i} ∈ A if we can find agents a_{j}, a_{k}, a_{m} ∈ A such that a_{i} ≠ a_{j}, a_{j} ≠ a_{k} and a_{k} ≠ a_{m}, π is a path from a_{i} to a_{m} and for some n_{j} ∈ {1, 2, …, n−1} the following two conditions are satisfied.

(i) π_{n_{j}} = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n_{j}}, a_{ℓ_{n_{j}}}) is the ideal path a_{i} ⇝ a_{j} in α. (ii) Let α_{n_{j}} : {1, 2, …, k_{n_{j}}} → E—i.e., the prefix of α upto k_{n_{j}}. Then, the path

(k_{n_{j}+1}, a_{ℓ_{n_{j} +1}}) ⋯ (k_{n}, a_{ℓ_{n}}) is the primary path a_{j} ⇝ a_{k} → a_{m} in α_{n_{j}}.

We say that π is a secondary path from a_{i} to a_{j} to a_{k} to a_{m} and denote this by π : a_{i} ⇝ a_{j} ⇝ a_{k} → a_{m}.

Lemma 4.5. Let α : {1, 2, …, M} → E. Suppose e appears on a primary path for a_{j} and a_{i} ∈ dom(e). Then, e appears either on a primary path or a secondary path for a_{i}.

Proof. Suppose e is on a primary path π : a_{j} ⇝ a_{k} → a_{ℓ}. Let π = (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n+1}, a_{ℓ_{n+1}}). Then, for some m ∈ {1, 2, …, n+1}, e = α(k_{m}). So, either a_{ℓ_{m−1}} = a_{i} or a_{ℓ_{m}} = a_{i}. Without loss of generality, we assume that a_{ℓ_{m}} = a_{i}.

Case 1. (m ≤ n): Then (k_{1}, a_{ℓ_{1}})(k_{2}, a_{ℓ_{2}}) ⋯ (k_{n}, a_{ℓ_{n}}), the ideal path a_{j} ⇝ a_{k} in α, passes through a_{i}. This path is shown in Figure 3.

[figure: a_{k} = a_{ℓ_{n}}; a_{ℓ_{m+1}}; a_{i} = a_{ℓ_{m}}; a_{ℓ_{m−1}}; a_{ℓ_{1}}; a_{j}; k_{n}; •; ⋯; k_{m+2}; •; k_{m+1}; •; •; k_{m}; •; •; e; k_{m−1}; •; ⋯; k_{2}; •; k_{1}; •; •]

Fig. 3. Timing diagram for Lemma 4.5

We claim that for some m′ ∈ {1, 2, …, m−1}, e lies on the secondary path a_{i} ⇝ a_{ℓ_{m′}} ⇝ a_{k} → a_{ℓ}. To see this, consider the ideal path π_{ij} : a_{i} ⇝ a_{j} in α. If k_{1} ≤ target(π_{ij}), e lies on the secondary path a_{i} ⇝ a_{j} ⇝ a_{k} → a_{ℓ}. If k_{1} > target(π_{ij}) then, look at π_{iℓ_{1}} : a_{i} ⇝ a_{ℓ_{1}}. We know that target(π_{iℓ_{1}}) < k_{1}— otherwise we would be able to reach the point k_{1} on a_{j} from a_{i}.

If k_{2} ≤ target(π_{iℓ_{1}}) < k_{1}, then e lies on the secondary path a_{i} ⇝ a_{ℓ_{1}} ⇝ a_{k} → a_{ℓ}. On the other hand, if target(π_{iℓ_{1}}) < k_{2}, we look at π_{iℓ_{2}} : a_{i} ⇝ a_{ℓ_{2}} and repeat the analysis for π_{iℓ_{1}}. In the worst case we come upto π_{iℓ_{m−1}} : a_{i} ⇝ a_{ℓ_{m−1}}. We know that target(π_{iℓ_{m−1}}) < k_{m−1} by the above analysis. On the other hand, α(k_{m}) = c_{iℓ_{m−1}}. So we definitely have k_{m} ≤ target(π_{iℓ_{m−1}}) < k_{m−1}. So we must have e lying on the secondary path a_{i} ⇝ a_{ℓ_{m−1}} ⇝ a_{k} → a_{ℓ}. Case 2. (m = n+1): So, a_{i} = a_{ℓ}. Then, a slight modification of the argument put forward for Case 1 yields that e either lies on a secondary path a_{i} ⇝ a_{ℓ_{m′}} ⇝ a_{k} → a_{i} for some m′ ∈ {1, 2, …, n−1} or e lies on the primary path a_{i} ⇝ a_{k} → a_{i}. We omit the details. ⊓ ⊔

So, the number of different copies of an action c_{ij} that can be part of other agents’ primary paths is bounded—by the preceding lemma, each such copy must appear on the primary or secondary paths of a_{i} and a_{j}, which are bounded in length and number. In addition, once a particular c_{ij} event disappears from the primary and secondary paths of a_{i} and a_{j}, these two agents know that the event is not present on any primary path in the system. So, a_{i} and a_{j} can locally decide to recycle the label assigned to that event, knowing that this will not affect the outcome of any comparison in Lemma 4.3. This implies that a finite set of labels suffices.

The algorithm

Let L = {λ_{1}, λ_{2}, …, λ_{K}} be a finite set of labels and let E = Σ × L. We assume that each agent a_{i} ∈ A maintains all primary and secondary paths (starting at a_{i}) as sequences of events. In addition, each agent a_{i} also maintains an immediate history of events H_{i} = {last_{ij} | j ≠ i}, such that for each a_{j} ≠ a_{i}, last_{ij} ∈ E is the most recent event e in a_{i}’s history such that dom(e) = {a_{i}, a_{j}} .

Suppose agents a_{i} and a_{j} synchronize after α. They then update this local information as follows.

(i) Let λ ∈ L be the first label in the sequence λ_{1}λ_{2} … λ_{K} which does not appear in any primary or secondary path for a_{i} or a_{j}. (We assume that L is large enough that we can always do this. See Lemma 4.6 below.) Label the new c_{ij} communication with λ—i.e., the new event is e_{λ} = (c_{ij}, λ).

(ii) Update H_{i} to H′_{i} by setting last_{ij} = e_{λ}. Symmetrically update H_{j} to H′_{j} by

setting last_{ji} = e_{λ}. (iii) Define the new primary paths π′_{ijk} : a_{i} ⇝ a_{j} → a_{k} by π′_{ijk} = e_{λ}last_{jk}, for

each event last_{jk} ∈ H′_{j}. Symmetrically, define the new primary paths π′_{jik}. (iv) For a_{k} ∉ {a_{i}, a_{j}}, update primary paths π_{ikℓ} and π_{jkℓ} using lemmas 3.7 and

4.3. Secondary paths are updated in a similar fashion. Note that the update of the primary or secondary paths follows from the update of ideal path, i.e., Lemma 3.7.

It is not difficult to establish the following bounds on our local data structures.

Lemma 4.6. Let a_{i} ∈ A.

(i) The primary paths of a_{i} can be stored as an E-labelled tree with O(N^{2}) nodes. (ii) The secondary paths of a_{i} can be stored as an E-labelled tree with at most

O(N^{3}) nodes. (iii) It suffices to use O(N) labels in L.

To conclude this section, we formally relate the algorithm provided here to the Theorem in Section 2 that we set out to prove. A local state for a_{i} consists of a E-labelled tree of primary paths and an E-labelled tree of secondary paths for a_{i}. ¿From Lemma 4.6, it follows that the set of possible local states for a_{i} is bounded. Given c_{ij} ∈ Σ, the local function g_{c_{ij}} which computes best_{c_{ij}} is just the one which applies Lemma 4.3 to the local states of a_{i} and a_{j} and compares ideal paths a_{i} ⇝ a_{k} and a_{j} ⇝ a_{k}.

5 Discussion

In this paper, we have demonstrated a finite-state algorithm for keeping track of the flow of information in a system where N agents communicate synchronously.

Our algorithm works on an asynchronous automaton [Z]. Asynchronous automata are closely related to trace theory [Maz], an important language-theoretic model of concurrent systems. Versions of these automata have been used to characterize ω-regular trace languages [GP, DM].

In addition to these connections to trace theory, versions of asynchronous automata are also used in model-checking, where one wants to verify whether a given system’s behaviour corresponds to its specification [GW]. Recently, Thiagarajan [T] has developed an extension of propositional linear-time temporal logic which is interpreted over infinite traces, rather than linear sequences. This logic appears to be quite expressive, while remaining decidable. Our algorithm plays a crucial role in establishing the decidability of Thiagarajan’s logic.

One interesting problem is to try and characterize the functions which are locally computable (Definition 2.1). Another line of work is to extend our approach to deal with (reliable) message-passing systems. We believe this is possible, subject to the assumption that there is an overall bound B on the number of new messages that a_{i} will send to a_{j} without an acknowledgment (direct or indirect) from a_{j}. A report of this extension is in preparation.

Acknowledgments We thank P.S. Thiagarajan for suggesting the problem and for numerous discussions which have helped clean up the presentation.

References

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

[DM] V. Diekert, A. Muscholl: Deterministic asynchronous automata for infinite traces, Proc. STACS ’93, LNCS 665 (1993) 617–628.

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

[GW] P. Godefroid, P. Wolper: A partial order approach to model checking, Proc. 6th IEEE LICS, Amsterdam (1991) 406–415.

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

[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 timestamps suffice, Report TCS-93-3, School of Mathematics, SPIC Science Foundation, Madras, India (1993).

[T] P.S. Thiagarajan: A trace based extension of PTL, Report TCS-93-4, School of Mathematics, SPIC Science Foundation, Madras, India (1993).

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