Brief Announcement: Non-Uniform Content-Oblivious Leader Election on Oriented Asynchronous Rings

The field of reliable distributed computing is characterized by the study of a wide range of failure models, from failures affecting specific processes [4, 17] to failures affecting communication channels, such as message omission failures, message addition failures or message corruptions [19]. In a recent paper, Censor-Hillel et al. [7] introduced a new interesting failure model for channels: the fully-defective asynchronous network. In this model, processes do not fail, but all messages in transit may be arbitrarily corrupted by an adversary. While the adversary can alter the content of any message, it cannot create or destroy messages.

This model is content-oblivious, meaning that messages carry no reliable content, not even the identity of the sender. The only information a message conveys is its existence.

Surprisingly, Censor-Hillel et al. [7] showed that if a leader process is initially known and the topology is 2-edge-connected, it is possible to simulate a reliable, uncorrupted message-passing network, even in asynchronous settings, within this fully-defective model.

This result makes studying leader election algorithms for this model particularly compelling: if a leader can be elected in a certain topology, with an algorithm that is terminating and where it is possible to distinguish in some way the messages of the leader election algorithm, then on such topology any asynchronous algorithm can be simulated even if all messages are arbitrarily corrupted. In this regard, Censor-Hillel et al. [7] conjectured that electing a leader was impossible in content-oblivious model and thus that having a leader was a necessary requirement. We stress that electing a leader is a fundamental problem in the classical message-passing setting, and it has been extensively studied in systems with unique identifiers [1, 12, 16, 18] and in anonymous networks [2, 3, 8, 21].

Frei et al. [13] disproved the aforementioned conjecture for a notable family of 2-edge-connected networks: oriented ring topologies. In an oriented ring, processes have a common notion of clockwise and counter-clockwise direction. More specifically, Frei et al. [13] proposed a quiescently terminating leader election algorithm with a message complexity of $O(n{\mathrm{𝖨𝖣}}_{\max })$, where ${\mathrm{𝖨𝖣}}_{\max }$ is the maximum identifier in the system. The quiescent termination of the algorithm allows it to be composed with the simulator of Censor-Hillel et al. [7] and thus implies that the presence of unique identifiers is enough to simulate any asynchronous algorithm on a content-oblivious oriented ring.

Additionally, Frei et al. [13] proved that, for any uniform algorithm, there exists an identifier assignment under which the algorithm must send $\mathrm{\Omega }\left(n\log \frac{{\mathrm{𝖨𝖣}}_{\text{max}}}{n}\right)$ messages. Although originally established for the uniform setting, this lower bound can be extended to the non-uniform setting, even when the exact value of $n$ is known; see the full version of the paper for details.

In anonymous systems, where processes lack identifiers, Frei et al. [13] showed a randomized leader election algorithm using $n^{O(c^2)}$ messages and succeeding with probability $1-n^{-c}$, but without explicit termination. In fact, Itai and Rodeh [15] proved that no uniform algorithm can both elect a leader and guarantee explicit termination in anonymous systems without additional assumptions. We stress that the lack of explicit termination does not allow the composition of this algorithm with the simulator of Censor-Hillel et al. [7].

Finally, we want to mention the related line of research of the beeping model [5, 6, 9, 20], where in each round a process may either emit a beep to its neighbors or listen. This model is inherently synchronous. Therefore, the techniques developed for leader election in the beeping model [10, 11, 14] cannot be applied in content-oblivious networks.

We consider a system composed of a set of $n$ processes $P=\{p_0,p_1,\mathrm{\dots },p_{n-1}\}$ that communicate on a ring network by sending messages to each other. More precisely, a process $p$ has two local communication ports: port $0$ and port $1$. By means of a specific port, a process is able to send messages to and receive messages from one of its neighbors.

When the system is not anonymous, processes have unique identifiers that are arbitrarily selected from $\mathbb{N}$.

We assume an asynchronous system; that is, each message has an unpredictable delay that is finite but unbounded. A message cannot be lost. Messages are buffered, in the sense that if several messages are delivered to a process at the same time, they are stored in a local buffer and can then be retrieved by the destination process at its discretion. The local computation time at each process may be arbitrary but bounded, and processes do not share a notion of common time.

Processes are correct and do not experience any kind of failure.

We now describe an algorithm where each process sends $O(U{\mathrm{𝖨𝖣}}_{\min })$ messages in the clockwise direction, and just 3 messages in the counter-clockwise direction. This algorithm is of interest as it shows that our claim below needs the uniformity assumption:

The Constant Direction Algorithm, pseudocode in Algorithm 1, starts in a competing phase. In the competing phase, blue lines, a process $p$ with identifier $\mathrm{𝖨𝖣}$ performs a loop of $U\mathrm{𝖨𝖣}$ iterations. In each iteration, the process sends a message in the CW direction and waits for a message from the CW direction. This phase synchronizes the processes so that the indices of any two processes in the phase loop can differ by at most $n-1$. The process with the minimum identifier will be the only one to end the competing phase by completing the prescribed number of iterations.

This process then enters the termination detection phase (green lines). In this phase, the process first sends a message CCW to inform all other processes that they are not leaders. Once this message returns, it sends a second CCW message while starting to relay CW messages; when this second message will be received back the process will know that all CW messages in the network are eliminated. Finally, once the second message is received, it sends a third and final CCW message to terminate the algorithm.

A process whose identifier is not the minimum will enter the relay phase (red lines) upon receiving and relaying a message from the CCW direction. In the relay phase, the process first waits to receive a CW message, in order to eliminate the CW message it sent during the competing phase, and afterwards it relays both CCW and CW messages it receives. A non-leader process terminates after receiving three CCW messages.

We now describe an algorithm in which each process sends $O(U\log {\mathrm{𝖨𝖣}}_{\min })$ messages. The algorithm uses an encoding of identifiers such that the smallest identifier is not a prefix of any other identifier, and the last bit of every encoded identifier is $0$. To achieve this, given an identifier $\mathrm{𝖨𝖣}$ of bit length $\mathrm{\ell }$, we encode it as $1^{\mathrm{\ell }}0\cdot \mathrm{𝖨𝖣}\cdot 0$.

The algorithm elects the process with the minimum identifier and proceeds in elimination rounds. In each round, active processes compare a specific bit of their (encoded) identifiers, eliminating all processes that do not have the minimum bit at that position.

The bound $U$ on the network size is used to synchronize processes across different rounds of the algorithm. When an active process enters a round, it begins the Synchronization phase. In this phase, each active process sends and receives messages in the CW direction for $U$ steps. Then, processes with bit $0$ send and receive one message in the CCW direction, blocking messages in the CW direction (this is the Zero Signaling phase). Meanwhile, processes with bit $1$ attempt to continue sending and receiving messages in the CW direction for another $U$ steps. However, they become inactive if they receive a CCW message, indicating the presence of a process with bit $0$ (this is the No-Zero Checking phase).

The rationale for these phases is to ensure that processes with bit $1$ proceed to the next round in the active state if and only if no process with bit $0$ exists in the current round. Indeed, when processes with bit $0$ stop propagating CW messages, the processes with bit $1$ are prevented from completing their No-Zero Checking phase.

Conversely, a process with bit $0$ in a given round remains active. The Synchronization phase described above ensures that once an active process completes this phase for a new round, all active processes have completed the previous round and are in the Synchronization phase of the current round.

An inactive process relays messages, and while doing so, it eliminates the first CW message it receives. This guarantees that, once all inactive processes have eliminated one message, the total number of messages in the network equals the number of active processes. Therefore, once all processes except the one with the minimum identifier have been eliminated, only a single message remains in the network.

The algorithm terminates after $|{\mathrm{𝖨𝖣}}_{\min }|=O(\log {\mathrm{𝖨𝖣}}_{\min })$ rounds. At this point, the only remaining active process is the one with the minimum identifier. This process can detect this locally and communicates it to all other processes (which are, by construction, inactive) by sending an additional message in the CCW direction (this is the Termination phase).

All other processes detect termination when they receive two consecutive messages in the CCW direction: the first sent during the Zero Signaling phase by the process with the minimum identifier, and the second sent during the Termination phase. Therefore, we have the following theorem.

In our randomized algorithm, each process samples its $\mathrm{𝖨𝖣}$ uniformly at random from the set $\{0,1,2,\mathrm{\dots },2^{\lceil c_1\log U\rceil }-1\}$. With probability at least $1-U^{2-c_1}$, all processes receive distinct identifiers. The bit-by-bit comparison algorithm from Section 4 is then executed using these random identifiers.

This sampling strategy yields a useful property: for any fixed bit index $i$, every maximal consecutive sequence of processes whose bit $\mathrm{𝖨𝖣}[i]$ equals $1$ has length at most $\lceil c_2\log U\rceil$ with probability at least $1-U^{1-c_2}$. This property reduces the number of steps in the Synchronization and No-Zero Checking phases of the algorithm in Section 4 from $U$ to $\lceil c_2\log U\rceil$, thereby improving the message complexity and establishing our final theorem.