An Almost-Logarithmic Lower Bound for Leader Election with Bounded Value Contention

This paper assumes the strong (adaptive) adversary model. In this model, the order in which processes take steps is decided adaptively by an adversary. It knows everything about the current state of all processes when it chooses which process takes the next step. By comparison, weaker adversaries have only partial information about process states such as the outcomes of random coin flips [3, 14]. To be specific, our lower bound proofs assume that the adversary knows the next step of every process, but does not need other information about internal process states.

Consider a (possibly randomized) algorithm $𝒜$ and an adaptive adversary $D$, which we assume, for simplicity, to be deterministic. Let $T_{p,D}$ be the random variable denoting the number of steps process $p$ performs in the execution of $𝒜$ when the scheduling is done by the adversary $D$. The expected step complexity of an execution under $D$ is $𝔼[T]={\max }_{p\in P}[T_{p,D}]$, where the expectation is taken over the processors’ coin flips. The worst-case expected step complexity of algorithm $𝒜$ is ${sup}_D\left[𝔼(T_{p,D})\right]$, i.e. the supremum over the expected step complexity of $𝒜$, under any adversary.

A Leader Election algorithm supports a single operation, elect, which each process may perform at most once. This operation returns either win or lose indicating whether the process won the election. It satisfies the following properties:

• $\mathrm{■}$

  With probability $1$, every process that does not crash finishes its operation in a finite number of steps.

• $\mathrm{■}$

  At most one operation returns win.

• $\mathrm{■}$

  If all operations that started have finished, then exactly one operation returned win.

A Splitter [21, 23] is an object that supports a single operation, decide, which each process may perform at most once. It satisfies the following properties:

• $\mathrm{■}$

  The output of decide is either Stop, Left, or Right.

• $\mathrm{■}$

  Every process that calls decide finishes it within a finite number of steps.

• $\mathrm{■}$

  At most one process can get Stop.

• $\mathrm{■}$

  If only one process calls decide, then it is guaranteed to get Stop.

• $\mathrm{■}$

  If more than one process calls decide, then not all processes get the same output.

Instead of the last property, a Randomized Splitter [8] requires that the probability a call of decide returns Left is the same as the probability it returns Right, independent of all other calls. Splitter and Randomized Splitter objects are similar to Leader Election, where getting Stop as output is analogous to winning, but they do not guarantee that some process gets output Stop, even if all calls have terminated.

We now describe formalize some well-known results used for to proving lower bounds, which were previously applied for this and other distributed problems [19, 14, 5, 25, 10].

We say that process $p$ sees another process if $p$ reads a value from some register that differs from the last value $p$ wrote there or is not the initial value of the register, if $p$ never wrote there. We say that $p$ sees process $q$ if $q$ was the last process that wrote to that register before $p$ read it. For any execution $ℰ$, define $p{\leftrightarrow }_{ℰ}q$ if $p$ sees $q$ or $q$ sees $p$ in execution $ℰ$. Let $p{\sim }_{ℰ}q$ be the reflexive transitive closure of ${\leftrightarrow }_{ℰ}$. This is an equivalence relation. A set of processes $P^{\prime }\subseteq P$ is closed (with respect to ${\sim }_{ℰ}$) if there does not exist $q\in P^{\prime }$ and $p\notin P^{\prime }$ such that $q{\sim }_{ℰ}p$.

Note that, if $P^{\prime }$ is a set of processes that is closed with respect to ${\sim }_{ℰ}$, then erasing the steps of all processes in $P^{\prime }$ from $ℰ$ results in an execution. Since exactly one operation wins in every terminating execution of Leader Election, we get the following result.

Based on this lemma, we formulate the first commonly used idea guaranteeing that processes have to take more steps in an execution $ℰ$ of Leader Election that contains at least two processes that are not related by ${\sim }_{ℰ}$.

For every part, $P^{\prime }$, of the partition, there is an execution obtained by erasing the steps of all processes in $P\setminus P^{\prime }$ from $ℰ$ and then running all processes in $P^{\prime }$ until they each finish performing elect(). By Lemma 1, exactly one process in $P^{\prime }$ wins in this execution. Consider the winning process for each set $P^{\prime }$ in the partition. Since at most one process wins in $ℰ$, each of these processes, except possibly one, has not won in $ℰ$ and, thus, it has not finished performing elect. $◀$

Intuitively, Lemma 2 shows that, if we execute processes in a way that prevents them from learning about one another, we can ensure that they have to take more steps.

A faction graph $G^{\star }=(V,F,E^{\star })$ is defined by a partition, $F$, of its vertex set, $V$, and a set of super-edges, $E^{\star }$, which connects vertices to parts of the partition, called factions. It contains no edges from any vertex to the faction that contains it. The graph $G=(V,E)$ represented by $G^{\star }$ is an undirected graph with the property that, if a vertex $v$ has a super-edge in $E^{\star }$ to a faction, $A\in F$, then all vertices in $A$ are neighbors of $v$ in $G$. An example of a faction graph is shown in Figure 1(a). The formal definition is given below.

Generally, a faction graph is a much more compact representation of the graph it represents.

Figure 1(a) is a faction graph with 7 vertices, 3 factions, $A$, $B$, and $C$, and 3 super-edges. Figure 1(b) is the graph it represents. The super-edge $(w,C)$ is expanded into the two edges $\{w,x\}$ and $\{w,u\}$.

We will show, using the probabilistic method, that the graph $G=(V,E)$ represented by a faction graph $G^{\star }=(V,F,E^{\star })$ has an independent set of size $\mathrm{\Omega }\left(\frac{{|V|}^2}{|E^{\ast }|+|V|}\right)$. This is similar to Turán’s theorem (Theorem 3). Our key observation is that we can obtain a much bigger lower bound on the size of an independent set, since $|E^{\ast }|$ can be asymptotically much smaller than $|E|$.

Let $N=|V|$ and $M^{\star }=|E^{\star }|$. If $E^{\star }=\mathrm{\varnothing }$, then $E=\mathrm{\varnothing }$, so $V$ is an independent set of $G$ of size $|V|$. Therefore, assume $M^{\star }>0$.

Since there are no edges in $E$ between two nodes in the same faction, every faction is an independent set. For each vertex $v\in V$, let $F(v)\in F$ be the faction that contains $v$ and let

By definition, $F(v)\notin {\mathrm{OutNhd}}^{\star }(v)$. Observe that

since every super-edge $(v,C)\in E^{\star }$ contributes exactly once to the sum.

We use the probabilistic method. Select each faction $A\in F$, independently, with some fixed probability $p\in (0,1)$, obtaining a random subset $F^{\prime }\subseteq F$. From $F^{\prime }$ build a random vertex set

consisting of every vertex whose faction was selected, but has no super-edge to any selected faction.

First, we show that $S$ is an independent set of $G=(V,E)$. Consider any two vertices, $u,v\in S$. If $F(u)=F(v)$, then $\{u,v\}\notin E$, since every faction is an independent set. So suppose $F(u)\ne F(v)$. By definition of $S$, $F(u),F(v)\in F^{\prime }$, so $F(v)\notin {\mathrm{OutNhd}}^{\star }(u)$ and $F(u)\notin {\mathrm{OutNhd}}^{\star }(v)$. Hence $(u,F(v)),(v,F(u))\notin E^{\star }$. By Definition 4, it follows the $\{u,v\}\notin E$.

Next, we get a lower bound on the expected size of $S$. For any fixed $v\in V$, the event that $F(v)\in F^{\prime }$ is independent of the event that $F^{\prime }\cap {\mathrm{OutNhd}}^{\star }(v)=\mathrm{\varnothing }$. Therefore

The function $f(x)={(1-p)}^x$ is convex for $p\in (0,1)$. By Jensen’s inequality [18],

Hence $𝔼\left[|S|\right]\ge Np{(1-p)}^{\alpha }$, where $\alpha =M^{\star }/N$.

We now choose a good value for $p$. Consider the function $g(p)=p{(1-p)}^{\alpha }$ on the interval $[0,1]$. Since its derivative is $g^{\prime }(p)={(1-p)}^{\alpha -1}\left(1-(\alpha +1)p\right)$, it follows that $g$ is maximized when $p=1/(1+\alpha )$. Using this value of $p$ gives

Since $\ln (1+x)\le x$ for $x>-1$, we have

Hence

Because $S$ is an independent set for every choice of $F^{\prime }$, it follows that $G$ contains an independent set $S$ of at least this size. $◀$

We note that bounded value contention is strictly more general than both write contention and register size. In particular, bounded write contention $\kappa$ implies value contention at most $\kappa$. However, the reverse does not hold because we can allow arbitrary many processes be simultaneously poised to write the same value to a register, without exceeding the value contention bound. Likewise, an upper bound, $C$, on the number of different values that can be written to a register (which is equivalent to a bound on register size) implies value contention at most $C$. Again, the reverse does not hold, since arbitrarily many different values can be poised to be written to a register in different executions, or at different configurations during the same execution without exceeding the value contention bound.

To see the intuition why we need this additional restriction on the algorithm to obtain a non-trivial lower bound, consider the following pseudocode:

Here, each process first writes its id to a shared register, door, and then reads this register. If it reads the id of another process, it immediately loses. Observe that we can add this code at the beginning of any Leader Election algorithm, since the last process to write to door will continue to the next part of the algorithm, if it does not crash. The previous step complexity lower bound proofs construct a worst-case execution by repeatedly selecting a set of processes that each perform one more step, one after the other [5, 10, 7]. However, in an execution that begins with a round in which every process takes one step, there is only one process that does not lose when it performs its second step. Consequently, this process will execute the next part of the algorithm by itself. For some algorithms, for example, one that uses a Splitter, this process will also terminate within a constant number of steps. However, in an execution in which no process writes to door between the write to door and subsequent read of door by the same process, all non-faulty processes reach the next part of the algorithm. Our bounded value contention does not allow all processes to be simultaneously poised to write their ids to the same register, so such an algorithm does not contradict our lower bound.

The main result of this section is the following:

We begin by giving an overview of the proof approach. We will construct a round-by-round execution, one round at a time. In each round, we have a set of active processes that each takes one additional step. We maintain the invariant that the processes do not see one another. In other words, for each active process, the execution is indistinguishable from a solo execution. Initially, all processes are active and the execution is empty.

To add an additional round, we consider the next step of all active processes and partition them into groups depending on what register they access, whether they read or write, and what value they read or what value they write. After that, we construct a conflict graph, where the nodes are the active processes and there is an edge between two processes if one of them sees the other in any extension of the current execution in which each active process takes one more step or if they write different values to the same register. We observe that this graph can be represented by a faction graph. Using Theorem 5, we select a sufficiently large independent set of active processes in the conflict graph. All other processes are erased from the execution and then each process in the independent set takes its next step. Similarly to Anderson and Kim [7], this ensures that each process only reads the initial value of a register or the last value that it wrote there. The construction continues until only one process remains.

Let $P_t\subseteq P$ be the set of active processes that participate in the current execution, ${ℰ}_t$. In this execution, no process in $P_t$ sees any other process, so, for all processes $p,q\in P_t$, $p{\sim }_{{ℰ}_t}q$ if and only if $p=q$. By Lemma 2, there is at most one process that has terminated at the end of ${ℰ}_t$. Each process in $P_t$ that has not terminated has taken exactly $t$ steps in ${ℰ}_t$. We also ensure that no two processes write different values to the same register in their $i$’th step in ${ℰ}_t$, for $1\le i\le t$. Initially, ${ℰ}_0$ is empty and $P_0=P$.

To create ${ℰ}_{t+1}$, we begin by partitioning the processes in $P_t$ into groups, where two processes are in the same group if, at the end of ${ℰ}_t$,

• $\mathrm{■}$

  they are poised to write the same value into the same register,

• $\mathrm{■}$

  they are poised to read the same register and they have never written to that register, or

• $\mathrm{■}$

  they are poised to read the same register and they last wrote the same value to that register.

If there is a process in $P_t$ that is terminated at the end of ${ℰ}_t$, it is put in a group by itself. For each register, there are at most $Q$ groups of processes writing different values to the register, there is at most one group of processes that is reading the register, but have never written to it, and there are at most $t$ groups of processes that are reading the register and last wrote to it in one of the previous $t$ rounds.

We need to show that we can choose sufficiently many active processes $P_{t+1}\subseteq P_t$, which each performs one more step, without letting it see any other process. Other active processes will be erased from the execution when creating ${ℰ}_{t+1}$. (Note that one of the processes in $P_{t+1}$ may have terminated.) To determine such a set of active processes, we construct a conflict graph. This is a graph with vertex set $P_t$, where there is an edge between two processes if one of them is poised to read a register from which it could see the other process or both are poised to write different values to the same register. The conflict graph can be represented by a faction graph, where the factions are the groups of processes. We will describe only the set of super-edges, $E^{\ast }$, of this faction graph from which the set of edges of the conflict graph can be deduced. Intuitively, we want to find an independent set in the conflict graph, remove all steps by other processes in ${ℰ}_t$, and add a round to the resulting execution to create ${ℰ}_{t+1}$.

There are two rules used to construct the super-edges of the faction graph:

Consider some process, $p$, that wrote a value to register $r$ during ${ℰ}_t$. Let $v$ be the value that $p$ last wrote to $r$. Let $A$ be a group of processes that are poised to read register $r$ and last wrote the value $v^{\prime }\ne v$ to register $r$ or a group of processes that are poised to read register $r$, but have never written to register $r$, and $v^{\prime }\ne v$ is the initial value of register $r$. In a solo execution, each process in $A$ would read the value $v^{\prime }$ when it performs this read. Then $(p,A)\in E^{\ast }$.

Consider a group of processes, $A$, poised to write value $v$ to a register $r$ and a group of processes, $B$, poised to write value $v^{\prime }\ne v$ to the register $r$. Then, $(p,B)\in E^{\ast }$, for all processes $p\in A$, and $(q,A)\in E^{\ast }$, for all processes $q\in B$.

Since all active processes take $t$ steps during ${ℰ}_t$, each process $p$ writes to at most $t$ different registers. For each register, $r$, to which it wrote, $(p,A)\in E^{\ast }$ by Rule 1, only if the processes in group $A$ are poised to read $r$. At most one value is written to $r$ in each round of ${ℰ}_t$, so there are at most $t-1$ groups of processes poised to read $r$ that last wrote a different value to $r$ than $p$ did. There is at most one group of processes poised to read $r$ that have never written to $r$. Hence, there are at most $t\cdot t=t^2$ groups $A$ for which $(p,A)\in E^{\ast }$ by Rule 1.

Suppose $(p,A)\in E^{\ast }$ by Rule 2. Then $p$ is poised to write a value $v$ to a register $r$ at the end of ${ℰ}_t$ and the processes in $A$ are poised to write a different value to register $r$ at the end of ${ℰ}_t$. Since the value contention of the algorithm is at most $Q$, there are at most $Q-1$ different groups that are poised to write values other than $v$ to register $r$ at the end of ${ℰ}_t$. Hence, there are at most $Q-1$ groups $A$ for which $(p,A)\in E^{\ast }$ by Rule 2.

In total, $|E^{\ast }|\le |P_t|\cdot (t^2+Q-1).$ Let $P_{t+1}$ be a maximum independent set in the conflict graph. By Theorem 5,

Since $P_t\setminus P_{t+1}$ is closed with respect to ${\sim }_{{ℰ}_t}$, removing the steps of all processes in $P_t\setminus P_{t+1}$ from ${ℰ}_t$ results in an execution. Let ${ℰ}_{t+1}$ be obtained from this execution by appending a round in which all processes in $P_{t+1}$ that are poised to read each take one step and then all processes in $P_{t+1}$ that are poised to write each take one step. Note that, by Rule 2, at most one value is written to each register during the last round of ${ℰ}_{t+1}$. Since at most one value is written to each register during each round of ${ℰ}_t$, the same is true for ${ℰ}_{t+1}$. Furthermore, since each process in $P_t$ that has not terminated takes exactly $t$ steps during ${ℰ}_t$, each process in $P_{t+1}$ that has not terminated takes exactly $t+1$ steps during ${ℰ}_{t+1}$.

Suppose there is a process, $q\in P_{t+1}$, in some group, $A$, that sees another process during ${ℰ}_{t+1}$. Since $q$ sees no other processes during ${ℰ}_t$, it must be that, during round $t+1$, $q$ read a value $v$ from register $r$ and, during ${ℰ}_t$, either $q$ did not write to $r$, or $q$ last wrote some value $v^{\prime }\ne v$ to $r$. By definition of the groups, the same is true for all processes in group $A$. Note that all writes to $r$ during round $t+1$ occur after $q$ read $r$. Let $p\in P_{t+1}$ be any process that last wrote $v$ to $r$ during ${ℰ}_t$. Note that $p\notin A$. By Rule 1, $(p,A)\in E^{\ast }$ is an edge in the faction graph. This implies that $\{p,q\}$ is an edge in the conflict graph, which contradicts the fact that $P_{t+1}$ is an independent set. Hence, no process in $P_{t+1}$ sees another process during ${ℰ}_{t+1}$.

Thus, the execution ${ℰ}_{t+1}$ has all the required properties. We repeatedly construct additional rounds until the remaining set of active processes has size 1. Note that, if $|P_t|>1$, it is always possible to choose $P_{t+1}$ so that it contains a process that takes $t+1$ steps during ${ℰ}_{t+1}$. Let $T$ be the first number such that $|P_T|=1$. Then ${ℰ}_T$ is a solo execution of length $T$.

It remains to show that $T\in \mathrm{\Omega }\left(\frac{\log N}{\log Q+\log \log N}\right)$. Recall that $|P_{t+1}|\ge \frac{1}{e}\cdot \frac{|P_t|}{Q+t^2}$, so

Rearranging and using the facts that $|P_0|=N$ and $|P_T|=1$, we obtain

Hence,

Let $N\ge 4$. Then $\log Q+\log \log N\ge 1$, since $Q\ge 1$. If $T\ge \log N$, then $T\ge \frac{\log N}{\log Q+\log \log N}$. So, assume that . In this case,

Since $Q,\log N\ge 1$, we have $Q+{(\log N)}^2)\le 2Q(\log N){}^2$, so $\log e+\log (Q+{(\log N)}^2)\le \log e+\log (2Q{(\log N)}^2)=1+\log e+\log Q+2\log \log N\in O(\log Q+\log \log N)$. Therefore, $T\in \mathrm{\Omega }\left(\frac{\log N}{\log Q+\log \log N}\right)$. $◀$

This theorem leads to some additional results. First, we observe that our lower bound argument can be applied directly to the more general class of non-deterministic solo-terminating algorithms [11], which includes randomized wait-free algorithms for the Leader Election problem.

By specializing the parametrization to focus on particular ranges of interest, we obtain the following two results.

We can also apply our theorem to adaptive Leader Election algorithms, where the step complexity depends on the number of processes that take at least one step, rather than on the total number of processes in the system.