No Symmetric Broadcast Abstraction Characterizes $k$-Set-Agreement in Message-Passing Systems

This paper considers distributed systems consisting of a set of asynchronous processes prone to crash failures. These processes communicate by sending and receiving messages across an asynchronous network and must cooperate to achieve a common goal. What makes distributed computing challenging is that the dynamics of the underlying network on which the distributed application operates are beyond the programmer’s direct control. This necessitates treating the environment as a “hidden input” forcing processes to manage uncertainty at runtime [20]. To facilitate the design of advanced algorithms in this unpredictable setting, it is usual to define appropriate communication abstractions, that allow modularity and help mitigate uncertainty by restricting communication patterns that may occur at a higher abstraction level.

In crash-prone asynchronous distributed systems, a significant source of uncertainty stems from the divergent perceptions of the event set (i.e., send and receive events) among different processes. Broadcast abstractions, which enable processes to transmit a message to all participants within the same operation, alleviate this issue by ensuring consistent and reliable communication across different nodes, thereby simplifying the complexity of managing individual send/receive operations and enhance fault tolerance by reducing the impact of node failures. Hence, message broadcasts (at least by correct processes) constitute a set of global events for which all correct processes eventually agree they took place, thereby establishing a system-wide communication foundation that enables cooperation and synchronization.

Another source of uncertainty arises from the disparate order in which different participants may receive messages, leading to varied perceptions of the global state of the system. Several communication abstractions have been defined by enforcing properties on the message delivery order. FIFO and Causal Ordering are examples of such properties at the heart of FIFO-broadcast and Causal-broadcast [3, 21]. These abstractions facilitate the construction of distributed objects, like causal memory in asynchronous message-passing systems [2].

This paper follows the quest of identifying broadcast abstractions that characterize the major fundamental problems in distributed computing. Specifically, we aim to determine broadcast abstractions that are computationally equivalent to particular synchronization problems in a crash-prone asynchronous message-passing system. This equivalence means that a deterministic algorithm based on the broadcast abstraction can resolve the synchronization problem regardless the number of crash failures, and vice versa.

A well-known such characterization is the equivalence between Total Order Broadcast and the consensus problem [6]. Consensus is a fundamental problem of distributed computing, that provides processes with a single operation, denoted $\text{propose}()$. This operation allows each process to propose a value and decide on a value. The defining properties of this problem are as follows: if a process invokes $propose(v)$ and does not crash, it will decide on a value (termination); no two processes will decide on different values (agreement); and the decided value must have been proposed by a process (validity). One of the primary practical applications of consensus is to maintain consistency across replicated machines in a message-passing system. However, State Machine Replication (SMR) [23] typically builds on an intermediate communication abstraction, the well-known and powerful Total Order Broadcast abstraction [18]. This abstraction ensures that the order of message delivery is consistent across all processes.

The consensus problem is famously unsolvable in an asynchronous distributed system, even under the assumption that at most one process may crash [10]. The same holds for Total Order Broadcast. Indeed, both abstractions are computationally equivalent: on the one hand, Total Order Broadcast allows an easy implementation of a consensus object; on the other hand, it can be implemented using consensus objects. In a sense, Total Order Broadcast precisely “characterizes” the essence of the consensus problem. In a similar vein, Mutual Broadcast was recently proposed as a broadcast abstraction equivalent to read/write atomic registers [8]. Moreover, Pair Broadcast characterizes the computational power of both test-and-set and consensus between two processes [9]. Such characterizing broadcast abstractions are instrumental for understanding the fundamentals of distributed computing problems by reducing their complexity into a logical property about the order in which different processes perceive the global events (a.k.a. broadcast invocations) occurring in the system.

Specifically, this paper delves into characterizing the $k$-set agreement problem ($k$-SA), a generalization of consensus introduced by S. Chaudhuri in [7]. In $k$-SA, the agreement property is weakened as follows: processes are allowed to collectively decide up to $k$ different values. Here, $k$ represents the maximum disagreement in the number of different values that can be decided. The smallest value $k=1$ corresponds to consensus. As $k$ increases, the problem becomes less constrained and may become easier to solve. However, it still embodies numerous complexities and challenges of distributed systems. It remains insoluble in a crash-prone asynchronous system when $k\le t$, where $t$ is the maximum number of processes in the system that may crash [4, 12, 22].

The exploration of a broadcast abstraction that characterizes $k$-SA was initiated in a work dedicated to the shared-memory model, which proposed $k$-Bounded Order Broadcast ($k$-BO Broadcast in short) [13]. The $k$-BO Broadcast abstraction limits the disagreement on the message delivery order among processes. Specifically, its ordering property asserts that every set of $k+1$ messages contains two messages delivered in the same order by all processes. In the special case where $k=1$, it boils down to Total Order Broadcast.

In crash-prone asynchronous systems where processes additionally have access to a shared memory composed of atomic read/write registers, $k$-BO Broadcast is computationally equivalent to $k$-set agreement. However, this equivalence in shared memory does not inherently translate to message-passing systems. Indeed, although $k$-BO broadcast can be used to solve $k$-set agreement on its own, it remains unproven whether it can be implemented using solely $k$-set agreement objects and send/receive operations. While consensus is strong enough to emulate atomic registers in a message-passing system, $k$-set agreement, for $k>1$, is unable to emulate shared memory. Indeed, it has been proved that on one hand, $k$-SA and a problem called the $k$-simultaneous-agreement are equivalent in shared memory systems [1], and on the other hand, the $k$-simultaneous-agreement problem is harder than $k$-SA in message-passing systems where a shared memory emulation is not possible [5]. A corollary of this paper is that the implementation of $k$-BO broadcast on top of $k$-SA is not feasible in message-passing systems.

A broadcast abstraction denoted as $B$, enables correct processes to broadcast messages that are guaranteed to be delivered at least to all correct processes. Consequently, all broadcast abstractions share the same interface, comprising a single operation named broadcast and an event called deliver.

A process $p_i$ invokes the operation “$B.\text{broadcast}(m)$” to utilize $B$ for broadcasting a message whose content is $m$. This is referred to as $p_i$ $B$-broadcasting a message whose content is $m$. Subsequently, the event “$B.\text{deliver}m\text{from}{p}_i$” might be triggered at some processes $p_j$, leading us to say that $p_{j}B$-delivers a message from $p_i$, whose content is $m$. Analogous to the send/receive interface, it is assumed that each broadcast message is unique, regardless of having identical content. However, for the seek of readability, we amalgamate a message and its content whenever the distinction is immaterial. The set of all messages that can be broadcast during an execution is denoted by $𝕄$. The following properties must be verified by all broadcast abstractions.

BC-Validity.

If a process $p_i$ $B$-delivers $m$ from $p_j$, then it is guaranteed that $p_j$ has previously $B$-broadcast $m$.

BC-No-Duplication.

A process will not $B$-deliver the same message more than once.

BC-Local-Termination.

If a correct process invokes $B.\text{broadcast}(m)$, it will eventually return from this invocation.

BC-Global-CS-Termination.

If a correct process $B$-broadcasts $m$, then all correct processes will eventually $B$-deliver $m$.

The first two properties mentioned are classical safety properties and share the same definitions as their send/receive counterparts. The third property is a classical liveness property. It is important to note that the BC-Global-CS-Termination property only applies to correct processes. (The abbreviation “CS”, standing for correct sender, emphasizes that this property is contingent on the sender’s correctness.) Consequently, if a process $p_i$ crashes during its execution of $\text{broadcast}(m)$, it is permissible for some processes to deliver $m$ while others do not, unless otherwise specified. This specification choice is intentionally made to allow for flexible definitions of liveness properties in broadcast abstractions.

In particular, the most basic broadcast abstraction that can be defined, only verifies the four properties defined above. In the $𝒞𝒜ℳ{𝒫}_n[\mathrm{\varnothing }]$ model, its implementation involves simply sending messages to all participants. For this reason, it is commonly referred to as Send-To-All Broadcast.

Broadcast abstractions can be characterized by additional predicates on the set of executions they admit. Typically, these predicates fall into two categories. On one hand, liveness predicates ensure message delivery in scenarios not covered by Send-To-All Broadcast. Examples of this include the definitions of Reliable Broadcast and Uniform Reliable Broadcast [11]. On the other hand, safety predicates concern the relative order in which processes deliver messages. Examples in this category are FIFO Broadcast, Causal Broadcast  [3, 21], Mutual Broadcast [8], Pair Broadcast [9], $k$-Bounded Order Broadcast [13], and Total Order Broadcast [18].

As highlighted in the Introduction, not all predicates are equally appropriate for the design of a broadcast abstraction. In this section, we introduce two novel symmetry properties inspired by the broader principle of “network neutrality”. Network neutrality advocates, among other tenets, that network services should not discriminate based on the content, sender, or usage of the messages they transmit. While concerns regarding network neutrality often arise in discussions about non-functional aspects of message routing, they hold significant relevance for the functional design of broadcast abstractions. Within this framework, we interpret network neutrality to include two essential symmetry properties: Compositionality and Content Neutrality. These properties assert that the broadcast abstraction should impartially treat all messages, irrespective of their usage or content.

$k$-Set agreement, first introduced by S. Chaudhuri in [7] (refer to [19] for a comprehensive survey of $k$-set agreement in various contexts), was conceptualized to analyze the relationship between the maximum number of allowable process failures ($t$) and the feasible degree of agreement ($k$) among processes. Here, a lower value of $k$ signifies a higher degree of agreement, with the ultimate agreement being $k=1$, which corresponds to consensus.

The $k$-Set agreement problem is a one-shot agreement problem that equips processes with a singular operation, denoted $\text{propose}()$. When a process $p_i$ invokes $\mathrm{𝑘𝑠𝑎}.\text{propose}(v_i)$ on a $k$-SA object $\mathrm{𝑘𝑠𝑎}$, it is said to “propose the value $v_i$ to $\mathrm{𝑘𝑠𝑎}$”. This operation yields a return value $v$, at which point the invoking process is described as “deciding $v$ on $\mathrm{𝑘𝑠𝑎}$”, and “$v$ becomes a decided value”. In other words, the steps $⟨p_i:\text{return}w\text{from}\mathrm{𝑘𝑠𝑎}.\text{propose}(v)⟩$ and $⟨p_i:\mathrm{𝑘𝑠𝑎}.\text{decide}(w)⟩$ are interpreted as synonymous. It is a standard assumption that each process is limited to a single invocation of $\text{propose}()$ on any given $k$-SA object, ensuring the problem’s one-shot nature. $k$-Set agreement is defined by the following properties.

$k$-SA-Validity.

If a process decides a value $v$, then $v$ was proposed by some process.

$k$-SA-Agreement.

No more than $k$ distinct values are decided upon by the processes.

$k$-SA-Termination.

Every non-faulty process that invokes $\text{propose}()$ eventually decides.

For brevity in this subsection, we pose $k>1$ and $N>0$. Additionally, we postulate the existence of a deterministic algorithm $ℬ$ that implements a certain broadcast abstraction $B$ within the model $𝒞𝒜ℳ{𝒫}_{k+1}[k\text{-SA}]$. The argument is then generalized to the case where $n>k+1$ in the proof of the main theorem. This is achieved by observing that processes $p_j$, for $j>k+1$, may fail at the beginning of the execution.

The adversarial execution ${\alpha }_{k,N,B,ℬ}$ is constructed by an adversarial scheduler that follows the procedure outlined in Algorithm 1. The scheduler decides when processes get executed, when messages are received, and which values get decided upon by $k$-SA objects. It produces an execution admitted by the model $𝒞𝒜ℳ{𝒫}_{k+1}[k\text{-SA}]$ as validated by lemmas 5 to 12, though it does not necessarily exploit all possibilities offered by the specification of the model.

The scheduler begins with a sequential execution of all processes, ranging from $p_1$ to $p_{k+1}$. During this phase, each process $p_i$ repetitively calls $B.\text{sync-broadcast}(\text{synch})$, where synch represents a message with void content used for synchronization purpose, until it has $B$-delivered $N$ of its own messages. This part of the execution remains indistinguishable to $p_i$ from an execution ${\gamma }_{k,N,B,ℬ,i}$, where other processes $p_j$ would have crashed before the local delivery of their own $N$ messages. To achieve this, processes decide on their own value on $k$-SA objects whenever possible, and the transmission of their messages to other processes is deferred by the scheduler until the end of this phase. However, a complication arises when all processes propose a value on the same $k$-SA object $\mathrm{𝑘𝑠𝑎}$. In such scenarios, $p_{k+1}$ is compelled to decide on the value proposed by $p_k$ to maintain the $k$-SA-Agreement property. This decision renders $p_{k+1}$’s execution distinguishable from a scenario where $p_k$ had initially crashed, allowing $p_{k+1}$ to await $p_k$’s message. As a result, all messages sent by $p_k$ to $p_{k+1}$ are received by $p_{k+1}$ (lines 1 to 1), and the messages that $p_k$ $B$-broadcast before this juncture are excluded from its count of $N$ messages.

Subsequently, in a later phase of the algorithm, all processes receive all messages that were sent to them in the initial stage but have yet to be received, as delineated in Line 1. Algorithm 1 concludes by returning the execution halted at this juncture. Notably, at this point of termination, not all messages that have been $B$-broadcast are necessarily $B$-delivered by every process. However, this does not pose a problem for our analysis: the counterexample required for the proof in the following section involves a safety property that is already violated in the execution prefix returned by the algorithm. The scheduler maintains the following main variables:

• $\mathrm{■}$

  $\alpha$, which is initially an empty sequence $\epsilon$, is the execution currently being constructed.

• $\mathrm{■}$

  $i$, which stores the identifier of the process currently under execution.

• $\mathrm{■}$

  $\mathrm{𝑠𝑒𝑛𝑡}$, initially set to $\mathrm{\varnothing }$, is a set of triplets. A triplet $⟨m,i,j⟩$ is included in $\mathrm{𝑠𝑒𝑛𝑡}$ when a message $m$ has been sent by process $p_i$ to process $p_j$, but has not yet been received by $p_j$.

• $\mathrm{■}$

  $\mathrm{𝑑𝑒𝑐𝑖𝑑𝑒𝑑}[\mathrm{𝑘𝑠𝑎}][j]$ is a two-dimensional associative array. The keys $\mathrm{𝑘𝑠𝑎}$ correspond to $k$-SA objects used in $ℬ$, and $j$ represents process identifiers. The values are either potential values that can be proposed to $k$-SA objects in $ℬ$, or a special value $\perp$ that cannot be proposed. For each $\mathrm{𝑘𝑠𝑎}$ and $j$, $\mathrm{𝑑𝑒𝑐𝑖𝑑𝑒𝑑}[\mathrm{𝑘𝑠𝑎}][j]$ is initially set to $\perp$. It is later updated to value $w$ when the process $p_j$ decides on $w$ for $\mathrm{𝑘𝑠𝑎}$.

• $\mathrm{■}$

  $\mathrm{𝑙𝑜𝑐𝑎𝑙}\mathrm{\_}\mathrm{𝑑𝑒𝑙}$ tracks the number of messages that process $p_i$ $B$-delivers from itself, while avoiding communication with other processes. Under normal conditions, $\mathrm{𝑙𝑜𝑐𝑎𝑙}\mathrm{\_}\mathrm{𝑑𝑒𝑙}$ cycles through values from $0$ to $N-1$ for each process $p_i$. However, if communication between processes $p_k$ and $p_{k+1}$ is inevitable during the execution of a $B.\text{sync-broadcast}(m)$ operation by $p_k$, $\mathrm{𝑙𝑜𝑐𝑎𝑙}\mathrm{\_}\mathrm{𝑑𝑒𝑙}$ is assigned a value of $-1$. This assignment signifies that $\mathrm{𝑙𝑜𝑐𝑎𝑙}\mathrm{\_}\mathrm{𝑑𝑒𝑙}$ will be reset to $0$ once $p_k$ completes its $B$-broadcast operation. Consequently, this setup enables $p_k$ to $B$-deliver $N$ of its own messages (excluding $m$) without engaging in communication.

• $\mathrm{■}$

  $\mathrm{𝑠𝑡𝑒𝑝}$ identifies the subsequent step to be executed by Process $p_i$, represented either by the pair $⟨p_i,\mathrm{𝑎𝑐𝑡𝑖𝑜𝑛}⟩$ or by the special value $\perp$ if the step is yet to be determined. In this context, there are two primary scenarios to consider. Firstly, if $p_i$ has initiated the $B.\text{sync-broadcast}$ operation but has not yet completed this invocation, then the deterministic algorithm $B$ is responsible for defining the subsequent step that $p_i$ must execute (Line 1). This step is crucial to fulfilling the BC-Local-Termination property of $B$ within the configuration $C(\alpha )$, which delineates its local state after the execution $\alpha$. In the second scenario, if the aforementioned condition does not hold, $p_i$ proceeds to $B$-broadcast a new message, specifically synch.

Definition 4 now outlines the adversarial executions ${\alpha }_{k,N,B,ℬ}$, ${\beta }_{k,N,B,ℬ}$, and ${\gamma }_{k,N,B,ℬ,i}$. Our subsequent objective is to demonstrate that ${\alpha }_{k,N,B,ℬ}$ qualifies as an admissible execution of the $𝒞𝒜ℳ{𝒫}_{k+1}[k\text{-SA}]$ model. It is required to verify that ${\alpha }_{k,N,B,ℬ}$ is well-formed (as per Lemma 10), upholds the three defining properties of the $k$-set agreement: $k$-SA-Validity (Lemma 5), $k$-SA-Agreement (Lemma 6), and $k$-SA-Termination (Lemma 7). and ensures compliance with the three properties of send/receive communication: SR-Validity (Lemma 8), SR-No-Duplication (Lemma 9), and SR-Termination (Lemma 12).