Brief Announcement: Adaptive Self-Organization in Anonymous Dynamic Networks

We consider synchronous dynamic networks comprising a fixed set of nodes. Nodes communicate with each other via message passing over a communication graph whose topology changes over time. Following the standard time-varying graphs formulation [1], we assume an adversary controls which edges are present in each round, restricted only by 1-interval connectivity; i.e., the topology may change arbitrarily between rounds so long as the corresponding snapshots are connected. Nodes are anonymous, lacking unique identifiers, and – unless explicitly stated otherwise – have no knowledge or approximation of any global measure, including the number of nodes $n=|V|$.¹¹1We emphasize that allowing $𝒪(\log n)$ memory per node, as our algorithm does, is not the same as having a priori knowledge of $n$. Such an equivalence would, among other undesirable consequences, trivialize the deep technical literature on exact counting in anonymous dynamic networks [12, 7, 6, 3, 2, 11, 4, 5]. We further assume that nodes are port-indistinguishable; i.e., they cannot count or locally distinguish among their neighbors. Consequently, when a node communicates with its neighbors via message passing, it must send the same message to all its current neighbors. Algorithms execute synchronously, with each round comprising a communication phase followed by a state transition phase (see Figure 1).

In each round $t$, the environment – represented by a signal adversary – emits one of $k$ distinct signals $s_t\in \{1,\mathrm{\dots },k\}$ or no signal at all, denoted by $s_t=\perp$. We assume that the number of signals is a fixed constant $k$, independent of $n$. Any signal $s_t\ne \perp$ is perceived by a non-empty set of witnesses $W_t\subseteq V$ chosen by the signal adversary. Thus, whether a signal exists in the system, which signal is emitted, and what nodes witness an emitted signal may all change arbitrarily and independent of each other between rounds. A signal $s_t\in \{\perp ,1,\mathrm{\dots },k\}$ is persistent if $s_{t^{\prime }}=s_t$ for all rounds $t^{\prime }\ge t$ (though its witnesses may still change).

Each node may change its color over time to indicate its fluctuating response to different signals (or lack thereof). Formally, we denote by $c_t(v)\in \{1,\mathrm{\dots },\mathrm{\ell }\}$ the color of node $v\in V$ at time $t$ (i.e., at the start of round $t$) and by $C_t(i)$ the number of nodes at time $t$ with color $i$. We assume the number of colors $\mathrm{\ell }$ is a fixed constant, independent of $n$.

Let $F_{\mathrm{\ell }}=\{(f_1,\mathrm{\dots },f_{\mathrm{\ell }})\in {\mathbb{Q}}^{\mathrm{\ell }}\mid {\sum }_{i=1}^{\mathrm{\ell }}{f}_i=1\text{ and }{f}_i\ge 0,\forall i\}$ be all fractional probability distributions over the $\mathrm{\ell }$ colors. An instance of the adaptive self-organization problem takes the form of a response function $r:\{\perp ,1,\mathrm{\dots },k\}\to F_{\mathrm{\ell }}$ mapping each distinct signal and the absence of a signal to a goal distribution over colors. Informally, if a signal (or lack thereof) $s$ is persistent, the nodes must collectively change their colors to reach and remain in a distribution approximating $r(s)$. Formally, suppose a signal $s$ becomes persistent at time $t_0$. An algorithm execution stabilizes (w.r.t. signal $s$) if there exists a time $t_1\ge t_0$ such that $c_t(v)=c_{t-1}(v)$ for all times $t>t_1$ and nodes $v\in V$. A dynamic network configuration approximates a goal distribution $r(s)$ at time $t$ if its nodes’ color frequencies $C_t/n$ satisfy

where $\epsilon (n)$ is an error term satisfying ${lim}_{n\to \mathrm{\infty }}\epsilon (n)=0$. An algorithm solves an instance $r$ of adaptive self-organization if, for all sufficiently large $n$, every execution stabilizes w.r.t. any persistent signal $s$ in a configuration approximating $r(s)$.

Adaptive self-organization is fundamentally a communication problem in that nodes disseminate local knowledge (i.e., the presence and type of signal they witness) to coordinate the appropriate response across an entire dynamic network. But related works on broadcast [13, 15, 10], $k$-token dissemination [9, 8], and aggregate computation [12, 7, 6, 3, 2, 11, 4, 5] in anonymous dynamic networks are not directly applicable here. Unlike most algorithms which use progress as a structural feature – e.g., tracking informed vs. uninformed nodes in broadcast or local symmetries that remain to be broken in aggregate computation – our problem allows signals to change or disappear at any moment, suddenly requiring past progress be undone in pursuit of a different goal. In this sense, our algorithms feature a kind of self-stabilization, though our concern is achieving continuously changing goals from in-progress configurations rather than recovering from arbitrary corruption of node memory.

Most relevant to our work is Oh, Randall, and Richa’s recent results on “adaptive collective responses” which are also driven by local stimuli and operate on anonymous dynamic networks [14]. If a stimulus (resp., no stimulus) is witnessed for sufficiently long, they desire for all nodes to become Aware (resp., Unaware), akin to a one-signal, two-color, homogeneous version of our problem. In their randomized solution, witnesses continuously generate “alert” tokens that spread through the network using degree-weighted random walks and cause nodes they reach to become Aware. Whenever a node stops witnessing stimuli, it broadcasts an “all clear” token that causes other nodes to become Unaware. This algorithm solves the problem in constant memory, $𝒪(n^2)$ expected time for becoming Unaware, and $𝒪(n^6\log n)$ expected time for becoming Aware. But they make several assumptions that are incompatible with ours: (1) their scheduler sequentially activates nodes uniformly at random while we assume synchrony, (2) they restrict dynamics such that each Aware node’s set of Aware neighbors always form a connected component while we assume standard 1-interval connectivity, (3) they assume the number of active stimulus locations and the dynamic degree are both upper bounded by constants known to the nodes a priori while we make no such assumptions, and (4) they guarantee all nodes will become Aware if the stimuli remain unchanged for sufficiently long while we allow the number and locations of stimuli to change arbitrarily so long as at least one stimulus is present anywhere in the network for sufficiently long. In comparison, our algorithms solve a more general formulation of the problem under more standard assumptions in optimal time, but require logarithmic memory.

We first prove that the only instances of adaptive self-organization that can possibly be solved by deterministic algorithms are those with homogeneous goal distributions, i.e., those in which all nodes stabilize with the same color. Formally, an instance $r:\{\perp ,1,\mathrm{\dots },k\}\to F_{\mathrm{\ell }}$ of adaptive self-organization is homogeneous if for each signal $s\in \{\perp ,1,\mathrm{\dots },k\}$, there exists a color $c_s\in \{1,\mathrm{\dots },\mathrm{\ell }\}$ such that $r(s,i)=1$ if $i=c_s$ and $0$ otherwise. An instance $r$ is non-homogeneous otherwise, i.e., if there exists a signal $s$ whose distribution $r(s)$ places non-zero probability mass on multiple colors. The following impossibility result follows from the interaction of highly-symmetric topologies and port-indistinguishable message passing.

Theorem 1 shows that deterministic algorithms can only hope to solve homogeneous instances of adaptive self-organization. The deterministic algorithm we present next solves exactly these instances. Its performance guarantees are given by the following theorem.

A naïve approach to homogeneous adaptive self-organization would have all witness nodes for a signal $s$ continuously send messages indicating this fact, causing nodes that receive these messages to change their color to $c_s$ (i.e., the color with $r(s,c_s)=1$). This flooding approach works if signals and their witnesses never change, but fails as soon as nodes must locally resolve conflicting evidence about which signal is currently in the system, if any.

We address this challenge by assigning every message a time-to-live value ttl that is initialized as some maximum value max-ttl by witness nodes. A message is forwarded (with a decremented ttl) if and only if it has the largest ttl value among all received messages, thus reflecting something about the temporal distance between the recipient node and the closest originating witness. If signals ever disappear from the network (i.e., $s=\perp$ is persistent), there will be no witnesses to send new messages with $\text{ttl}=\text{max-ttl}$, so eventually all messages will expire, causing nodes to “reset” their color to the baseline color $c_{\perp }$. If instead one signal $s$ is replaced by another signal $s^{\prime }$, messages about $s^{\prime }$ will have higher ttl values than – and thus preempt – any messages about $s$ that are still being propagated.

It remains to define a mechanism that eventually finds an max-ttl value that is large enough for messages to reach all nodes in the network (i.e., at least the temporal eccentricity of any witness) but does not grow indefinitely. We distinguish between three node state values, loosely interpreted as: (1) Reset nodes that either do not believe a signal is present in the system or are otherwise not participating in forwarding messages, (2) Set nodes that are participating in forwarding messages and have set their color accordingly, and (3) Locked nodes that believe their color correctly represents the current signal present in the system. Set nodes use a variable timer to count rounds from zero up to max-ttl, effectively waiting until the broadcast they are participating in reaches its furthest extent, at which point they become Locked. If ever a non-Locked node receives a message from a Locked node, it knows max-ttl was not large enough; this recipient thus doubles its max-ttl value and resets itself, ultimately initiating a new broadcast with double the reach. Otherwise, if no such recipient exists, all nodes must be Locked with the desired color.

The statement of Theorem 2 differentiates between two types of convergence: strong and weak. A network strongly converges in $r$ rounds if, within $r$ rounds of a persistent signal appearing, every node adopts and remains the corresponding color. On the other hand, a network weakly converges in $r$ rounds if, from the time a persistent signal appears, there are at most $r$ (not necessarily consecutive) rounds in which any node does not have the corresponding color. Weak convergence for present signals $s\ne \perp$ arises from the fact that the dynamics adversary can keep eccentricities – and, by extension, max-ttl values – small for arbitrarily long periods of time. If the adversary suddenly increases witness eccentricities, some node that is “far” from a witness may now have its ttl expire, causing it to incorrectly reset to color $c_{⟂}$ despite a signal being present in the network. This isn’t a correctness issue – such nodes will eventually double their max-ttl value until the network once again stabilizes at the correct color – but it creates intermediate periods of restabilization. If nodes had knowledge of $n=|V|$, this situation could be avoided entirely by initializing $\text{max-ttl}=n$, which always upper bounds eccentricity. In this case, ttl values will never expire with a signal present, ensuring strong convergence.

Theorems 1 and 2 show that deterministic algorithms can only solve homogeneous instances of adaptive self-organization and then gives a deterministic algorithm for exactly these instances. We conclude with a simple, randomized extension of the deterministic algorithm that solves any instance of adaptive self-organization w.h.p., homogeneous or otherwise: now, whenever a node updates its signal, it samples a new color from the goal distribution $r(\text{signal})$.