Brief Announcement: Synchronization in Anonymous Networks Under Arbitrary Dynamics

Modern distributed systems, such as wireless sensor networks, mobile peer-to-peer systems, and biologically inspired swarm networks, often exhibit constantly changing and unpredictable communication dynamics that make achieving coordinated behavior between agents challenging, even for simple tasks. Achieving coordinated behavior in such a setting can be further compounded by asynchrony and agent anonymity (no identifiers). To simplify the design of distributed algorithms, researchers developed synchronizers that can transform algorithms designed under strong synchrony assumptions into algorithms that work correctly under weaker assumptions [2, 19, 15]. Previous work on synchronizers considers systems in which agents have unique identifiers and the network is either static or is dynamic for some time but eventually stabilizes. In contrast, this paper considers a system of anonymous agents that communicate through a network with arbitrary dynamics, i.e., with no restrictions on topological changes, including no assumptions on eventual (local or global) stabilization.

In such networks, three different synchrony models are considered [13]. In the synchronous model, time is divided into stages and all nodes are active in every stage. In the semi-synchronous model (see, e.g., [14]), time is also divided into stages, but some nodes might not be active in a given stage. In both models, an active node executes one action – which involves communication with their neighbors and a bounded amount of computation – per stage, and topology changes occur only at the beginning of a stage. In other words, the semi-synchronous mode is one where time is synchronous but nodes are activated asynchronously. In the asynchronous model, there is no synchronization of time nor node activations, so actions can take an arbitrary bounded amount of time to execute, and topological changes and node activations can happen at arbitrary times.

In this paper, we introduce our Arbitrary-Dynamics Synchronizer, or $\delta$-Synchronizer for short. The $\delta$-Synchronizer is the first deterministic synchronizer that allows algorithms designed for a synchronous anonymous network with arbitrary adversarial dynamics to execute correctly in a semi-synchronous anonymous, arbitrary dynamics network under a weakly-fair node activation scheduler. Specifically, our $\delta$-Synchronizer transforms any algorithm ${𝒜}_{sync}$ designed for a synchronous dynamic network under arbitrary edge-dynamics given by a time-varying graph ${𝒢}_{sync}$ into an algorithm ${𝒜}_{semi}$ that correctly simulates ${𝒜}_{sync}$ under a weakly-fair scheduler in a semi-synchronous dynamic network under arbitrary edge-dynamics given by a time-varying graph ${𝒢}_{semi}$.

Unlike other synchronizers that assume eventual stabilization and for which one can compare executions of the original algorithm and the transformed algorithm on the same stabilized network, in our setting, there is no guarantee that the network ever stabilizes and there is no guarantee that ${𝒢}_{sync}$ and ${𝒢}_{semi}$ are identical, which should not be surprising. This necessitates a non-triviality requirement on synchronizers for networks with arbitrary dynamics. The overall requirements for such synchronizers are captured by the following three general conditions (in bold), which we then indicate how they are satisfied by our $\delta$-Synchronizer. We formalize our guarantees in Section 4.

• $\mathrm{■}$

  (Correctness) The simulated synchronous execution is valid: We show that for any ${𝒢}_{semi}$ and $i\ge 0$, there exists a ${𝒢}_{sync}$ such that the state of each node at the end of phase $i$ (where phases are maintained by the synchronizer) of the semi-synchronous execution of ${𝒜}_{semi}$ under ${𝒢}_{semi}$ and a weakly-fair scheduler is equal to the state of each node at the end of $i$-th step of a synchronous execution of ${𝒜}_{sync}$ under ${𝒢}_{sync}$. (Theorem 1)

• $\mathrm{■}$

  (Non-triviality) Every possible outcome of a synchronous execution can be simulated: We show that for any ${𝒢}_{sync}$ and $i\ge 0$, there exists a ${𝒢}_{semi}$ such that the state of each node at the end of step $i$ of the synchronous execution of ${𝒜}_{sync}$ under ${𝒢}_{sync}$, is equal to the state of each node at the end of phase $i$ in a semi-synchronous execution of ${𝒜}_{semi}$ under ${𝒢}_{semi}$ and a weakly-fair scheduler. (Theorem 2)

• $\mathrm{■}$

  (Finite termination) If the synchronous algorithm always terminates in finite time, so do the simulated executions: We show that the synchronous execution of ${𝒜}_{sync}$ terminates in finite time for ${𝒢}_{sync}$ if and only if the semi-synchronous execution of ${𝒜}_{semi}$ terminates in finite time for ${𝒢}_{semi}$, which implies the condition. (Theorem 3)

While the non-triviality requirement rules out trivial solutions, e.g., in which ${𝒢}_{semi}$ always contains no edges regardless of the actual dynamics, our transformation actually satisfies a strong non-triviality requirement: Any edge $(u,v)$ that persists long enough for both nodes $u$ and $v$ to be activated at least once during a phase $i\ge 0$ of the semi-synchronous execution must be part of ${𝒢}_{sync}$ during the $i$-th step of the synchronous execution. In particular, if ${𝒢}_{semi}$ is static, then the simulation guarantees that ${𝒢}_{sync}={𝒢}_{semi}$.

We assume the Pull model of communication (see, e.g., [9]), with the addition of a disconnection detector, as in [12], and a 1-bit multi-writer atomic register at each edge-port. The $\delta$-Synchronizer operates with an asymptotic memory overhead that is logarithmic on the number of nodes provided that the underlying synchronous algorithm terminates in polynomial time [7]. We present applications and discuss future work in Section 5, and summarize the most relevant related work in Table 1.

We consider an edge-dynamic network that we formalize using a time-varying graph [10]. A time-varying graph is represented as $𝒢=(V,E,T,\rho )$ where $V$ is the set of nodes, $E$ is a (static) set of undirected pairwise edges between nodes, with a lifetime $T\subseteq \mathbb{N}$. A presence function $\rho :E\times T\to \{0,1\}$ indicates whether or not a given edge exists at a given time. We define a snapshot of $𝒢$ at time $t$ as the undirected graph $G_t(V,E_t)$, where $E_t=\{e\in E:\rho (e,t)=1\}$. At any time, we denote the neighborhood of a node $u\in V$ by $N(u)$. For $t\ge 0$, the $t$-th stage lasts from time $t$ to the instant just before time $t+1$; thus, the communication graph in stage $t$ is $G_t$.

We assume that each node is equipped with a mechanism to detect disconnections on its ports [12, 16, 18]. When an edge connected to a node $u$ is disconnected, the disconnection detector adds the corresponding port label to a temporary set $D$. The set $D$ is reset to $\mathrm{\varnothing }$ at the end of each activation of $u$. To ensure anonymity among nodes and their neighbors, each node $u$ associates with its neighbors through port labels $\mathrm{\ell }$, noting that different nodes may connect to $u$ through the same port over time, and that a node may connect at different ports of $u$ over time (respecting that at most one node is connected to any port at any point in time). Each edge $(u,v)$ is assigned specific ports at both nodes $u$ and $v$. For convenience, we use $u.x$ to denote the value of variable $x$ at node $u$.

An algorithm, including the synchronizer, is composed of multiple actions of the form $⟨label⟩:⟨guard⟩\to ⟨operations⟩$. An action is enabled if its guard (a boolean predicate) evaluates to true, and a node is said to be enabled if it has at least one enabled action. The scheduler controls the stages when an enabled node is activated and picks exactly one enabled action at the node to execute at the given stage. Our synchronizer algorithm will ensure that we only have one enabled action per node at any stage $t$.

We assume the Pull model of communication (see, e.g., [9]), where every time a node $u$ is activated at a stage $t$, $u$ can pull the state information of a neighboring node $v$. In [7], we show that the classic Pull (or Push) model is not powerful enough to support synchronization. Thus, we further equip the Pull model with a 1-bit multi-writer atomic register at each edge-port, and allow an activated node $u$ at stage $t$ to perform one atomic write onto each multi-writer register of any neighbor node $v$ such that $(u,v)\in E_t$ during the stage. Each action follows the Read-Compute paradigm, where these two components are executed in this order in lockstep (and writes occur within the compute cycle).

We focus on semi-synchronous concurrency, where in each stage, any (possibly empty) subset of enabled nodes is activated concurrently, under arbitrary topological changes. To model this, we assume two adversaries, an adaptive adversary that controls the edge presence function at each stage (i.e, controls the edge dynamics), and the scheduler adversary – or simply the scheduler – that controls when nodes are activated. We assume a weakly fair scheduler that activates nodes such that any continuously enabled node is eventually activated (or equivalently, that every enabled node will be activated infinitely often).

The $\delta$-Synchronizer (Algorithm 1) consists of two actions, Handshake and ExecuteSynch, with exactly one of them being enabled for a node at any stage. Recall that the synchronizer works by showing the equivalence between a semi-synchronous execution of $\delta$(${𝒜}_{sync}$) under an arbitrary dynamic network ${𝒢}_{semi}=\{G_0,G_1,\mathrm{\dots }\}$ and a synchronous execution of ${𝒜}_{sync}$ under a (potentially different) arbitrary dynamic network ${𝒢}_{sync}=\{H_0,H_1,\mathrm{\dots }\}$.

Each node $u$ keeps a local counter, $u.\mathrm{𝚙𝚑𝚊𝚜𝚎}$, of the phase number it is simulating and updates it when the simulation of the phase completes and an action of ${𝒜}_{sync}$ is executed (Lines 27-28). During the handshake for the simulation of phase $i$, a node $u$ maintains a set of potential neighbors (identified by the ports to which they are connected) to be included as neighbors in the simulated execution, which is initially equal to the set $u.P$ of all valid neighbors at the start of the handshake, when $u.\mathrm{𝚜𝚢𝚗𝚌𝚑}=\mathrm{𝟶}$. The set of potential neighbors can “lose” elements in other stages of the handshake for phase $i$ due to edge disconnections, but does not gain new elements. The crucial property to maintain is edge consistency: At the end of the simulation of phase $i$, the final set of neighbors of $u$, $u.F$, which is a subset of $u.P$, contains node $v$ if and only if the set $v.F$ contains node $u$. The sets $u.F$, for all nodes $u\in V$, determine the set of (undirected) edges in the simulated graph $H_i$ for phase $i$.

Initially, the set $u.P$ contains the following nodes:

1.

(Running behind) Neighbors that have not yet started simulating phase $i$. These nodes can be included because node $u$ will wait for them to catch up during the next stages in $u$’s handshake for phase $i$ (unless they disconnect from node $u$),

2a.

(Concurrent nodes in initialization stages) Neighbors that have started simulating phase $i$ but have not yet finished the initialization stage of the handshake. These nodes will also be able to see that node $u$ has not yet finished its initialization stage of the simulation.

2b.

(Concurrent nodes past initialization stages) Neighbors that completed the initialization of the simulation of phase $i$ and are still considering node $u$ as a neighbor in their handshake of phase $i$. These nodes must have started the handshake of phase $i$ before node $u$ but have not detected a disconnection in the edges linking them to node $u$.

To calculate the set $u.P$, a node pulls information from its neighbors and determines which nodes fall into one of the categories above (Lines 7–10). At the end of the first stage of the handshake, node $u$ sets its synch flag to 1 to signal the end of its initialization for phase $i$.

To ensure edge consistency, each node $u$ keeps track of all ports that have experienced a disconnection since the start of the simulation of phase $i$ in its set $u.\tilde{D}$ (initially empty). All neighbors connected through ports in $u.\tilde{D}$ are removed from consideration to be included in the simulated graph $H_i$. Indeed, if there is a disconnection of an edge $(u,v)$ in a given stage, then nodes $u$ and $v$ will each add the respective port connected to edge $(u,v)$ to its own set $\tilde{D}$ in the first stage in which the node is active after the disconnection, and the edge $(u,v)$ will not be included in the simulated graph $H_i$ by either node. Since nodes are anonymous, any edge that later connects to the port of either $u$ or $v$ earlier connected to $(u,v)$ – including, potentially, a reconnection of $u$ and $v$ – will be ignored in phase $i$.

A node $u$ checks if the neighbors running behind in the simulation have caught up to phase $i$ (Line 14) or, if the neighbor $v$ has caught up, $u$ only needs to update the respective ack value (since it already pulled the state information from $v$ for phase $i$ the last time it pulled from $v$ in Line 15). Note that when the check is done in Line 14, if the neighbor is not behind, it must be simulating the same phase: The reason is that if the node was previously behind it could not have advanced beyond phase $i$ without first executing the ack/block exchange and the first (and only) time that is done is when the two nodes are in phase $i$.

A node $u$ completes the handshake of phase $i$ when it determines that all edges linking it to a tentative neighbor in $u.P\setminus u.\tilde{D}$ are blocked (Line 25), implying that such an edge $(u,v)$ will be considered to be in $H_i$ by both $u$ and $v$. The blocking of such an edge $(u,v)$ can be initiated by $u$ itself or by node $v$, but in either case it will result in the block flags on the respective ports at $u$ and $v$ being set to 1 during the current stage (while the edge is up). Whichever node blocks the edge-ports, say $u$, must have detected that the other node ($v$) set its ack to 1 (Lines 20-22), acknowledging that $u$ and $v$ are both simulating phase $i$, and that $v$ has pulled $u$’s phase $i$ state information prior to the blocking ($u$ has also pulled $v$’s phase $i$ state during the current stage). Note that there are blocked edges in phase $i$ that disconnect later in the phase: Those edges will be in the respective sets $F$ and thus also in $H_i$.

Theorems 1–3, whose proofs appear in [7], ensure that the $\delta$-Synchronizer satisfies the three conditions outlined in Section 1. The ${𝒜}_{sync}$-state of node $u$ consists of the variables of $u$ that directly pertain to the state variables of ${𝒜}_{sync}$.

Designing algorithms for highly dynamic networks without any assumptions on edge dynamics or eventual stabilization is challenging, even in synchronous settings. On the other hand, scenarios with high and unpredictable network dynamics are getting increasingly more common in practice, and practitioners are looking at the benefits of time synchronization in order to better manage the dynamics (see, e.g., [11]). This work aims to bridge this divide.

In a classic application of our $\delta$-synchronizer, we extend the applicability of the synchronous algorithm for maintaining a spanning forest that approximates the minimum possible number of spanning trees in arbitrary dynamic networks of [6] to semi-synchronous environments (after adapting the algorithm from the Push to Pull model). Another application is in the context of minority dynamics [8], a stateless protocol in which each node samples a random subset of neighbors and adopts the minority opinion observed. The impact of our synchronizer is not about enabling synchronous algorithms in semi-synchronous environments, but about providing an exponential speed-up in runtime when doing so, as we describe in [7].

In future work, we plan to investigate whether we can extend the $\delta$-Synchronizer also to work in asynchronous environments, determine its overhead in terms of runtime and bits exchanged, and investigate whether it can work under certain classes of (non-stabilizing) network dynamics (e.g., edge recurrent, snapshot connected, etc.).