Content-Oblivious Leader Election in 2-Edge-Connected Networks

For our result on general 2-edge-connected topologies, we assume no prior knowledge of the network topology, except that each node is given an upper bound $N\ge n$ on the total number of nodes. That is, the algorithm is non-uniform.

The degree of a node $v$, $\mathrm{deg}(v)$, is the number of edges incident to $v$. A node does not know the identifiers of its neighbors, but can distinguish its incident edges using port numbering, a bijection between the set of incident edges and the set $\{1,2,\mathrm{\dots },\mathrm{deg}(v)\}$. Therefore, we use the term port to refer to the local endpoint of an edge, uniquely identified by its port number, which is used to send and receive messages to and from a specific neighbour.

For our result on rings, we assume that the topology is an unoriented ring. In this case, each node $v_i$ is connected to nodes $v_{i-1}$ and $v_{i+1}$ (indices taken modulo $n$) by port $0$ and port $1$. These local labels do not induce a consistent orientation of the ring; that is, the global assignment of labels $0$ and $1$ to ports is arbitrarily set by an adversary. A correct algorithm must work for any possible assignment of port labels.

In the content-oblivious setting, nodes communicate by sending content-less pulses. We consider the asynchronous model, where node behavior is event-driven: A node can act only upon initialization or upon receiving a pulse. Based on the pattern of previously received pulses, each node decides its actions, which may include sending any number of pulses through any subset of its ports. We emphasize that when a node receives a pulse, it knows the port through which the pulse arrived. We restrict our attention to the deterministic setting, in which nodes do not use randomness in their decision-making.

There is no upper bound on how long a pulse may take to traverse an edge, but every pulse is guaranteed to be delivered after a finite delay. An equivalent way to model this behavior is by assuming the presence of a scheduler. At each time step, as long as there are pulses in transit, the scheduler arbitrarily selects one and delivers it.

We assume that upon receiving a pulse, all actions triggered by that pulse are performed instantaneously, so that the system can be analyzed in discrete time steps. We focus only on specific, well-defined moments in the execution of the algorithm – namely, the moments just before the scheduler selects a pulse to deliver. At these times, all the actions resulting from earlier pulse deliveries have been completed, and the system is in a stable state, awaiting the next step. We do not analyze the system during any intermediate period in which a node is still performing the actions triggered by a pulse arrival.

We write $[s]=\{1,2,\mathrm{\dots },s\}$. In the algorithm description and analysis for Theorem 1, for each node $v\in V$ and each port number $i\in [\mathrm{deg}(v)]$, we use the following notation to track the number of pulses sent and received so far:

• $\mathrm{■}$

  ${\sigma }_i(v)$ denotes the number of pulses sent on port $i$ of node $v$.

• $\mathrm{■}$

  ${\rho }_i(v)$ denotes the number of pulses received on port $i$ of node $v$.

Throughout this paper, we write $r$ to denote the node with the smallest identifier. Consider a DFS traversal rooted at $r$ such that when a node selects the next edge to explore among its unexplored incident edges, it chooses the one with the smallest port number. Let $T_G=(V,E_T)$ be the resulting DFS tree. The edges in $E_T$ are called tree edges, and the remaining edges $E_B=E\setminus E_T$ are called back edges. The following observation is folklore.

When a node $u$ explores an incident edge $e=\{u,v\}$ during the DFS, there are two possibilities: Either $v$ is an ancestor of $u$, or $v$ has not been visited yet. In the first case, $\{u,v\}\in E_B$. In the second case, $v$ is discovered for the first time, so $\{u,v\}\in E_T$ is added as a tree edge in $E_T$. $◀$

A directed graph is strongly connected if for any two nodes $u$ and $v$ in the graph, there is a directed path from $u$ to $v$. We have the following observation. Due to page limit, the proof of Observation 9 is deferred to the full version [9] of the paper.

Throughout the paper, for any two nodes $u\in V$ and $v\in V$, we write $P_{u,v}$ to denote any shortest path from $u$ to $v$ in $\overrightarrow{G}$, whose existence is guaranteed by Observation 9. We allow $u=v$, in which case $P_{u,v}$ is a path of zero length consisting of a single node $u=v$.

To achieve an almost synchronized counting, we employ the $\alpha$-synchronizer [4], as follows. Each node maintains a counter variable $\mathrm{𝖢𝗈𝗎𝗇𝗍}(v)$, which is initialized to $0$ at the start of the algorithm. A node increments its counter by one after receiving a new pulse from each of its neighbors. Formally, the counter value of a node $v$ is given by

Each node broadcasts a pulse to all its neighbors upon initialization and immediately after each counter increment. This process is non-blocking: In the absence of an exit condition, nodes will continue counting together indefinitely. Furthermore, no node can advance significantly faster than its neighbors: For any pair of adjacent nodes, their counter values differ by at most one. A faster-counting node must wait for a pulse from a slower-counting neighbor before it can increment its counter again.

A node $v$ elects itself as the leader once $\mathrm{𝖢𝗈𝗎𝗇𝗍}(v)=\mathrm{𝖨𝖣}(v)$, after which node $v$ freezes its counter and does not increment it further. This action caps the counter value of any neighbor of $v$ at most $\mathrm{𝖨𝖣}(v)+1$. More generally, in a graph of $n\le N$ nodes, the counter value of any node is upper bounded by $\mathrm{𝖨𝖣}(v)+N-1$, due to the diameter upper bounded by $N-1$.

To ensure that the algorithm elects the node $r$ with the smallest identifier as the unique leader, it suffices for any two identifiers to differ by at least $N$. This can be achieved by first multiplying each identifier by $N$. This is where the a priori knowledge of $N$ comes into play.

At this stage, we have a simple stabilizing leader election algorithm. However, it remains insufficient for our purposes: We also want all non-leader nodes to recognize their non-leader status and terminate in a quiescent manner.

Let $u$ be a neighbor of the leader $r$, and let the edge $e=\{u,r\}$ correspond to port $i$ at $r$ and port $j$ at $u$. The leader $r$ notifies $u$ of its leadership as follows:

1. 1.

   Wait until ${\rho }_i(r)\ge \mathrm{𝖨𝖣}(r)+1$.

2. 2.

   Send pulses to $u$ until ${\sigma }_i(r)=\mathrm{𝖨𝖣}(r)+N+2$.

Since the graph $G$ is 2-edge-connected, there exists a path $P$ from $u$ to $r$ that avoids $e$, implying

Eventually, $u$ receives $\mathrm{𝖨𝖣}(r)+N+2$ pulses from $r$, so there must be a moment where

triggering anomaly detection. Under normal conditions in the first phase, $u$ would expect

so this deviation signals a violation.

Additionally, the waiting condition ${\rho }_i(r)\ge \mathrm{𝖨𝖣}(r)+1$ ensures that $\mathrm{𝖢𝗈𝗎𝗇𝗍}(u)\ge \mathrm{𝖨𝖣}(r)$. Thus, $u$ not only recognizes that it is not the leader but can also deduce the exact value of $\mathrm{𝖨𝖣}(r)$ using

since all node identifiers are integer multiples of $N$.

Intuitively, the leader $r$ is able to notify a neighbor $u$ because the counter value of node $u$ is constrained by a chain $P$, whose other end is anchored at the leader $r$, whose counter has already been frozen. To extend this notification process to the entire network, we perform a DFS, using the same notification procedure to explore each new edge. When a node finishes exploring all its remaining incident edges, it can notify its parent by sending pulses until a total of $\mathrm{𝖨𝖣}(r)+N+2$ pulses have been sent through this port since the start of the algorithm. When a node $u$ explores a back edge $\{u,v\}$, the node $v$ replies using the same method. When a node decides which new incident edge to explore, it prioritizes the edge with the smallest port number, so the resulting DFS tree is $T_G$, as defined in Section 2.3.

To see that the algorithm achieves quiescent termination, observe that by the end of the execution, for each edge $e$, the number of pulses sent in both directions is exactly $\mathrm{𝖨𝖣}(r)+N+2$. Therefore, once a node observes that it has both sent and received exactly $\mathrm{𝖨𝖣}(r)+N+2$ pulses along each of its ports and has completed all local computations, it can safely terminate with a quiescent guarantee.

A similar chain-and-anchor argument can be applied to analyze the correctness of the DFS-based notification algorithm. We prove by induction that for each node $u$ that has been visited by DFS, its frozen counter value satisfies

Recall from Section 2.3 that $P_{a,b}$ is a shortest path from $a$ to $b$ in the directed version $\overrightarrow{G}$ of $G$ defined in Definition 8.

Suppose during the DFS, a node $x$ is about to explore an incident edge $e=\{x,y\}$ using the notification procedure, and that $y$ has not yet been visited. Let $w$ be the first node on the path $P_{y,r}$ that is either $x$ or an ancestor of $x$ in the DFS tree $T_G$, then we have

We now apply the chain-and-anchor argument using the chain $P_{y,w}$ and anchor $w$. This choice of chain is valid because the path $P_{y,w}$ cannot include the edge $e$, as $e$ is oriented from $x$ to $y$ in $\overrightarrow{G}$. This is precisely why the analysis is carried out in $\overrightarrow{G}$ rather than in $G$.

By the induction hypothesis, the frozen counter value at the anchor satisfies $\mathrm{𝖢𝗈𝗎𝗇𝗍}(w)\le \mathrm{𝖨𝖣}(r)+\mathrm{𝗅𝖾𝗇𝗀𝗍𝗁}(P_{w,r})$. It follows that

Therefore, the chain-and-anchor argument works, allowing $y$ to be successfully notified. Moreover, the frozen counter value of $y$ also satisfies the induction hypothesis.

In addition, we must ensure that the DFS procedure proceeds correctly and no event is triggered unexpectedly. Once again, the chain-and-anchor argument implies that the condition

holds for all nodes $u\in V\setminus \{r\}$ at all times. This ensures that no node other than $r$ can be mistakenly elected as a leader. It also guarantees that pulses sent by nodes still in the first phase cannot accidentally trigger a notification in the second phase. Specifically, if $u$ is still in the first phase, then for every port $j\in [\mathrm{deg}(u)]$, we have

which remains below the threshold of $\mathrm{𝖨𝖣}(r)+N+2$ pulses required to confirm receipt of a notification.

One might wonder why the notification must follow a DFS instead of being performed in parallel. A key reason is that doing so can break the chain-and-anchor argument by eliminating anchors. For instance, in a ring topology, if the node $r$ with the smallest identifier simultaneously sends multiple pulses to both neighbors, all of the pulses might be interpreted as part of the first phase, with no detectable anomaly, regardless of how many pulses are sent.

Both our leader election algorithm and the simulation algorithm of [7] utilize DFS, but for different purposes. They perform a DFS from a pre-selected leader to find a cycle, while we use DFS to disseminate the identity of the elected leader to all nodes and to achieve quiescent termination. Coincidentally, both approaches leverage the strongly connected orientation of 2-edge-connected graphs. In our case, the orientation $\overrightarrow{G}$ is used solely in the analysis to facilitate the chain-and-anchor argument. In their case, it guarantees the existence of a Robbins cycle, which is critical to their algorithm.

Suppose w.l.o.g. that node $v_a$ exchanges pulses with $v_b$ on port 1, while node $v_b$ exchanges pulses with $v_a$ on port 0.

If node $v_a$ executed $x$ times Line 5 (i.e., $x+1\ge i_a\ge x$), then node $v_b$ executed $y\ge x$ times Line 3 (i.e., $i_b\ge y$). From this $i_b\ge i_a-1$. By a symmetric argument we have $i_a\ge i_b-1$ and this shows the first part of the lemma. Assume now that $v_b$ has not executed its send, this means that $y=(i_b-1)$ and thus $x\le y\le i_b-1$ therefore since $i_a\le x+1\le i_b$. For the hypothesis we have $i_a=i_b$. $◀$

By Lemma 12 and Observation 11, we have that when $v_2$ exits the loop, it has sent ${\mathrm{𝖨𝖣}}_2$ pulses to both its neighbors and thus $v_1$ and $v_3$ are in iteration ${\mathrm{𝖨𝖣}}_2$ or ${\mathrm{𝖨𝖣}}_2+1$ of the loop. Since their identifiers are at least ${\mathrm{𝖨𝖣}}_2+2$, they are still in their competing phase. Note that, by Lemma 12 and Observation 11, they cannot complete iteration ${\mathrm{𝖨𝖣}}_2+2$ before they have received at least ${\mathrm{𝖨𝖣}}_2+2$ pulses from $v_2$. The last two of these pulses have to be sent by $v_2$ either at Line 7 or at Line 15. $◀$

Any node $v\ne v_2$ in the ring has an $\mathrm{𝖨𝖣}$ that is at least ${\mathrm{𝖨𝖣}}_2+2$. Consequently, by Lemma 13 and Lemma 12, every node eventually completes ${\mathrm{𝖨𝖣}}_2$ iterations of the competing phase and every node $v\ne v_2$ enters iteration ${\mathrm{𝖨𝖣}}_2+1$. Thus, in particular, $v_1$ and $v_3$ send pulses to $v_2$ in iteration ${\mathrm{𝖨𝖣}}_2+1$. Consequently, $v_2$ will eventually receive a pulse from $v_3$ on port $1$ (i.e., it will not be blocked at Line 8). Moreover, since $v_1$ has sent a pulse p to $v_2$ at iteration ${\mathrm{𝖨𝖣}}_2+1$, $v_2$ will eventually receive a pulse on some port $q$ (i.e., it will execute Line 9). As long as $v_2$ does not send a pulse to $v_3$, $v_3$ will not complete iteration ${\mathrm{𝖨𝖣}}_2+1$ of the competing phase, and it will thus not send another pulse to $v_2$ before p is delivered. Consequently, $q=0$ and $v_2$ enters the rebalancing phase. $◀$

Notice that if $v_2$ is only a local minimum among $v_1,v_2,$ and $v_3$, rather than a global one, it is still possible to adapt the proof to obtain a weaker variant of the lemma. In this variant, if $v_2$ executes Line 10, it must do so with $q=0$.

From Lemma 14 we have:

The following observation follows from the fact that the second minimum identifier in the ring is at least ${\mathrm{𝖨𝖣}}_2+2$. Recall that the reduced ring is obtained by removing node $v_2$ and directly connecting $v_1$ and $v_3$ while respecting the original port labeling.

Once $v_2$ terminates its competing phase it has sent/received ${\mathrm{𝖨𝖣}}_2$ pulses to/from each of its neighbors. At Line 7, it sends $2$ pulses to $v_1$ and at Line 15 it sends $2$ pulses to $v_3$. Moreover, at Lines 8 and 17, it has received two pulses from $v_3$ and at Lines 9 and 16 it has received two pulses from $v_1$ (recall, Lemma 14, that if Line 16 is executed then $q=0$ at Line 9). $◀$

We are now ready to prove Proposition 10.

By Observation 18, before node $v_2$ completes its rebalancing phase, nodes $v_1$ and $v_3$ are not able to distinguish this execution from the one on the reduced ring. By Lemma 14, node $v_2$ completes its rebalancing phase and it eventually enters the relaying phase. It is easy to see that, from this point onward, $v_2$ behaves as an asynchronous link between $v_1$ and $v_3$ as long as $v_2$ does not exit the loop at Lines 19–23. $◀$

From Proposition 10, it follows that as long as no node terminates and there are at least two active nodes, the one with the minimum identifier will enter the relaying phase, and the other active nodes will behave as if this node were not present in the ring.

Observe that the global minimality of ${\mathrm{𝖨𝖣}}_2$ is used only in the proof of Lemma 14, to establish that $v_2$ must enter the relaying phase, all the other lemmas, when needed, they only require the identifier of $v_2$ to be a local minimum among $v_1,v_2,v_3$. As a matter of fact, a node $v^{\prime }$ may have an identifier that is a local minimum over a sufficiently long sequence of nodes, allowing it, in some executions, to enter the relaying phase before the global minimum. This does not affect the indistinguishability claimed in Proposition 10 that remains valid for $v^{\prime }$ and its two neighbours.

We now show that no node terminates before the one with the maximum identifier exits its competing phase. Moreover, we show that this node eventually enters the global termination phase, triggering the algorithm’s termination with the election of the node with the maximum identifier. We will show that each node terminates when it has received three more pulses on one port than the other. In the next lemma, we characterize when such an event can happen.

During the competing phase, on each port, each node alternately sends a pulse on each port and receives a pulse on each port. At the end of the competing phase, node with identifier $\mathrm{𝖨𝖣}$ has sent and received $\mathrm{𝖨𝖣}$ pulses on each port. At Line 7, it sends two pulses on port $0$. Then, if the condition at Line 10 is true, it sends a third pulse on port $0$ (i.e., it executes Line 11) and stops sending pulses afterwards.

Suppose now that the condition at Line 10 is not satisfied. Then it means that at Line 9, $q=0$ and at this point, $v$ has sent $\mathrm{𝖨𝖣}+2$ pulses on port $0$, has sent $\mathrm{𝖨𝖣}$ pulses on port $1$, has received $\mathrm{𝖨𝖣}+1$ pulses on port $0$, and has received $\mathrm{𝖨𝖣}+1$ pulses on port $1$. After the rebalancing phase (Lines 15 to 17), $v$ has sent and received $\mathrm{𝖨𝖣}+2$ pulses on each port.

After that, it just relays the pulses in the order they arrive and stores the difference between the number of pulses sent on each port in the variable $\mathrm{𝖣𝗂𝖿𝖿}$. Thus, after each iteration of the loop of the relaying phase, the number of pulses it has sent on a port $q$ is precisely the number of pulses it has received on port $1-q$. Thus, it will send three more pulses on port $q$ than on port $1-q$ only if it has received three more pulses on port $1-q$ than on port $q$. When this happens, $|\mathrm{𝖣𝗂𝖿𝖿}|=3$ and node $v$ exits the loop and terminates. $◀$

By contradiction, suppose that some node $v$ terminates and that no node has executed Line 11 before. Then $v$ necessarily terminates the algorithm at Line 24, and thus at some time $t$, $v$ has received three more pulses on some port $q$ than on port $1-q$. Among all such nodes, consider the node $v$ such that this time $t$ is minimal. Let $v^{\prime }$ be the neighbor of $v$ behind port $q$. By Lemma 19, $v$ is a relaying node, and $v$ has received three more pulses from $v^{\prime }$ than it has sent to $v^{\prime }$. Consequently, there exists a time where $v^{\prime }$ has sent at least three more pulses to $v$ than it has received from $v$. By Lemma 19 and since we assumed that $v^{\prime }$ has not executed Line 11, it implies that at time $t^{\prime }$, $v^{\prime }$ has received three more pulses on one port than on the other. But this contradicts the definition of $v$ and $t$. $◀$

By iteratively applying Corollary 15 and Proposition 10, and by observing that, by Corollary 20, no node terminates early, we obtain the following corollary:

We now show that the node with the maximum identifier eventually enters the $\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$ state and that, after this point, no more pulses are sent in the network, and every other node eventually enters the $\mathrm{𝖭𝗈𝗇}\text{-}\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$ state.

Suppose that there is a moment $t$ where the ring contains only one competing node $v$. Then, by Proposition 10, Corollary 15, and Corollary 20 applied iteratively to all nodes except $v$, node $v$ cannot distinguish the original ring from a ring containing only $v$.

Thus during the competing phase, $v$ sends and receives $\mathrm{𝖨𝖣}(v)$ pulses to itself in each direction. In the solitude-checking phase, $v$ sends two pulses on port $0$ that are eventually delivered to itself on port $1$. Once $v$ has received both pulses, the condition at Line 10 is true and $v$ enters the global termination phase. It sends another pulse to itself on port $0$ (Line 11) that is eventually delivered on port $1$ and $v$ can then execute Lines 12 and 13 terminating in the $\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$ state.

Note that by Corollary 15, when $v$ exits its competing phase, every other node $v^{\prime }$ is a relaying node. Consequently, at this point, it has sent and received the same number of pulses on each port by Observation 11. Therefore, at this point, there are no pulses in transit in the network and, by Lemma 17, for each node $v^{\prime }\ne v$, we have $\mathrm{𝖣𝗂𝖿𝖿}(v^{\prime })=0$.

Once $v$ has executed Line 7, there are two pulses in transit in the network that are moving in the same direction and each node $v^{\prime }\ne v$ relays them (through the same port) before they reach $v$ on port $1$. So when $v$ executes Line 9, for each node $v^{\prime }\ne v$, we have $|\mathrm{𝖣𝗂𝖿𝖿}(v^{\prime })|=2$. Then, when $v$ executes Line 11, it sends a third pulse in the same direction that will eventually reach $v$ on port $1$, at which point there are no pulses in transit. In the meantime, every node $v^{\prime }\ne v$ will have relayed it and its variable $\mathrm{𝖣𝗂𝖿𝖿}(v^{\prime })$ will satisfy $|\mathrm{𝖣𝗂𝖿𝖿}(v^{\prime })|=3$. Thus, after $v^{\prime }$ has relayed this third pulse, $v^{\prime }$ will exit the loop in the relaying phase and it will terminate in the $\mathrm{𝖭𝗈𝗇}\text{-}\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$ state. $◀$

It suffices to show that Algorithm 1 is a correct leader election algorithm for all unoriented rings and it has a message complexity of $O(n{\mathrm{𝖨𝖣}}_{\max })$.

Correctness follows directly from Corollary 21 and Lemma 22. Regarding the message complexity, take the node $v_{\max }$ with maximum identifier ${\mathrm{𝖨𝖣}}_{\max }$, by Corollary 21 and Lemma 22, this node will execute Lines 1–13, sending $4{\mathrm{𝖨𝖣}}_{\max }+3$ pulses (the factor 4 comes from the fact that we initially double each identifier and send pulses in both directions) in the process. Consider now any other node $v_j$ with identifier ${\mathrm{𝖨𝖣}}_j\ne {\mathrm{𝖨𝖣}}_{\max }$, by Corollary 15 and Lemma 17, $v_j$ first executes Lines 1–9 and Lines 15–17, the number of pulses sent at these lines is $4{\mathrm{𝖨𝖣}}_j+4$, and then it executes Lines 19–23, but here it will only send a pulse when it receives one. Therefore, Lemma 22 and the fact that $v_{\max }$ sends $4{\mathrm{𝖨𝖣}}_{\max }+3$ pulses show that $v_j$ cannot send more than ${\delta }_j=(4{\mathrm{𝖨𝖣}}_{\max }+3)-(4{\mathrm{𝖨𝖣}}_j+4)$ pulses while relaying. The total number of pulses sent by Algorithm 1 is therefore at most $n(4{\mathrm{𝖨𝖣}}_{\max }+3)$. $◀$