## self-stabilizing function computation

If we really do not care about time complexity at all, then I suspect the following simpler idea would work. If not, it would benefit the paper to discuss why this idea fails.

The agents can increase counts, as in the paper, through direct interaction of two agents with the same input. For example, suppose we have input alphabet $\{a,b,c\}$. Fix $k$ to be the maximum count in any root set. Then for agents with input $a$, we have transitions

$a,a \to a_2,a$

$a_2,a_2 \to a_3,a_2$

$a_3,a_3 \to a_4,a_3$

...

$a_{k-1},a_{k-1} \to a_k,a_{k-1}$

$a_i \to a$ (for all $2 \leq i \leq k$)

for agents with input $b$,

$b,b \to b_2,b$

$b_2,b_2 \to b_3,b_2$

$b_3,b_3 \to b_4,b_3$

...

$b_{k-1},b_{k-1} \to b_k,b_{k-1}$

$b_i \to b$ (for all $2 \leq i \leq k$)

and similarly for $c$:

$c,c \to c_2,c$

$c_2,c_2 \to c_3,c_2$

$c_3,c_3 \to c_4,c_3$

...

$c_{k-1},c_{k-1} \to c_k,c_{k-1}$

$c_i \to c$ (for all $2 \leq i \leq k$)

The final transition ($a_i \to a$) in each case occurs with some probability on every transition with any agent. The goal of this is to eliminate false counts from the initial population. Any fair execution will eventually reset all $a_i$'s to $a$, and after that, $a_j$ is producible if and only if the number of $a$'s in the population is at least $j$, and similarly for $b$ and $c$.

Suppose for concreteness that our goal is to detect if root set $R_1 = \{5a,4b,3c\}$ is a subset of the population. Eventually, this is true if and only if $a_5$, $b_4$, and $c_3$ are producible. To allow one agent to learn that these states exist simultaneously in the population, we can add transitions to each agent that represent each of the Boolean values

$\phi_{a_5} =$ "I have seen an $a_5$"

$\phi_{b_4} =$ "I have seen a $b_4$"

$\phi_{c_3} =$ "I have seen a $c_3$"

These bits switch to true upon encountering the correct agent, i.e.,

$\phi_{a_5}=F,a_5 \to \phi_{a_5}=T,a_5$

$\phi_{b_4}=F,b_4 \to \phi_{b_4}=T,b_4$

$\phi_{c_3}=F,c_3 \to \phi_{c_3}=T,c_3$

But true values can spontaneously fall back to false, in order to clear out erroneous information from the initial configuration (which any fair execution will do):

$\phi_{a_5}=T \to \phi_{a_5}=F$

$\phi_{b_4}=T \to \phi_{b_4}=F$

$\phi_{c_3}=T \to \phi_{c_3}=F$

For other root sets, we have similar variants of these Booleans, but marked specific to that root set.

Once all $\phi$ values are false, and all count values are $1$, only the true root set is detectable, and any fair execution will eventually detect it by executing the transitions above in the proper order.

## Suggestion for exposition to help explain and justify $O(\log n)$ time protocol (SSLE)
I suspect that another algorithm is intermediate in complexity between this algorithm and Algorithm 1, and that explaining this algorithm would help to see the idea of the new algorithm.

In Algorithm 1 each agent stores a sync bit with every other agent, in a table of $n$ bits (let's call this $A$.sync in agent $A$, with $n-1$ entries). Perhaps this can be extended slightly, to additionally have each agent store the entire sync table of the other agent as well, and as you suggest, store more than a single bit, such that it is very unlikely to generate the same sync value twice in a row (let's call this $A$.other_sync, with $(n-1)(n-2)$ entries, one for each pair of agents not including $A$).

In other words, when $A$ and $B$ talk, they not only agree on a sync value between $A$ and $B$, but they share the sync values that they have with every other agent as well. This might be similar to the idea of Section 3.4, but restricted to paths of length 2.

Then the idea is that when $B$ talks with $C$, $B$ and $C$ share information about their sync values; in particular, with regard to agent $A$, $B$ tells $C$ "here's my current sync value with $A$". $C$ stores this in $C$.other_sync[$A,B$].

Suppose the following is the order of interactions, and some information they record in the interaction (except the last row, which just shows information already recorded from previous interactions):

| interaction | information shared (=) or changed ($\leftarrow$) |
|---|---|
| $B$-$C$ | $B$.sync[$C$] $\leftarrow$ 456, $C$.sync[$B$] $\leftarrow$ 456 |
| $A$-$B$ | $A$.sync[$B$] $\leftarrow$ 123, $B$.sync[$A$] $\leftarrow$ 123, $A$.other_sync[$B,C$] $\leftarrow$ 456 |
| $B$-$C$ | $B$.sync[$C$] $\leftarrow$ 789, $C$.sync[$B$] $\leftarrow$ 789, $C$.other_sync[$A,B$] $\leftarrow$ 123 |
| $A$-$C$ | $A$.sync[$B$] = 123, $C$.other_sync[$A,B$] = 123, $C$.sync[$B$] = 789, $A$.other_sync[$B,C$] = 456 |

In the final interaction, $A$ sees that its sync value with $B$ ($A$.sync[$B$] = 123), matches what $C$ thinks is the $A$-$B$ sync value ($C$.other_sync[$A,B$] = 123). This is guaranteed to be true whenever the order of interactions is as above.

$C$ sees that its sync value with $B$ ($C$.sync[$B$] = 789), does *not* match what $A$ thinks is the $B$-$C$ sync value ($A$.other_sync[$B,C$] = 456). However, this doesn't mean that there is a name collision, merely that $B$ and $C$ generated a new sync value since the last time $A$ and $B$ talked. $A$ realizes that this can be explained by the relative order of interactions (not by a name collision), so $A$ simply updates $A$.other_sync[$B,C$] to be the new value 123 it got directly from $C$.

So in other words, because one of those two values matched, the agents assume no collision, and they interpret the mismatch between the other pair of values to be due to the relative order of interactions. But suppose there is a ghost name, i.e., another $A$, called $A'$. Then it would be possible to have the following order of interactions

1. $B$-$C$
2. $A$-$B$
3. $A'$-$B$
4. $B$-$C$
5. $A$-$C$
> [name=Eric] This doesn't work as the contradiction we can detect in $\Theta(n^{1/3})$ time, though, since $B$ is meeting both $A$ and $A'$ (see the case I describe at the bottom)

Now, we are no longer guaranteed that $A$.sync[$B$] = $C$.other_sync[$A,B$], and in fact if the set of sync values is large enough, it's very low probability. This is because $A$ wrote down a sync value (say 123) in interaction 2, but then $B$ generated a new sync value with $A'$ (say, 765) in interaction 3, which it tells to $C$ (storing it in $C$.other_sync[$A,B$]) in interaction 4. When $A$ and $C$ interact, they see that $A$.sync[$B$] $\neq$ $C$.other_sync[$A,B$], but also $C$.sync[$B$] $\neq$ $A$.other_sync[$B,C$] = 456. At most one of these two inequalities is explained by the relative order of interactions. The other is only due (except with probability $1/k$, where $k$ is the number of sync values) to the presence of a second agent with $A$'s name.
> [name=Eric]what is the exception case? It seems to be like if all names are truly unique, there is an invariant that this double inequality cannot happen. This is essential to show that it stabilizes. The failure probability is just that A' and A are not distinguished.

This exposition might be a good introduction to help explain the algorithm of Section 3.4. It should have time complexity $O(n^{1/3})$, since it will take that much time for $A$ to talk to $\Theta(n^{1/3})$ agents, and then it will take that much time for each of them to talk to $\Theta(n^{1/3})$ agents, which is $\Theta(n^{2/3})$ total agents that interacted with an agent that interacted with $A$. Once there are $\Theta(n^{2/3})$ such agents, $A$ meets one of them in expected time $O(n^{1/3})$.

Then the full algorithm could be explained as extending this idea to longer paths than length 2. But a full description of this intermediate algorithm might help immensely to understand the faster algorithm, and also would help to develop some terminology to explain and prove correctness of the $O(\log n)$ time algorithm.

> [name=Eric] Here's a case for how we detect a name collision between $A$ and $A'$ in $\Theta(n^{1/3})$ time

1. $A$-$B$
2. $B$-$C$
3. $C$-$D$
4. $A'$-$D$

Assume all sync bits are intialized to $0$.

| interaction | information shared (=) or changed ($\leftarrow$) |
|---|---|
| $A$-$B$ | $A$.sync[$B$] $\leftarrow B$.sync[$A$] $\leftarrow$ 123 |
| $B$-$C$ | $B$.sync[$C$] $\leftarrow C$.sync[$B$] $\leftarrow$ 456, $C$.other_sync[$A,B$] $\leftarrow$ 123 |
| $C$-$D$ | $C$.sync[$D$] $\leftarrow D$.sync[$C$] $\leftarrow$ 789, $D$.other_other_sync[$C$.other_sync[$A,B$]] $\leftarrow$ 123, |
| $A'$-$D$ | $A'$.sync[$B$] $\neq$ $C$.other_sync[$A,B$] and $A'$.other_sync[$B,C$] $\neq$ $C$.sync[$B$] detects the name collision|

$D\to^{789} C \to^{456} B \to^{123} A$

$A \to^{123} B \to^{\epsilon} C \to^{\epsilon} D$

consistent with

$A$-$B$ (123)

$B$-$C$ (456)

$C$-$D$ (789)

$A$-$D$

another valid case: ($A$ later met $B$ again)

$D \to^{789} C \to^{456} B \to^{123} A$

$A \to^{321} B \to^{456} C \to^{987} D$

consistent with

$C$-$D$ (987)

$A$-$B$ (123)

$B$-$C$ (456)

$A$-$B$ (321)

$C$-$D$ (789)

$A$-$D$

another valid case: ($A$ later met $B$ again, *and* $B$ later met $C$)

$A \to^{849} B \to^{654} C \to^{789} D$

consistent with

$A$-$B$ (123)

$B$-$C$ (456)

$C$-$D$ (789)

$A$-$B$ (849)

$B$-$C$ (654)

$A$-$D$

another valid case: ($A$ later met $B$ again and got same value, *and* $B$ later met $C$ and got same value, low probablity but possible)

$C$-$D$ (987)

$B$-$C$ (456) ($C$ tells $B$ that $C$'s sync with $D$ is 987)

$C$-$D$ (789)

$A$-$B$ (321)

$A$-$D$

$A \to^{321} B \to^{456} C \to^{987} D$

invalid case:

$A \to^{849} B \to^{654} C \to^{987} D$