Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election

The subtree comparator takes two non-isomorphic subtrees $T^v$ and $T^u$ as input and determines whether $T^v\prec T^u$ or $T^u\prec T^v$. The enumeration of subtrees is required to be consistent with this comparator: if $T^v\prec T^u$, then $T^v$ must be listed before $T^u$. We will later show that the comparator is transitive, ensuring that a valid enumeration indeed exists. For isomorphic subtrees, we write $T^v=T^u$, and we use $T^v⪯T^u$ to denote either $T^v=T^u$ or $T^v\prec T^u$.

Given inputs $T^v$ and $T^u$, the comparator follows the three rules below.

Low layer first:

Assume $v$ and $u$ are not of the same layer. If $v$ is from a lower layer, then the comparator outputs $T^v\prec T^u$, and vice versa.

Fewer children first:

Assume $v$ and $u$ are of the same layer. Let $N_{T^v}(v)$ (resp., $N_{T^u}(u)$) be the set of neighbors of $v$ (resp., $u$) in $T^v$ (resp., $T^u$). If , then the comparator outputs $T^v\prec T^u$, and vice versa.

Recursion rule:

Assume $v$ and $u$ lie in the same layer and have the same number of children in their respective rooted subtrees, i.e., $|N_{T^v}(v)|=|N_{T^u}(u)|$. Let the children of $v$ be $v_1,v_2,\mathrm{\dots },v_{d-1}$, ordered so that

$$T^{v_1}⪯T^{v_2}⪯\mathrm{\cdots }⪯T^{v_{d-1}}.$$

Similarly, list the children of $u$ as $u_1,u_2,\mathrm{\dots },u_{d-1}$, ordered according to $⪯$.

Now consider the smallest index $i$ for which $T^{v_i}$ and $T^{u_i}$ are not isomorphic. If $T^{v_i}\prec T^{u_i}$, then comparator outputs $T^v\prec T^u$, and vice versa.

The proof is deferred to the full version [10] of the paper due to the page limit. $◀$

Now all nodes obtain identical enumerations: $T_1,T_2,\mathrm{\dots }{T}_k$, where $k$ is the number of distinct (non-isomorphic) subtrees appearing in $G$.

For convenience of presentation, we define a helper function that maps each vertex $v$ to the index of the subtree rooted at $v$ in the enumerated list.

We also define a helper function that maps the index $i$ to the integer $k-i$.

Write $\lambda \tau (v)$ as shorthand for $\lambda (\tau (v))$. By definition, we have if and only if $T^v\prec T^u$, and $\lambda \tau (v)=\lambda \tau (u)$ if and only if $T^v$ is isomorphic to $T^u$.

We are now ready to present the rules for our algorithm. Each node derives three categories of rules from the subtree enumeration: $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$, $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$, and $\mathrm{𝐃𝐨𝐰𝐧𝐬𝐭𝐫𝐞𝐚𝐦}$. Initially, only $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ and $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rules are active. After a node triggers at least one of $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ and $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rules, $\mathrm{𝐃𝐨𝐰𝐧𝐬𝐭𝐫𝐞𝐚𝐦}$ rules become active for that node.

Recall that we defined parent and children in Definition 9. If the advised topology $G$ has even diameter, then $V_r=\{l\}$ is a singleton set; apart from $l$, each vertex has its parent assigned, and we aim to elect the node corresponding to $l$ as the leader. If $G$ has odd diameter, $V_r$ contains two vertices $l_1$ and $l_2$, which both have no parents. The fact that $G$ is not symmetric over any edge enables us to decide a leader between $l_1$ and $l_2$: in fact, $T^{l_1}$ must not be isomorphic to $T^{l_2}$, and they are exactly the last two trees enumerated due to belonging to the highest layer $r$. Without loss of generality, we assume $T^{l_1}=T_{k-1}$, $T^{l_2}=T_k$ in the remainder of this section. To make proofs more concise, we manually assign $l_2$ as the parent of $l_1$, and $l_1$ as a child of $l_2$. At no risk of confusion, if the diameter is odd, define $l=l_2$. In either case, the only vertex without a parent is $l$, and we call it the root of the tree. Our goal is to elect the node corresponding to the root vertex $l$ as leader.

The definition of $\lambda$ implies that

To prove $\lambda (j)>\lambda (j^{\prime })$, it suffices to show that , i.e., that $T_j$ is enumerated before $T_{j^{\prime }}$. Since the respective roots of $T_j$ and $T_{j^{\prime }}$ have the same degree, the Fewer children first rule does not apply. Thus, the comparison must be determined by either the Low layer first rule or the Recursion rule.

If the root of $T_j$ lies in a lower layer than the root of $T_{j^{\prime }}$, then $T_j\prec T_{j^{\prime }}$ immediately by the Low layer first rule.

Now consider the case where the two roots lie in the same layer. Since the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rules under consideration are distinct, there exists a smallest index $i$ such that meaning that $T^{m_i}$ is enumerated before $T^{m_i^{\prime }}$, and hence $T^{m_i}\prec T^{m_i^{\prime }}$. By the Recursion rule, we then obtain $T_j\prec T_{j^{\prime }}$, so $T_j$ is enumerated first.

It remains to show that it is impossible for the root of $T_j$ to lie in a higher layer than the root of $T_{j^{\prime }}$. Since each list of $\lambda \tau$-values is sorted in non-increasing order, we have

Thus $T^{m_{d-1}}$ is the last among these subtrees to be enumerated, so $m_{d-1}$ is a highest-layer child of the root of $T_j$. By Observation 10, $m_{d-1}$ must lie exactly one layer below the root of $T_j$, and therefore must lie in a higher layer than $m_{d-1}^{\prime }$. Hence $\tau (m_{d-1})>\tau (m_{d-1}^{\prime }),$ contradicting the fact that $\tau (m_{d-1})\le \tau (m_{d-1}^{\prime })$. $◀$

The following observation still applies.

Lemma 27 and Observation 12 show that our Upstream rules are well-defined in the following sense: While a node can trigger multiple $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rules throughout the election process, an $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule triggered earlier does not send more pulses along $\mathrm{𝖯𝗈𝗋𝗍}\ast$ than an $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule triggered later.

Recall from the definition of $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ that if the rule constructed from the $\tau (u)$th enumerated tree $T_{\tau (u)}=T^u$ is triggered, $\lambda \tau (u)$ pulses are sent to $\mathrm{𝖯𝗈𝗋𝗍}\ast$. The only possible way for $u$ to send additional pulses would be to trigger another $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule and send $\lambda \tau (u^{\prime })>\lambda \tau (u)$ pulses to $v$. We will show that this cannot occur. We proceed by induction over layers, from $V_0$ to $V_r$, i.e., in a bottom-up manner.

Let $u$ be a leaf node in $V_0$. Then $T^u$ is a single-node tree and must be the first to be enumerated, i.e., $\tau (u)=1$. By the Upstream rule constructed from it, $u$ sends $k-1=\lambda \tau (u)$ pulses to its parent immediately upon initialization and never sends any additional pulses. Hence, the lemma holds for $u$.

Assume the lemma holds for all nodes in $V_s$ and lower layers for some $s\in [0,r-1]$. Let $u$ be a node in $V_{s+1}$ with $u\ne l$, and let $v$ be its parent. Note that $\tau (u)\le k-1$, so $\lambda \tau (u)\ge 1$.

Suppose $u$ sets $\mathrm{𝖯𝗈𝗋𝗍}\ast$ to point to $v$ (otherwise the lemma follows immediately for $u$). Let the children of $u$ be $\{m_1,m_2,\mathrm{\dots },m_{d-1}\}$ with

Assume, for the sake of contradiction, that $u$ eventually triggers some Upstream rule sending $\lambda \tau (u^{\prime })>\lambda \tau (u)$ pulses to $v$. Let the children of $u^{\prime }$ be $\{m_1^{\prime },m_2^{\prime },\mathrm{\dots },m_{d-1}^{\prime }\}$, ordered so that

Since each child of $u$ lies in a layer below $V_{s+1}$, the induction hypothesis implies that each $m_i$ sends at most $\lambda \tau (m_i)$ pulses to $u$. Consequently,

By Lemma 27, we have , contradicting the assumption that $\lambda \tau (u^{\prime })>\lambda \tau (u)$. $◀$

We first show that $l$ cannot trigger any $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule. Recall that $T^l=T_k$ is the last enumerated subtree; let the children of $l$ be $\{m_1,m_2,\mathrm{\dots },m_d\}$, ordered so that $\lambda \tau (m_1)\ge \lambda \tau (m_2)\ge \mathrm{\cdots }\ge \lambda \tau (m_d)$. By Lemma 28, node $l$ receives at most $\lambda \tau (m_1),\lambda \tau (m_2),\mathrm{\dots },\lambda \tau (m_d)$ pulses from its children. Consider any $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule associated with some node $u^{\prime }$ of degree $d$, whose children are $\{m_1^{\prime },m_2^{\prime },\mathrm{\dots },m_{d-1}^{\prime }\}$, with $\lambda \tau (m_1^{\prime })\ge \lambda \tau (m_2^{\prime })\ge \mathrm{\cdots }\ge \lambda \tau (m_{d-1}^{\prime })$.

Suppose first that $u^{\prime }$ lies in a layer lower than or equal to $r-1$. Then, by Observation 10, the child $m_{d-1}^{\prime }$ must lie in a layer at least as high as $r-2$. Meanwhile, regardless of whether the diameter is even or odd, the two children $m_{d-1}$ and $m_d$ of $l$ lie in layers at least as high as $r-1$. Hence, $\lambda \tau (m_{d-1}^{\prime })>\lambda \tau (m_{d-1})\ge \lambda \tau (m_d)$, which shows that $l$ cannot trigger the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule for the subtree rooted at $u^{\prime }$.

Now suppose instead that $u^{\prime }$ also lies in layer $r$. Then $T^{u^{\prime }}=T_{k-1}$, and moreover the last child of $l$, namely $m_d$, is exactly $u^{\prime }$. By the Recursion rule of the subtree comparator, $T^{u^{\prime }}$ is ordered before $T^l$, which implies there exists a smallest index $i$ such that . Thus $l$ again cannot satisfy the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule for the subtree rooted at $u^{\prime }$.

Next, we proceed by induction over the layers to prove the lemma, from $V_r$ to $V_0$, i.e., in a top-down manner.

In $V_r$, the (possibly) only node we need to consider is $l_1$, whose parent is $l$. Suppose, for the sake of contradiction, that $l_1$ receives a pulse from $l$ before sending one to $l$. Such a pulse cannot result from a triggered $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule, as established above. It also cannot arise from a triggered $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule, since that would require $l$ to have received pulses from all its ports, yet $l_1$ has not sent any pulses to $l$. This yields a contradiction.

Assume that the lemma holds for all nodes in $V_s$ and higher layers for some $s\in [1,r]$. Let $u$ be a node in $V_{s-1}$ and let $v$ be its parent. Suppose, for the sake of contradiction, that $u$ receives a pulse from $v$ before sending one to $v$. As in the base case, $v$ cannot trigger the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule. Thus, it remains to rule out the possibility that $v$ triggers an $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule and sets the port pointing to $u$ as $\mathrm{𝖯𝗈𝗋𝗍}\ast$.

If $v=l$, then the same argument as in the base case yields a contradiction. If instead $v$ has a parent $w$, then for $v$ to trigger $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$, it must have received a non-zero number of pulses from $w$. By the induction hypothesis, $v$ must have sent pulses to $w$ before receiving any, and such pulses can only result from an $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule with the port pointing to $w$ designated as $\mathrm{𝖯𝗈𝗋𝗍}\ast$. This contradicts Observation 12. Hence, $u$ also satisfies the lemma. $◀$

Observe that the following four lemmas continue to apply. We omit the proofs, as they follow from arguments nearly identical to those used previously.

See 16 See 17 See 18 See 19

The next lemma follows from the way we constructed $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ and $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rules.

Lemma 19 establishes that, before $l$ triggers $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$, pulses travel from children to parents. Therefore, we only need to consider pulses directed as such, as we are reasoning about a necessary condition for $l$ to trigger $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$.

First, let the children of $l$ be $\{m_1,m_2,\mathrm{\dots },m_d\}$, ordered so that

By the definition of the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule, $l$ must receive

pulses from its children, respectively, in order to trigger $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$. Since Lemma 28 shows that each child $m_i$ can send at most $\lambda \tau (m_i)$ pulses to $l$, it follows (by an induction on $i$ from $d$ down to $1$) that $l$ may trigger the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule only after each child $m_i$ has triggered the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule corresponding to its own subtree $T_{\tau (m_i)}=T^{m_i}$.

Let the children of a node $v\ne l$ be $\{m_1,m_2,\mathrm{\dots },m_{d-1}\}$, ordered so that

Assume it has been established that $l$ may trigger the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule only after $v$ triggers the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule defined by $T_{\tau (v)}=T^v$.

By the definition of the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule constructed from $T_{\tau (v)}=T^v$, node $v$ must receive

pulses from its $d-1$ children in order to trigger the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule of $T_{\tau (v)}=T^v$. Meanwhile, by Lemma 28, each child $m_i$ can send at most $\lambda \tau (m_i)$ pulses to $v$. Similarly, it follows that $v$ may trigger the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule corresponding to $T_{\tau (v)}=T^v$ only after each child $m_i$ has triggered its own $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule associated with $T_{\tau (m_i)}=T^{m_i}$.

Therefore, we have extended the necessary condition for $l$ to trigger $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ from node $v\ne l$ to all children of $v$. $◀$

The above lemma does not guarantee that $l$ will trigger the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule. It only points out a condition for $l$ to trigger the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule. To show that this condition is eventually satisfied and that $l$ indeed triggers the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule, we present the next lemma.

We again apply induction over layers, from $V_0$ to $V_r$, to show that every node $u$ other than $l$ eventually triggers the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule corresponding to its subtree $T_{\tau (u)}=T^u$ and sets $\mathrm{𝖯𝗈𝗋𝗍}\ast$ to point to its parent. To do so, it suffices to show that $u$ eventually sends $\lambda \tau (u)$ pulses to its parent, as the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rules are well-defined (Lemma 27 and Observation 12).

Indeed, once every node $v\ne l$ has sent $\lambda \tau (v)$ pulses to its parent, node $l$ receives enough pulses from its neighbors to trigger the $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ rule, as required.

It is immediate that any node $u\in V_0$ eventually sends $\lambda \tau (u)=\lambda (1)=k-1$ pulses to its parent, as this follows directly from the definition of the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule applied to degree-1 nodes.

​​Assume the lemma holds for all nodes up to $V_s$ for some $s\in [0,r-1]$. Let $u$ be a node in $V_{s+1}$. By the induction hypothesis, the children of $u$, denoted $\{m_1,m_2,\mathrm{\dots },m_{d-1}\}$, eventually send $\lambda \tau (m_1),\lambda \tau (m_2),\mathrm{\dots },\lambda \tau (m_{d-1})$ pulses to $u$, respectively. This causes the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule corresponding to the subtree $T_{\tau (u)}=T^u$ to trigger, so $u$ sends $\lambda \tau (u)$ pulses through $\mathrm{𝖯𝗈𝗋𝗍}\ast$ to its parent.

During this process, $u$ does not receive any unexpected pulses from its parent. The possibilities of $u$ getting such a pulse from its parent due to $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$, $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$, or $\mathrm{𝐃𝐨𝐰𝐧𝐬𝐭𝐫𝐞𝐚𝐦}$ are ruled out by combining Lemma 16, Lemma 17, Lemma 18 (or equivalently, just Lemma 19), and Lemma 30.

Finally, once the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule for $T_{\tau (u)}=T^u$ has been triggered, the entire subtree rooted at $u$ reaches quiescence: each child of $u$ has already sent the maximum number of pulses permitted by Lemma 28, and all such pulses have been received. $◀$

We remark that the above proof, combined with Lemma 28, shows that the number of pulses every node $v\ne l$ sends to its parent due to the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rules is exactly $\lambda \tau (v)$.

We first observe that by Lemma 31, the node $l$ eventually terminates as $\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$, and at that moment the tree is in quiescence. For all remaining nodes, we assume that $l$ has already terminated as $\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$ and proceed by induction from $V_r$ down to $V_0$.

For the layer $V_r$, the only node we may need to consider is $l_1$. By Lemma 31, the node $l_1$ has already triggered the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule corresponding to $T_{\tau (l_1)}$ and set $\mathrm{𝖯𝗈𝗋𝗍}\ast$ to point to $l$ before $l$ terminates as $\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$ and sends a pulse to $l_1$. Consequently, $l_1$ will eventually receive a pulse from $\mathrm{𝖯𝗈𝗋𝗍}\ast$, trigger the $\mathrm{𝐃𝐨𝐰𝐧𝐬𝐭𝐫𝐞𝐚𝐦}$ rule, and terminate as $\mathrm{𝖭𝗈𝗇}\text{-}\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$. At this point, $l$ has already terminated and will not send further pulses to $l_1$, and by Lemma 28, $l_1$ will not receive additional pulses from its children. Thus, $l_1$ reaches quiescent termination.

Assume the lemma holds for all nodes in $V_s$ or higher layers, for some $s\in [1,r]$. Let $u$ be a node in $V_{s-1}$. By Lemma 31, $u$ must have triggered the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rule corresponding to $T_{\tau (u)}$ and set $\mathrm{𝖯𝗈𝗋𝗍}\ast$ to its parent $v$. Since $v$ lies in a higher layer, the induction hypothesis ensures that $v$ eventually triggers the $\mathrm{𝐃𝐨𝐰𝐧𝐬𝐭𝐫𝐞𝐚𝐦}$ rule and terminates as $\mathrm{𝖭𝗈𝗇}\text{-}\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$. Therefore, $u$ will eventually receive a pulse from $\mathrm{𝖯𝗈𝗋𝗍}\ast$, trigger the $\mathrm{𝐃𝐨𝐰𝐧𝐬𝐭𝐫𝐞𝐚𝐦}$ rule, and terminate as $\mathrm{𝖭𝗈𝗇}\text{-}\mathrm{𝖫𝖾𝖺𝖽𝖾𝗋}$. The argument for quiescent termination follows exactly as in the base case. $◀$

For each node other than $l$, exactly $\lambda \tau (u)\le k-1\le n-1$ pulses are sent to its parent due to the $\mathrm{𝐔𝐩𝐬𝐭𝐫𝐞𝐚𝐦}$ rules (see the proofs of Lemmas 28 and 31), contributing at most ${(n-1)}^2$ pulses in total. The $\mathrm{𝐋𝐞𝐚𝐝𝐞𝐫}$ and $\mathrm{𝐃𝐨𝐰𝐧𝐬𝐭𝐫𝐞𝐚𝐦}$ rules cause exactly one pulse to be sent across each edge (see the proof of Lemma 32), contributing an additional $n-1$ pulses. Therefore, the total number of pulses sent during the execution of the algorithm is at most ${(n-1)}^2+(n-1)=O(n^2)$. $◀$

The correctness and quiescent termination of the leader election algorithm follow from Lemmas 31 and 32, and the message complexity bound follows from Lemma 33. $◀$