On the Decidability of Distributed Tasks with Output Sets under Asynchrony and Any Number of Crashes Timothé Albouy # IMDEA Software Institute, Spain
Antonio Fernández Anta # IMDEA Software Institute and IMDEA Networks Institute, Spain
Chryssis Georgiou #
arXiv:2604.06920v1 [cs.DC] 8 Apr 2026
University of Cyprus, Cyprus
Nicolas Nicolaou # Algolysis Ltd, Cyprus
Junlang Wang # IMDEA Software Institute and Universidad Carlos III de Madrid, Spain
Abstract In this paper, we define a new class of distributed tasks, called SOS tasks (for Set of Output Sets tasks), defined by the set O of distinct output sets of values that can be produced. We then demonstrate that this class of tasks is decidable: there exists an effective procedure that determines whether any SOS task is solvable asynchronously under t crashes. The decision rule is as follows. Every SOS task is solvable when t = 0. For t > 0, an SOS task is solvable if and only if its SOS graph G = (O, ⊂) is connected. In this graph, each vertex is an output set in O, and two vertices are linked by an edge whenever one output set includes the other. One of the surprising implications of our results is that, without a validity property, k-set agreement is solvable under any number of crashes t ≥ 0 for k > 1, and unsolvable under t > 0 crashes only for k = 1 (consensus). Finally, we study a novel family of tasks called d-disagreement, which requires the system to always produce d different output values, and we show that its implementability condition is related to the harmonic series. 2012 ACM Subject Classification Theory of computation → Distributed algorithms Keywords and phrases Solvability, Decidability, Asynchrony, Impossibility proofs, Distributed tasks, Crash tolerance, Consensus, k-set agreement, Disagreement. Funding This work has been partially supported by the Spanish Ministry of Science and Innovation under grants SocialProbing (TED2021-131264B-I00) and DRONAC (PID2022-140560OB-I00), the ERDF “A way of making Europe”, NextGenerationEU, and the Spanish Government’s “Plan de Recuperación, Transformación y Resiliencia”. This work is part of the grant CEX2024-001471M/funded by MICIU/AEI/10.13039/501100011033.
1
Introduction
Many problems studied in distributed computing can be represented as tasks, i.e., abstractions where every participant has at most one input value and at most one output value. Consensus, for example, is a task where each participant proposes a value (the inputs), and all participants must decide on the same value (the outputs) from among the initial proposals. Although tasks cannot capture some distributed problems (in particular, long-lived primitives such as shared registers or transactional objects), they remain a particularly useful abstraction for studying the solvability boundaries of distributed computing.
2
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
Towards a theory of distributed decidability One of the grand challenges of distributed computing involves determining which families of distributed problems are decidable and which ones are not. Decidability in this context means that there exists an effective procedure determining if a given distributed problem is solvable in a given computing model or not. It has been shown that distributed computing as a whole is undecidable, as undecidable families of tasks have been identified within it, in particular, the class of asynchronous tasks under at least 2 crashes [10, 13]. But undecidability in the general case does not prevent some classes of tasks to still be decidable: indeed, all asynchronous tasks under at most 1 crash [3, 4, 18], or in the presence of only initial crashes [22], are decidable. The present work is part of this endeavour: it focuses on a particular class of tasks that we call SOS tasks, and it shows that there exists a procedure determining whether any of these SOS tasks can be implemented asynchronously under any number of crashes. Eventually, by progressively identifying new classes of decidable and undecidable tasks, it will be possible to build an exhaustive theory of distributed decidability that is as fundamental to this field as computability theory is to sequential computing. The limitations of traditional approaches Traditionally, a distributed task is defined as one specific triplet (I, O, →), where I and O are respectively the input and output domains of the task, and → is a mapping between the inputs and outputs. In this context, combinatorial topology is one of the most powerful approaches for studying the solvability and decidability of tasks [12]. With combinatorial topology, the input and output domains I, O are modelled as simplicial complexes, and the mapping → is a carrier map (representing the task specification) between the input simplexes and output simplexes. However, this traditional approach has some limitations. Rigidity of the classical task definition. In distributed computing, problem definitions are often not limited to a single triplet (I, O, →), as they can allow multiple implementations that each have different possible triplets (I, O, →). For instance, median consensus (which must decide the median value from those proposed) and majority consensus (which must decide the most frequent value from those proposed) are represented as two different triplets (I, O, →) as they do not entail the same mapping between the inputs and outputs, however they are both valid solutions to the consensus problem [9]. Restricted expressiveness of simplicial complexes. An important requirement of simplicial complexes is that they must be “closed under inclusion”, which means that, for each simplex in a complex, all its subsimplexes must also be in the complex. In practice, this means that many important distributed problems cannot be effectively captured by simplicial complexes. For instance, the output of tasks like strong symmetry breaking (SSB) [16], renaming [7], or election [21, 16] cannot be captured as classical simplicial complexes, as they have executions where the processes of the system output multiple distinct values (e.g., 0 and 1), but they do not have executions producing each of these values individually (resp., executions for 0 and executions for 1). To address this limitation, some approaches rely on colored simplicial complexes, but doing so introduces significant additional complexity. Our approach: focusing on the output sets of tasks In this paper, we address the previous limitations of traditional approaches by developing a novel way of defining and studying tasks. More precisely, we depart from the classical method where a task is defined as a triplet (I, O, →), and develop a new framework relaxing the closedness constraint of simplicial approaches, and allowing tasks to have multiple valid instances. Building upon this framework, we extend the Set of Output Sets (or SOS) approach introduced by Albouy et al. for considering tasks with binary output values [2]. To this
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
end, we formalize and define the class of SOS tasks, capturing both binary and multivalued output sets, where validity, output multiplicity, and process identities are disregarded. These SOS tasks are defined by the set of distinct output values that they can produce across their executions, called their set of output sets. Our approach does not capture the class of tasks that are reliant on validity or process identities for instance, but in exchange, it allows us to identify a new class of distributed decidability via the study of SOS tasks (whereas it has been shown that the classical approach is undecidable [10, 13]). Contributions and roadmap Our contributions are the following. A novel framework for studying distributed tasks. We introduce in Section 2 a new methodology for expressing and analyzing tasks. Specifically, we present in Section 2.1 our computing model, with its abstract communication medium that can be realized asynchronously under any number of crashes from traditional models such as messagepassing or shared memory. We then describe in Section 2.2 a new formalization of tasks generalizing the classical approach, enabling tasks to have multiple valid implementations, and allowing us to precisely define the solvability and decidability of tasks. A new class of distributed decidability: SOS tasks. We study in Section 3 the particular class of SOS tasks TO , which are defined by the set of output sets O that they can produce. We then show that this class is decidable, i.e., we provide a decision rule for determining whether any SOS task TO can be solved asynchronously under some number of crashes t. This rule can be stated as: TO is always solvable if t = 0, and it is solvable with t > 0 if and only if the graph G = (O, ⊂) is weakly connected. The vertices of this graph are the output sets in O, and its edges are derived from the inclusions between these output sets.1 Interestingly, our results have direct implications for k-set agreement. Indeed, we can define validity-less k-set agreement as an SOS task, and show that it can be solved under more than k crashes for k > 1, but only without crashes for k = 1 (consensus). Hence, this demonstrates a fundamental cut between consensus and >1-set agreement. To the best of our knowledge, we are the first ones to study the decidability of a particular subclass of tasks under any crash tolerance, instead of studying the decidability of all tasks under a specific crash tolerance. A particular family of SOS task: d-disagreement. Finally, we look at a special case of SOS tasks, which we call d-disagreement, and which requires the system to always produce d different output values (hence the system “disagrees”). This problem can have multiple interesting applications, especially in the context of fault-tolerant load balancing. For example, if a distributed system has to execute d idempotent jobs J1 , ..., Jd in parallel in the presence of up to t crashes, d-disagreement can be used, such that every process with output value i ∈ [1..d] executes job Ji . This effectively guarantees that all jobs are eventually executed despite crashes. The d-disagreement problem was introduced in its binary version by Albouy et al. [2], but the present paper provides its definition in terms of SOS tasks and generalizes it to the multivalued case. We then provide an impossibility proof and an algorithm demonstrating that the implementability condition of d-disagreement is tied to the harmonic series. Indeed, under t crashes, the number of processes required to solve disagreement is approximately Hd (t + 1), where Hd is the d-th harmonic number. Section 5 exposes the research landscape in which this work is situated, and concluding
1
Specifically, we consider the undirected version of G, which is sometimes referred to as the comparability graph of (O, ⊂).
3
4
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
remarks are provided in Section 6. For presentation clarity and completeness, we provide the full correctness proof of our first algorithm in Appendix A, and we provide new proofs for the necessity and sufficiency of non-resilient SOS tasks in Appendix B.
2
Computing Model and Problem Formalization
For clarity, we provide in Table 1 a list of concepts and notations used in this paper.
2.1
Computing Model
Process model. We consider a distributed system with a set P = {p, p′ , ...} of processes (|P | = n). Processes are deterministic computing entities that take steps according to their local state and the events they observe, following an algorithm A. Failures are restricted to crash faults: in an execution of the system, a process may halt prematurely and take no further steps, but it does not deviate from its algorithm before crashing. We assume an upper bound t on the number of processes that may crash in an execution, with 0 ≤ t ≤ n. A process that does not crash in an execution E is said to be correct in E. We also assume that all processes have access to their own private local clocks, which may run at a different pace, and which allow them to set local timeouts. Communication model Processes interact through a generic asynchronous communication medium that is reliable: it does not suppress, duplicate, or corrupt communicated information. Every process p ∈ P has access to two abstract operations: communicate I: process p disseminates some information I to all the system processes; observe I (callback event): process p is notified that information I was communicated. The medium guarantees that all correct processes eventually obtain a consistent view of the set of communicated information, while crashed processes may only have partial but always valid views. More formally, the communication abstraction satisfies the following properties (the “C” prefix stands for “communication”). C-Validity: If a process p observes information I, then I must have been previously communicated by some process p′ . C-Integrity: Any process p observes some information I communicated by a given process p′ at most once. C-Local-Termination: If a correct process p communicates information I, then some correct process p′ (if there is any) eventually observes I. C-Global-Termination: If a correct process p observes information I, then all correct processes eventually observe I. (Note that these properties are similar to those of reliable broadcast.) These communicate/observe operations can be implemented straightforwardly on top of classic asynchronous communication media such as message-passing networks or shared memory, regardless of Concept or notation Meaning p∈P Process p in the set of processes in the system P n Number of processes in the system (0 ≤ n = |P |) t Upper bound on the number of crashed processes (0 ≤ t ≤ n) T, A, E Task, algorithm, execution V, U Universe of values, Universe of pairs of input/output vectors ⊥ Sentinel value denoting no input/output (⊥ ∈ / V) Vin , Vout ∈ (V ∪ {⊥})n Input and output vectors of size n ⋆ Unspecified value Table 1 Concepts and notations used in this paper.
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
the number of crashes t [11]. We emphasize that our model does not place any bounds on communication delays. Therefore, any ordering or timing of observations that is consistent with the above properties can occur. This assumption is standard in asynchronous models and is only used in some of our correctness proofs (namely, Theorem 4 and Theorem 28).
2.2
Problem Formalization
Input and output vectors For some n ∈ N, a given instance of a distributed task takes 1 n 1 n an input vector Vin = (vin , ..., vin ) and returns an output vector Vout = (vout , ..., vout ), where i i the i-th value vin in Vin (resp. vout in Vout ) corresponds to the input (resp. output) value of process pi ∈ P . The values in the input and output vectors belong to the set V ∪ {⊥}, where V is the universe of values (of finite size) and ⊥ ∈ / V is a sentinel value that represents no input or no output. In an execution, a process p ∈ P can output at most one value v using the operation output v (multiple invocations of output by p must be for the same value v). S Let us define the universe of all pairs of input/output vectors as U = n∈N ((V ∪ {⊥})n ) × (V ∪ {⊥})n ): the n-exponentiation gives the set of all possible vectors of size n and the union merges all pairs of different sizes obtained previously. Task instances, tasks, and algorithms A task instance τ is a nonempty set of pairs (Vin , Vout ) of input/output vectors of the same size, representing all admissible input-output mappings of that instance. A task T = {τ1 , τ2 , ...} is a set of task instances. A task T is solvable under asynchrony and t crashes if at least one of its instances τ ∈ T can be implemented by some asynchronous algorithm tolerating up to t crashes. Informally, an algorithm A implements a task instance τ under asynchrony and up to t crashes if the set of (Vin , Vout ) pairs that A can produce across all its executions is exactly τ . A task instance τ supports a system size n if it contains at least one pair of vectors of size n; likewise, an algorithm A supports a system size n if it admits executions with n processes. A class of tasks T = {T1 , T2 , . . .} is decidable under asynchrony and up to t crashes if there exists an effective procedure determining whether each task in T is solvable. Set of output sets (SOS) We define the output set of an output vector Vout as the set of distinct output values in Vout , ignoring order, multiplicity, and ⊥: OS(Vout ) = i i {vout ∈ Vout | vout ̸= ⊥}. The set of output sets (SOS) of a task instance τ is then SOS(τ ) = {OS(Vout ) | (Vin , Vout ) ∈ τ }. Every SOS O ⊆ 2V must be non-empty, but O can contain the empty set if the task instance has executions that produce no output values. As V is finite, then O is also necessarily finite. SOS tasks Given some set of output sets O, an SOS task TO is a task that, for every defined system size n, contains all instances that (i) produce SOS O and (ii) have a full mapping between input and output vectors of the same size (meaning that inputs are not used to determine outputs, hence the task is “validity-less”). More formally, we have the following. ▶ Definition 1 (SOS task). An SOS task TO with SOS O ⊆ 2V , O = ̸ ∅ is defined as follows. Let τn be the subset of τ containing all pairs of vectors of size n. TO = τ ⊆ U, τ ̸= ∅ ∀ n ∈ N : τn ̸= ∅ =⇒ SOS(τn ) = O (constraint (i)) ∧ (∀(Vin , ⋆), (⋆, Vout ) ∈ τn : (Vin , Vout ) ∈ τn ) . (constraint (ii)) For example, consider a task instance τ that must produce O = {{1}, {1, 2}} for pairs of vectors of size n = 2 given V = {1, 2}. Constraint (i) requires that the output sets produced
5
6
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
across all pairs in τ2 are exactly O. Concretely, τ2 must contain some output vectors in {(1, 1), (1, ⊥), (⊥, 1)} to yield output set {1} ∈ O, and some output vectors in {(1, 2), (2, 1)} to yield output set {1, 2} ∈ O. Constraint (ii) requires that every input vector in τ2 (e.g., (1, 1), (1, 2), (2, ⊥), ...) is paired with each of these output vectors (i.e., inputs do not constrain outputs). In other words, τ2 is the full Cartesian product of all size-2 input vectors with all size-2 output vectors whose output sets lie in O. Therefore, solving an SOS task TO under asynchrony and t crashes reduces to providing an asynchronous algorithm A tolerating up to t crashes and satisfying constraints (i) and (ii) of Definition 1. To satisfy constraint (ii), it suffices that A ignores the input values of the processes: for a given size n, if all output vectors can be produced regardless of the input vector, then there is a total mapping between inputs and outputs. To satisfy constraint (i), A must fulfill the following two properties. Safety: Every execution of A produces an output vector Vout such that OS(Vout ) ∈ O. Completeness: For every system size n supported by A and every output set o ∈ O, there is an execution of A producing an output vector Vout of size n such that OS(Vout ) = o.
3
SOS Tasks are Decidable
In this section, we prove our main theorem (Theorem 3), stating that the entire class of SOS tasks is decidable under asynchrony and any number of crashes t. More precisely, we can determine whether any SOS task TO is solvable or not in an asynchronous system with up to t crashes.
3.1
Preliminaries and main theorem
Our SOS task classification relies on the concept of SOS graphs, defined as follows. ▶ Definition 2 (SOS graph). Given an SOS task TO with an SOS O, the SOSGraph(O) function returns the SOS graph (O, E) of TO , where the set of edges is E ≜ {{o, o′ } | o ⊂ o′ ∨ o′ ⊂ o}. Informally, the SOS graph of an SOS task TO links every pair of compatible output sets o, o ∈ O, in the sense that it would not break safety if some processes “think” that the system produces o, while some other “think” that the system produces o′ . Notice that the SOS graph of an SOS O is just the undirected version of the graph (O, ⊂). For notational convenience, we say that an SOS is connected if its SOS graph is connected, and disconnected otherwise. Likewise, we say that an SOS task is connected if its SOS is connected, or disconnected otherwise. We give in Figure 1 two examples of connected and disconnected SOS graphs. We can now state our main theorem. ′
▶ Theorem 3 (Decidability of SOS tasks). An SOS task TO with output set O can be solved asynchronously under up to t ∈ N crashes if and only if t = 0 or SOSGraph(O) is connected. 1, 2
1, 3 1
2, 3 3
1, 2
1, 3
2, 3
1
Figure 1 Examples of a connected SOS graph (on the left) for SOS {{1}, {3}, {1, 2}, {1, 3}, {2, 3}} and a disconnected SOS graph (on the right) for SOS {{1}, {1, 2}, {1, 3}, {2, 3}}.
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
7
Algorithm 1 Asynchronous algorithm implementing all connected SOS tasks TO with SOS O S assuming n ≥ |V |(t + 1), where V = O is the set of all output values in O. 1
instantiation parameters: a finite walk SOSWalk O of SOSGraph(O).
initialization: pick a set of leader processes Pleader ⊆ P such that |Pleader | > t; given V = the set of all possible output values in O, create partition P1 , ..., P|V | of P s.t. ∀ i ∈ [1..|V |], |Pi | > t. 3 code of every process pleader ∈ Pleader is 4 for i = 1 to |SOSWalk O | do 5 if i ̸= |SOSWalk O | then communicate move(i + 1); 6 wait for a predefined local time; 7 if pleader observed move(i + 1) from less than |Pleader | leaders then 8 communicate outputSet(oi ); 9 break.
2
S
O
code of every process pv ∈ Pv , v ∈ V is upon pv observes some outputSet(o) where v ∈ o do 12 output v; 13 exit.
10
11
Therefore, SOS tasks can be partitioned into two subclasses: (1) the SOS tasks that can tolerate any number of crashes (their SOS graph is connected), and (2) the SOS tasks that do not tolerate any crash (their SOS graph is disconnected). The proof of the above theorem follows from Algorithm 1/Theorem 4, presented in the next section and addressing case (1) for connected SOS tasks, and from Theorem 24 and Algorithm 3/Theorem 28, presented in Appendix B and addressing case (2) for disconnected SOS tasks. (The results presented in Appendix B are quite close to those of [18], however, the translation between the two models is not straightforward, hence we provide our own proofs in the appendix for completeness.) Notice that the SOS task TO with SOS O = {∅} can be trivially solved under any number of crashes, simply by having all processes of the system do nothing. Therefore, for the sake of simplicity, we consider in our classification that the empty graph G = (∅, ∅) is a special case of a connected graph, but in the remainder of this section, we only consider SOS tasks TO whose SOS O is different from {∅}.
3.2
Asynchronous t-resilient algorithm for any connected SOS
In this section, we introduce Algorithm 1, a universal t-resilient algorithm that can produce any SOS task TO with a connected SOS O under any number of crashes t ≥ 0, provided that S n ≥ (t + 1)|V |, where V = O is the set of all output values in O. This algorithm does not guarantee tightness in the sense that the proportion t/n of crashes tolerated in the system is usually lower than what is optimal, but it shows the solvability of all connected SOS tasks under any number of crashes t. The algorithm is instantiated (line 1) by providing as a parameter SOSWalk O , a finite walk2 that visits all output sets in SOSGraph(O) (recall that, in graph theory, a walk is similar to a path, but the same edge or vertex can be visited multiple times in a walk). By assumption, G = SOSGraph(O) is a connected graph, hence it is straightforward to construct a walk SOSWalk O that visits all vertices of G. SOSWalk O = (o1 , o2 , ...) is encoded as a sequence of output sets that can be iterated in order.
2
A finite walk SOSWalk O can always be constructed as the SOS O is finite by definition (see Section 2.2).
8
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
At the initialization of the algorithm (line 2), a set of more than t leader processes Pleader ⊆ P is selected, ensuring that at least one leader process does not crash. We then create a partition of |V | distinct exhaustive subsets of P (where V is the set of all output values in O), each of size greater than t and associated with a distinct value v ∈ V . We only assume n ≥ |V |(t + 1), hence every leader process pleader ∈ Pleader is also contained in some subset Pv of the partition of P . Each leader processes pleader ∈ Pleader iterates i from 1 to |SOSWalk O | (line 4). If i is smaller than |SOSWalk O |, pleader communicates move(i + 1) (line 5). After waiting a predefined local time (line 6), pleader checks whether it observed move(i + 1) from all other leaders (line 7). If it is not the case, pleader communicates outputSet(oi ) with the i-th element in SOSWalk O (line 8) and then exits the loop (line 9). When a process pv ∈ Pv (where v ∈ V ) observes some outputSet(o) information such that v is in o, pv outputs v (line 12) and exits (line 13). Correctness proof This section outlines the proof of Theorem 4, stating the correctness of Algorithm 1. For the sake of presentation, we defer the full proof of this theorem to Appendix A. ▶ Theorem 4 (Correctness of Algorithm 1). Algorithm 1 implements any given connected SOS task TO with SOS O under asynchrony and up to t crash failures, assuming n ≥ |V |(t + 1), S where V = O is the set of all possible output value in O. Proof sketch. We prove safety and completeness separately. Safety. The key insight is that, in any execution, the set of output sets communicated by leader processes (denoted LeadersOutputSets) is either a singleton {oi } or a pair {oi , oi+1 } of consecutive elements in SOSWalk O . This is because, once any leader communicates outputSet(oi ) and exits the loop, no leader can advance past iteration i + 1: it will not observe all |Pleader | move(⋆) for iteration i + 2, and will itself communicate outputSet(oi+1 ) and exit the loop. Since each process pv ∈ Pv outputs v only upon observing some outputSet(o) with v ∈ o, the output set produced by any execution is the S union LeadersOutputSets. In the singleton case, this union is oi ∈ O. In the pair case, since oi and oi+1 are adjacent in SOSWalk O , one must include the other by definition of the SOS graph, so their union equals the larger of the two, which is also in O. Completeness. We show that for every output set oi appearing in SOSWalk O , there exists an execution where LeadersOutputSets = {oi }. This is achieved by a crash-free execution with a delay pattern such that all leaders advance in lockstep through iterations 1, . . . , i − 1 (each observing all move(⋆) before the wait expires), but at iteration i, asynchrony causes the move(⋆) to arrive too late, so all leaders enter the condition at line 7, communicate outputSet(oi ), and exit the loop. Since |Pv | > t for every value v ∈ V , at least one correct process in each relevant partition outputs its value, producing exactly oi . ◀
3.3
The case of k-set agreement
Our decidability results for SOS tasks have surprising implications, especially in the case of k-set agreement [8], a family of tasks that output at least one and at most k ∈ N∗ different values among the input values. Consensus is a special case of k-set agreement where k = 1. It has been shown that k-set agreement under asynchrony and up to k crashes is impossible [20, 15, 6], if the validity of the task is considered (i.e., decisions are proposals). However, it is interesting to note that this validity assumption is unnecessary to prove the impossibility of 1-set agreement/consensus [9, 1]: to preclude trivial implementations, it only suffices to require that consensus “sometimes” produces different output values, without
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
9
imposing that the output values are also input values. Our work demonstrates a remarkable discontinuity in k-set agreement: its impossibility relies on validity only for k ≥ 2, but not for k = 1. In the following, we define via our formalism the family of “validity-less” k-set agreement tasks via our SOS approach. Intuitively, in validity-less k-set agreement, all nonempty output sets of size at most k can be produced, independently of the input values of the execution (i.e., the classical k-set agreement validity property does not hold). We then show that, for k ≥ 2, these tasks can be solved under any number of crashes, because their SOS graph is necessarily connected. ▶ Definition 5 (Validity-less k-set agreement). Given the universe of values V containing at least k + 1 values, an SOS task TO with SOS O is validity-less k-set agreement if and only if O = {o ⊆ V | 0 < |o| ≤ k}. For instance, given the universe of values V = {1, 2, 3}, the SOS of validity-less 2-set agreement is O = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}. The SOS graph associated with O is connected, so validity-less 2-set agreement can be solved with any number of crashes. More generally, ▶ Corollary 6 (Solvability of validity-less k-set agreement with k ≥ 2). If k ≥ 2, then validityless k-set agreement is solvable under any number of crashes t. Proof. Since k ≥ 2, the universe V has at least 3 values, and O contains every nonempty subset of V of size at most k. Hence, every output set o ∈ O is connected to (or is itself) a singleton {v} ∈ O (property 1), and any two singletons {v}, {v ′ } ∈ O are connected via the path {v} ⊂ {v, v ′ } ⊂ {v ′ }, since {v, v ′ } ∈ O whenever k ≥ 2 (property 2). Together, these imply that SOSGraph(O) is connected, so the result follows from Algorithm 1 via Theorem 4. ◀
4
The d-Disagreement Problem
In the previous section, we saw that all connected SOS tasks can be implemented using Algorithm 1. However, this algorithm makes a strong system assumption, namely, that there is at least one correct process for every possible output value. This raises a new question: Can we identify some subclasses of connected SOS tasks with better implementability conditions? We now turn to this question for a natural family of connected SOS tasks, called d-disagreement, and that requires every execution to produce exactly d ≥ 1 distinct output values. Formally, a d-disagreement SOS task TO has SOS O = {{v1 , ..., vd }}. As d-disagreement seeks to bound the minimum number of different decision values, it belongs to the symmetry breaking family of distributed problems (in contrast to agreement problems, which seek to bound the maximum number of different decision values). In the following, we first present in Section 4.1 an impossibility proof on the implementability of d-disagreement, namely, that it can be implemented under asynchrony only Pd if n ≥ i=1 t+1 . Notice that this bound approximates (up to the iterated rounding) to i the d-th harmonic number times t + 1. We then provide in Section t+1 4.2 an asynchronous implementation of d-disagreement that assumes n ≥ d t+1 + . 2 2
4.1
Impossibility of d-disagreement
▶ Theorem 7 (Necessity of d-disagreement). Under asynchrony, condition n ≥ is necessary for implementing the sets of output sets O = {{v1 , . . . , vd }}.
Pd
i=1
t+1 i
10
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
Proof. For simplicity of presentation, in this proof, we assume the existence of a global clock that is inaccessible to the processes. By contradiction, let us assume that there exists an algorithm A that implements the set of output sets {{v1 , . . . , vd }} under asynchrony and Pd n < i=1 t+1 . We present an execution E of A that violates this assumption. i The execution E of A (with t crashes) is illustrated in Figure 2, and corresponds to the concatenation of execution fragments described as follows. Let us consider the first fragment of E, denoted E 1 , which starts at time 0. Initially, we let the processes run A freely until the first process p11 is about to output some value v11 at a time τ11 . Process p11 is frozen at time τ11 , so no other process can observe v11 (for now). Then, we let the non-frozen processes run A freely until a second process p21 is about to output some value v12 at a time τ12 , which is also frozen at τ12 so no other process can observe v12 . We repeat this process until process pt+1 is 1 about to output value v1t+1 and is frozen at time τ1t+1 . This is the time execution fragment E 1 ends. (Remark that, if there are enough processes, such a process pt+1 must exist, since 1 otherwise at most t processes output values in the execution; then, crashing them instead of freezing them would create an execution that can not produce the output set {v1 , . . . , vd }.) Let w1 be the most frequent value in v11 , . .. , v1t+1 , and P1 be the subset of processes that output w1 in E 1 . Observe that |P1 | ≥ t+1 d . Let us denote c1 = |P1 |. Let us now consider the second fragment, E 2 , which starts at time τ1t+1 . Initially, in this fragment, all processes in P1 are thawed, so they can go ahead and output w1 . Then, we let the non-frozen processes run freely A as long as they only output value w1 . We stop when a process p12 is about to output some value v21 ̸= w1 at a time τ22 . Process p12 is then frozen at time τ21 , so no other process can observe v21 . We repeat this c1 times until there are (again) t + 1 frozen processes. At this time τ2c1 is when execution fragment E 2 ends. (By the same argument as before, this must always happen if there are enough processes.) Let w2 be the most frequent value to be output by the frozen processes and P2 be the subset of frozen processes output w2 . Since w1 is not output by any frozen process, we have that t+1that c2 = |P2 | ≥ d−1 . The third fragment E 3 is constructed similarly. It starts at time τ2c1 by thawing all processes in P2 . Then, we let non-frozen processes run A, while freezing the first c2 processes that are about to output values not in {w1 , w2 }. When this happens (at time τ3c2 ), fragment E 3 ends with t + 1 frozen processes. Let w3 be the most frequent value to be output by the frozen processes and P3 be the subset t+1 of frozen processes that output w3 . Since w3 ∈ / {w1 , w2 }, we have that c3 = |P3 | ≥ d−2 . i Each execution fragment E , for i = 4, ..., d − 1, is constructed inductively in a similar way. ci−2 It starts at time τi−1 by thawing all processes in Pi−1 , so they can output wi−1 . Then, we let non-frozen processes run A, while freezing the first ci−1 processes that are about to output c values not in {w1 , w2 , ..., wi−1 }. When this happens (at time τi i−1 ) fragment E i ends with t + 1 frozen processes. Let wi be the most frequent value to be output by the frozen processes and Pi be the subset of frozen / {w1 , w2 , ..., wi−1 }, we processes that output wi . Since wi ∈ t+1 have that ci = |Pi | ≥ d−i+1 . cd−2 The final execution fragment E d starts at time τd−1 by thawing all processes in Pd−1 , so P1
P2
≥ t+1 d
t+1 ≥ d−1
···
Pd−1
Pd
≥ t+1 2
≤t
Figure 2 Execution E, where all processes in the set Pd crash.
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
Algorithm 2 Asynchronous t+1 d-disagreement algorithm for every SOS task with O = {{v1 , ..., vd }}, + 2 . assuming n ≥ d t+1 2 1
initialization: P? of P s.t. partition P1 , ..., Pd ,t+1 create , ∀ i ∈ [1..d] : |P | = . |P? | = n − d t+1 i 2 2
code of every process pi ∈ Pi , i ∈ [1..d] is output vi ; 4 communicate output(vi ).
2
3
code of every process p? ∈ P? is wait until p? observed d − 1 distinct output(⋆); 7 Vobs ← {v | pi observed output(v)}; 8 output v ∈ {v1 , ..., vd } \ Vobs .
5
6
they can output wd−1 . Observe that all the remaining frozen processes are about to output the only value wd ∈ {v1 , . . . , vd } that is not in {w1 , . . . , wd−1 }. Then, we let non-frozen processes run A, while freezing the first cd−1 − 1 processes that are about to output value c wd . When this happens (at time τd d−1 ) fragment E d ends with a set Pd of cd = t frozen processes. At that time, we crash the t processes of Pd , so they never output value wd . This is the time execution E lends,msince all processes either have output a value or crashed, given Pd Pd that i=1 |Pi | = i=1 t+1 − 1 ≥ n. By construction, the set of values {v1 , . . . , vd } has i not been produced in execution E. Hence, we have a contradiction. ◀
4.2
Implementation of d-disagreement
In this section, we present Algorithm 2, an asynchronous implementation t+1 of the d-disagreement SOS task TO , where O = {{v1 , ..., vd }}, assuming n ≥ d t+1 + 2 . At the initialization 2 of the algorithm, the set of all processes P is partitioned into d+ 1 subsets, P1 , ..., Pd , P? , t+1 t+1 such that |P? | = n − d 2 , and for every ∈ [1..d], |Pi | = (line 1).3 We can 2 i t+1 t+1 easily see that the assumption n ≥ d 2 + 2 is sufficient to instantiate all sets of t+1 ≥ processes P1 , ..., Pd , P? . Remark that |P? | = n−d t+1 . Therefore, this construction 2 2 guarantees that, in any pair of subsets Pi , Pj of the partition, there is always at least one correct process.4 For every subset Pi , i ∈ [1..d], a process pi ∈ Pi outputs vi (line 3) and then communicates output(vi ) (line 4). Moreover, every process p? ∈ P? waits until it observes d − 1 distinct output(⋆) (line 6), and gathers the observed values in the set Vobs (line 7). Finally, p? outputs the only value that is not present in Vobs (line 8). ▶ Theorem 8 (Correctness of Algorithm 2). Algorithm 2 implements all d-disagreement SOS tasks TO with SOS t+1 O = {{v1 , ..., vd }} under asynchrony and up to t crash failures, assuming n ≥ d t+1 + . 2 2 Proof. We prove the safety and completeness of Algorithm 2 as follows. Safety Let us consider an arbitrary execution E, and let Π be the set of all subsets of processes of the partition P1 , ..., Pd , P? such that each P ∈ Π contains at least one correct process p ∈ P in execution E. By construction of line 1, it is impossible to crash all the
3
Note that any construction of P1 , ..., Pd , P? such that the union of two subsets is strictly greater than t also works. 4 Recall that, ∀ k ∈ N : k = k2 + k2 .
11
12
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
processes of two subsets of P1 , ..., Pd , P? , so we have d ≤ |Π| ≤ d + 1. We now consider the following two cases. / Π. In this case, we necessarily have Π = {P1 , ..., Pd }, thus there exists 1. Case (i): P? ∈ at least one correct process pi in every subset Pi , i ∈ [1..d] that outputs vi at line 3. Therefore, such an execution necessarily produces the output set {v1 , ..., vd }. 2. Case (ii): P? ∈ Π. In this case, there can be at most one subset of P1 , ..., Pd that does not belong to Π. Let Π′ = Π \ {P? } be the set of subsets of processes in P1 , ..., Pd that contain correct processes in execution E. We necessarily have |Π′ | ≥ d − 1. For every subset Pi ∈ Π′ , there is at least one correct processes pi ∈ Pi that outputs vi at line 3 and then communicates output(vi ) at line 4. By C-Local-Termination and C-Global-Termination, the correct processes p? ∈ P? eventually observe d − 1 distinct output(v) in line 6 (by case assumption, there is at least one correct process in P? ). By construction, the set Vobs of every correct process p? ∈ P? therefore contains d − 1 different values at line 7 (though the set Vobs may differ between correct processes of P? ). For every correct process p? ∈ P? , {v1 , ..., vd } \ Vobs contains exactly one value v ∈ {v1 , ..., vd }. Finally, every correct process p? ∈ P? outputs the only value v ∈ {v1 , ..., vd } \ Vobs (line 8) that has not been observed by p? . Hence, the execution produces the output set {v1 , ..., vd }. Completeness Since there is only one output set in O, and safety shows that any execution produces this unique output set, then completeness follows immediately. ◀
5
Related Work
Combinatorial topology for distributed computing As discussed earlier, combinatorial topology has found surprising applications in the study of distributed tasks, as exposed in the monograph by Herlihy, Kozlov, and Rajsbaum [12]. This approach finds its roots in STOC 1993, where three concurrent papers leveraged combinatorial or topological results [5, 19, 14] (journal versions: [6, 15, 20]), such as Sperner’s lemma or Brouwer’s fixed point theorem, to prove the impossibility of k-set agreement under asynchrony and k crashes [8]. Specifically, the last two papers [19, 14] (which won the 2004 Gödel prize) proved this impossibility in the wait-free case, while the first one [5] (which won the 2017 Dijkstra prize) introduces the BG simulation technique, extending the impossibility to the general case. Broadly speaking, BG simulation shows that adding more correct processes to a wait-free system does not increase its computability power, for a specific class of tasks called convergence tasks [6] (also called colorless tasks), which correspond to the tasks whose input and output domains are “closed under inclusion”. Decidability of distributed tasks We focus on the asynchronous crash-prone model, as most of the literature on distributed decidability studied this particular model (indeed, many of the hardest problems, such as consensus, become solvable with any number of Byzantine/crash faults under synchrony [17]). Moran and Wolfstahl generalized the famous impossibility of consensus [9] by proving that all tasks that have a connected input graph and disconnected output graph do not tolerate crashes [18] (informally, the input (resp. output) graph is constructed by linking the input (resp. output) vectors that differ by only one value). This result was later completed by Biran, Moran, and Zaks, who demonstrated the decidability of tasks in the 1-resilient message-passing model (later shown to be equivalent to 1-resilient shared memory [3]), notably by introducing a general algorithm solving all 1-resilient tasks in their classification [4]. In the same vein, Taubenfeld, Katz, and Moran showed the decidability of tasks in the presence of initial failures [22]. The first undecidability result of
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
distributed computing is due to Gafni and Koutsoupias, who, by drawing connections with the contractability problem in topology, showed that some 3-process tasks are undecidable in the shared-memory wait-free model (i.e., with 2 crashes), that is, it is impossible to say if these tasks are solvable or not [10]. This undecidability result has been extended to other communication models and arbitrary levels of resilience by Herlihy and Rajsbaum [13]. The known decidability results of distributed tasks in the asynchronous crash-prone model are summarized in Table 2. The SOS approach The present work is closest to that of Albouy et al. [2], who introduced the Set of Output Sets approach in the binary case (i.e., the output values are 0 or 1). However, they did not formally define the concept of SOS tasks. In contrast, our formalization of SOS tasks can capture both binary and multivalued output sets, and it allows us to transfer the tightness results of [2] to a precise class of tasks, noted “Binary SOS tasks” (∗) in Table 2.
6
Conclusions
In this paper, we introduce and study SOS tasks, a novel class of distributed tasks defined by the set of distinct output sets they can produce across their executions. By departing from the classical triplet-based formalization of tasks and from the constraints of simplicial complexes, we have developed a framework that accommodates multiple valid implementations and output domains that are not closed under inclusion. Our main result establishes that the entire class of SOS tasks is decidable under asynchrony and any number of crashes. The decision rule is remarkably simple: an SOS task is always solvable when no process may crash, and it is solvable under any positive number of crashes if and only if its SOS graph (whose vertices are the output sets and whose edges connect pairs related by inclusion) is connected. This clean dichotomy partitions SOS tasks into those that tolerate arbitrarily many crashes and those that tolerate none at all, with no intermediate regime. Our decidability result has yielded several noteworthy consequences. First, it reveals a sharp discontinuity in the landscape of k-set agreement: without validity, k-set agreement is solvable under any number of crashes for k ≥ 2, yet becomes impossible under even a single crash when k = 1 (consensus). This highlights that the classical impossibility of k-set agreement for k ≥ 2 fundamentally depends on the validity requirement, a dependency that does not exist for consensus, whose impossibility holds even in its validity-less form. Second, our study of d-disagreement, a symmetry-breaking task requiring the system to always produce exactly d distinct output values, has uncovered a surprising connection to the harmonic series: the number of processes necessary to solve d-disagreement under t crashes is approximately n ≥ Hd (t + 1), where Hd is the d-th harmonic number. Several directions for future work emerge naturally from this study. First, closing the Pd t+1 t+1 gap between the lower bound of i=1 ⌈ t+1 i ⌉ and the upper bound of d⌈ 2 ⌉ + ⌊ 2 ⌋ for ddisagreement remains an open problem, and an optimal algorithm would be of both theoretical and practical interest, particularly for fault-tolerant load balancing applications. Second, Family
Condition on crashes Decidable Reference t≥2 No [10, 13] t=1 Yes [4, 3, 18] Arbitrary tasks initial crashes Yes [22] Binary SOS tasks (∗) any t ≤ n Yes [2] SOS tasks any t ≤ n Yes This work Table 2 Decidability results on distributed tasks identified to date (under asynchrony and crashes).
13
14
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
the universal algorithm we have presented for connected SOS tasks (Algorithm 1) requires n ≥ (t + 1)|V | processes. It would be valuable to determine tight resilience bounds, that is, the exact relationship between n and t for which each connected SOS task becomes solvable. Third, and perhaps most ambitiously, our work suggests a broader program: extending the decidability analysis to richer classes of tasks, such as tasks defined by their set of output vectors (rather than output sets), or tasks that incorporate input-dependent specifications. By progressively mapping the boundary between decidable and undecidable families, we hope to contribute to an eventual comprehensive theory of distributed decidability, one that plays a role for distributed computing analogous to that of classical computability theory for sequential computing. References 1
2
3
4 5
6 7 8 9 10 11
12 13
14
Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Mathieu Gestin, Nicolas Nicolaou, and Junlang Wang. AMECOS: a modular event-based framework for concurrent object specification. In Proc. 28th Int’l Conference on Principles of Distributed Systems (OPODIS’24), volume 324 of LIPIcs, pages 4:1–4:29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou, and Junlang Wang. Tight conditions for binary-output tasks under crashes. In Proc. 29th Int’l Conference on Principles of Distributed Systems (OPODIS’25), volume 361 of LIPIcs, pages 5:1–5:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. Amotz Bar-Noy and Danny Dolev. Shared-memory vs. message-passing in an asynchronous distributed environment. In Proc. 8th Annual ACM Symposium on Principles of Distributed Computing (PODC’89), pages 307–318. ACM, 1989. Ofer Biran, Shlomo Moran, and Shmuel Zaks. A combinatorial characterization of the distributed 1-solvable tasks. J. Algorithms, 11(3):420–440, 1990. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proc. 25th Annual ACM Symposium on Theory of Computing (STOC’93), pages 91–100. ACM, 1993. Elizabeth Borowsky, Eli Gafni, Nancy A. Lynch, and Sergio Rajsbaum. The BG distributed simulation algorithm. Distributed Comput., 14(3):127–146, 2001. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. The renaming problem in shared memory systems: An introduction. Comput. Sci. Rev., 5(3):229–251, 2011. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Inf. Comput., 105(1):132–158, 1993. Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, 1985. Eli Gafni and Elias Koutsoupias. Three-processor tasks are undecidable. SIAM J. Comput., 28(3):970–983, 1999. Vassos Hadzilacos and Sam Toueg. Reliable broadcast and related problems. In Sape Mullender, editor, Distributed Systems, pages 97–145. Addison-Wesley, Reading, MA, 2nd edition, 1993. Chapter 5. Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013. Maurice Herlihy and Sergio Rajsbaum. The decidability of distributed decision tasks (extended abstract). In Proc. 29th Annual ACM Symposium on the Theory of Computing (STOC’97), pages 589–598. ACM, 1997. Maurice Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In Proc. 25th Annual ACM Symposium on Theory of Computing (STOC’93), pages 111–120. ACM, 1993.
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
15 16
17 18 19
20 21
22
Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858–923, 1999. Damien Imbs, Sergio Rajsbaum, and Michel Raynal. The universe of symmetry breaking tasks. In Proc. 18th Int’l Colloquium on Structural Information and Communication Complexity (SIROCCO’11), volume 6796 of Lecture Notes in Computer Science, pages 66–77. Springer, 2011. Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982. Shlomo Moran and Yaron Wolfstahl. Extended impossibility results for asynchronous complete networks. Inf. Process. Lett., 26(3):145–151, 1987. Michael E. Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: the topology of public knowledge. In Proc. 25th Annual ACM Symposium on Theory of Computing (STOC’93), pages 101–110. ACM, 1993. Michael E. Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput., 29(5):1449–1483, 2000. Eugene Styer and Gary L. Peterson. Tight bounds for shared memory symmetric mutual exclusion problems. In Proc. 8th Annual ACM Symposium on Principles of Distributed Computing (PODC’89), pages 177–191. ACM, 1989. Gadi Taubenfeld, Shmuel Katz, and Shlomo Moran. Initial failures in distributed computations. Int. J. Parallel Program., 18(4):255–276, 1989.
15
16
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
Appendix A
Correctness of Algorithm 1
In this section, we prove Theorem 4, stating the correctness of Algorithm 1. We first show some preliminary results. In the following, we denote by LeadersOutputSets the set containing all output sets o from the outputSet(o) communicated by the group of leader processes Pleader during an execution of Algorithm 3. ▶ Lemma 9. LeadersOutputSets is nonempty. Proof. As |Pleader | > t by construction, there is at least one non-faulty leader process pleader ∈ Pleader . Recall that SOSWalk O is necessarily of finite size. For some loop index i ∈ [1..|SOSWalk O |], pleader eventually enters the condition at line 5 for one of the following reasons: the communication was delayed due to asynchrony, and pleader did not observe all move(i + 1) by the end of the wait at line 6; some leader process p′leader ∈ Pleader did not communicate move(i + 1), either because p′leader crashed, or because oi was the last element of SOSWalk O at line 5. Hence, process pleader eventually communicates some outputSet(oi ) at line 8, and therefore LeadersOutputSets is nonempty. ◀ ▶ Lemma 10. For every output set oi ∈ SOSWalk O , there exists an execution of Algorithm 1 for which LeadersOutputSets = {oi }. Proof. As SOSWalk O is a sequence, every element oi ∈ SOSWalk O has a finite index i ∈ N∗ . There must exist a crash-free execution where, for every loop index j ∈ [1..i − 1], every leader process communicates move(j + 1) at line 5, observes all |Pleader | move(oj + 1) by the end of the wait at line 6, and therefore skips the condition at line 7. (If i = 1, then the loop is executed only once.) At the end of this procedure, loop index i is reached. There must exist a crash-free execution that reaches this stage, and all leader processes do not observe all |Pleader | move(i + 1) by the end of the wait at line 6 due to asynchrony (since any timing of observations consistent with the communication properties is admissible, see Section 2.1). Thus, all leader processes enter the condition at line 7, communicate outputSet(oi ) at line 8, and exit the loop at line 9. Hence, LeadersOutputSets = {oi }. ◀ ▶ Observation 11. By construction (lines 4 and 8), all elements of LeadersOutputSets are in SOSWalk O . ▶ Lemma 12. LeadersOutputSets is either of the form {oi } or of the form {oi , oi+1 }, where oi , oi+1 are two subsequent elements in SOSWalk O . Proof. Lemma 9 shows that LeadersOutputSets cannot be empty. Lemma 10 implies the existence of some executions where LeadersOutputSets is a singleton {oi } where oi ∈ SOSWalk O . Let us consider an execution where LeadersOutputSets is at least of size 2. By Observation 11, LeadersOutputSets contains elements of SOSWalk O , and therefore we can consider any two distinct output sets oi , oj ∈ LeadersOutputSets, where i and j are the indices of oi , oj in SOSWalk O such that i < j. By definition of LeadersOutputSets, there is one leader process pleader ∈ Pleader that communicated some outputSet(oi ) at line 8, during the loop iteration i, and then exited the loop at line 9. Therefore, pleader could not have communicated move(i + 2) during the loop iteration i + 1, and every leader process that reaches the loop iteration i + 1 thus enters the condition at line 7, communicates outputSet(oi+1 ) at line 8
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
and exits the loop at line 9. It follows that j = i + 1, and thus that LeadersOutputSets is of the form {oi , oi+1 }. ◀ ▶ Lemma 13. In an execution with a given set LeadersOutputSets, the set of output values S produced by the execution is o = LeadersOutputSets. S Proof. Let us consider an execution with set LeadersOutputSets, let o = LeadersOutputSets S be the set of all values appearing in LeadersOutputSets, and let V = O be the set of all values appearing in O. By definition, LeadersOutputSets is the set of all output sets o′ that have been communicated by leader processes in some outputSet(o′ ) at line 8. By C-Local-Termination and C-Global-Termination, all correct processes eventually observe all of these outputSet(o′ ). Since the union of all o′ ∈ LeadersOutputSets is o, and by Observation 11, we deduce that o ⊆ V . As |Pv | > t for every v ∈ V , there is at least one correct process pv ∈ Pv that outputs v at line 10 upon observing the first outputSet(o′ ) such that v ∈ o′ . Therefore, as a whole, the execution produces output set o. ◀ For completeness, we restate Theorem 4. Theorem 3.3 (Correctness of Algorithm 1). Algorithm 1 implements any given connected SOS task TO with SOS O under asynchrony and up to t crash failures, assuming S n ≥ (t + 1) · |VO |, where V = O is the set of all possible output value in O. Proof. We prove the safety and completeness of Algorithm 1 as follows. Safety Let us consider an arbitrary execution of Algorithm 1 with set LeadersOutputSets. By Lemma 12, there are only two cases: (i) LeadersOutputSets = {oi }, or (ii) LeadersOutputSets = {oi , oi+1 }, where oi , oi+1 are two subsequent elements in SOSWalk O . S Lemma 13 shows that the output set produced by the execution is o = LeadersOutputSets. S For case (i), the output set of the execution is o = {oi } = oi , which is a valid output set of O. For case (ii), as oi , oi+1 are subsequent elements in SOSWalk O , then they are linked by an edge in the SOS graph SOSGraph(O). By Definition 2, one of these two sets must include the other. Without loss of generality, let us assume that oi ⊂ oi+1 . Thus, the output set S of the execution is o = {oi , oi+1 } = oi+1 , which is also a valid output set of O. Therefore, any execution of Algorithm 1 produces a valid output set. Completeness By Lemma 10, for every output set o ∈ O, there exists an execution in which LeadersOutputSets = {oi }. By Lemma 13, the output set produced by this execution is oi . ◀
B
The Case of Non-Resilient SOS tasks
We provide in this section the remaining results of our decidability study of SOS tasks, namely, that all disconnected SOS tasks cannot be solved under asynchrony and crashes (Appendix B.1), that all SOS tasks can be solved asynchronously without crashes (Appendix B.2), and that n ≥ max{|o| : o ∈ O} and t = 0 are tight conditions to implement disconnected SOS tasks asynchronously (Appendix B.3).
B.1
Necessity: The unsolvability of disconnected SOS tasks under crashes
In this section, we present Theorem 24, which generalizes the famous impossibility of asynchronous resilient consensus (FLP theorem [9]) to a broader family of tasks with non-
17
18
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
connected SOS graphs. Results similar to Theorem 24 have already been shown [18, 4], however, they rely on model-specific arguments (esp. message passing) and on a reduction from the consensus problem. Therefore, the FLP theorem is not a consequence of these results, but a cause. In contrast, our proof of Theorem 24 is agnostic of the underlying communication medium, and the impossibility is proved from scratch, which allows us to state the FLP theorem as a corollary of our theorem (Corollary 26). Our proof generalizes the axiomatic approach of [1]: asynchrony, crash resilience, and termination are defined as axioms, and the impossibility of implementation is expressed as a contradiction within this system of axioms. We also generalize the classical notion of valence, introduced in [9]. However, unlike [1, 9], we extend the impossibility proof to any disconnected SOS task.
B.1.1
Preliminaries
We now introduce the necessary notions for our proof. Events An event eip is an action involving process p at index i (i.e., eip is the ith event of p). The only purpose of event indices is to differentiate events on the same process that could swap orders due to asynchrony. For instance, in asynchronous message passing, two messages could be sent by two different senders p′ , p′′ to the same recipient p, and due to asynchrony, there could be one execution where p first receives p′ and then p′′ , and another execution where p first receives p′′ and then p′ . However, thanks to indices, the reception by p of the message from p′ in these two executions is considered as two different events, since the indices of these events are different. Apart from this technical detail, the event indices are not used in the rest of the proof. Some special events, the input and output events, respectively, correspond to the input/output of a value v by a process p in the context of the task. These events are respectively noted invp and outvp . If the process p and/or index i of some event are not relevant, we can omit writing them. States A state σ is a set of events. An algorithm A is described by its set of states Σ and set of output states Ω ⊆ Σ, which are the final states where the algorithm can terminate. By definition, all maximal states of Σ are output states, i.e., {σ ∈ Σ | ∄ σ ′ ∈ Σ, σ ⊊ σ ′ } ⊆ Ω, but let us remark that there can also be output states that are subsets of the maximal states. Conversely, the input states are the states from which the algorithm begins and that have no previous state. They are given by: InStates(Σ) = {σ ∈ Σ | ∄ σ ′ ∈ Σ : σ ′ ⊊ σ}. ▶ Definition 14 (Input/output states of an implementation of task instance). If an algorithm with a set of states Σ and a set of output states Ω implements the task instance τ of some task T , then there must be input/output states corresponding to every pair of input/output vectors in τ : ∀ (Vin , Vout ) ∈ τ , ∃ σin ∈ InStates(Σ), ∃ σout ∈ Ω : σin ⊆ σout ∧ {invpj | v is the j th value in Vin , v ̸= ⊥} = σin ∧ {outvpj | v is the j th value in Vout , v ̸= ⊥} ⊆ σout . ▶ Definition 15 (SOS valence). Given a set of states Σ, a set of output states Ω, and a state
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
σ ∈ Σ, the SOS valence of σ is a set of sets of output values given by the function: ( {{v | outvp ∈ σ}} if σ ∈ Ω, Val(σ, Σ, Ω) = S ′ σ ′ ∈{σ ′ ∈Σ|σ⊊σ ′ } Val(σ ) otherwise. Informally, the SOS valence of an output state is the singleton containing the output set it produces, and the SOS valence of any other state is the union of the SOS valence of all its extensions. (Let us note that this definition of valence differs from that of [1, 9], since here SOS valence is the set of reachable sets of output values, and not the set of reachable output values, as executions producing multiple output values are allowed in our context.)
B.1.2
Axioms
Here, we define asynchrony, resilience, and termination as axioms that some algorithm must satisfy. In these definitions, and in the rest of the proof, we use the symbol ⊎ to denote the union of two disjoint sets. ▶ Definition 16 (Asynchrony axiom). Given a set of states Σ, asynchrony is defined as: Asynchrony(Σ) = ∀ σ ∈ Σ : (σ ⊎ {ep }, σ ⊎ {ep′ } ∈ Σ, p ̸= p′ ) =⇒ (σ ⊎ {ep , ep′ } ∈ Σ). Asynchrony (sometimes referred to as the diamond property) requires that if two states differ only in their last respective events, which are from different processes, their union is also a state, as the pace of processes can change across two executions. We point out that our impossibility proof is agnostic of the communication medium object, as long as the medium satisfies asynchrony as defined above (which is the case for the communicate/observe abstraction used in this paper).5 ▶ Definition 17 (Termination axiom). Given a set of states Σ, termination is defined as: Termination(Σ) = ∀ σ ∈ Σ : |σ| < +∞. Termination ensures that an algorithm does not have any state with an infinite number of events, and thus that the output states are reached in a finite number of steps. One could argue that it is allowed for an algorithm to keep making steps indefinitely after reaching an output state, but without loss of generality, we omit this scenario by removing the states extending an output state. ▶ Definition 18 (Resilience axiom). Given a set of states Σ and set of output states Ω ⊆ Σ, resilience is defined as: Resilience(Σ, Ω) = ∀ σ ∈ Σ \ Ω, ∃ σ ⊎ {ep }, σ ⊎ {ep′ } ∈ Σ : p ̸= p′ . Resilience imposes that at least two distinct processes can extend every state that is not an output state. If this is not the case, that is, if a state that is not an output state can only be extended by at most one process, then crashing this process would make the algorithm stop progressing, and thus never reach termination.
5
For a proof that some classical communication media (such as asynchronous message-passing and atomic memory) satisfy this definition of asynchrony, we refer the interested reader to [1].
19
20
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
B.1.3
Proof
Before proceeding to the impossibility theorem, we first establish some preliminary results. For notational simplicity, given a set of states Σ and a set of output states Ω, we say that a state σ ∈ Σ is disconnected if its SOS valence has an associated SOS graph SOSGraph(Val(σ, Σ, Ω)) that is disconnected, otherwise we say that state σ is connected. ▶ Observation 19. Given a set of states Σ and a set of output states Ω ⊆ Σ, by Definition 2, a disconnected σ cannot contain the empty set in its SOS valence Val(σ, Σ, Ω), because ∅ is included in any other set, which would make σ connected. ▶ Lemma 20. Let O be an SOS whose SOS graph SOSGraph(O) is disconnected, and let C1 , . . . , Ck (k ≥ 2) be its connected components (expressed as sets of vertices). If O′ ⊆ O and SOSGraph(O′ ) is connected, then O′ ⊆ Ci for some i ∈ [1..k]. Proof. By definition of connected components, there is no edge in SOSGraph(O) between any vertex in Ci and any vertex in Cj for i ̸= j. Since edges in SOSGraph(O′ ) are a subset of those in SOSGraph(O), if O′ contained vertices from two distinct components Ci and Cj , then SOSGraph(O′ ) would itself be disconnected. Contradiction. ◀ ▶ Lemma 21. Given a set of states Σ and a set of output states Ω ⊆ Σ, all states σ ∈ Σ have a nonempty SOS valence: Val(σ, Σ, Ω) ̸= ∅. Proof. Let us consider some state σ ∈ Σ. By definition, all maximal states of Σ (i.e., states that cannot be extended) are output states: {σ ′ ∈ Σ | ∄ σ ′′ ∈ Σ, σ ′ ⊊ σ ′′ } ⊆ Ω. By Definition 15, the SOS valence of an output state σ ′ (and in particular of a maximal state) is the singleton containing all output values of σ ′ , and it is therefore not empty. State σ is either an output state, or it is a subset of an output state: ∃ σ ′ ∈ Ω, σ ⊆ σ ′ . Again, by Definition 15, the SOS valence of σ must include the SOS valence of σ ′ : Val(σ ′ , Σ, Ω) ⊆ Val(σ, Σ, Ω). Therefore, the SOS valence of σ is not empty. ◀ Note that the previous lemma forbids the existence of an SOS valence of ∅, but it does not forbid the existence of an SOS valence of {∅} (i.e., the empty output set may be allowed). ▶ Lemma 22. Given a set of states Σ and a set of output states Ω ⊆ Σ, all disconnected states σ ∈ Σ are not output states, i.e., σ ∈ / Ω. Proof. Let us consider some disconnected state σ ∈ Σ with SOS valence O = Val(σ, Σ, Ω). That is, SOSGraph(O) is disconnected. By definition of SOSGraph() (Definition 2), there T must exist at least two output sets o, o′ ∈ O such that o ∩ o′ = ∅. Therefore, O = ∅. As there is no common value across all the output sets o ∈ O, then there cannot be any output event outvp in σ, and the set of output values of σ is the empty set ∅. But by Observation 19, as σ is disconnected, then O cannot contain the empty output set ∅, and thus ∅ is not a valid output set where the algorithm can terminate. Therefore, σ ∈ / Ω. ◀ ▶ Lemma 23. An algorithm A (with set of states Σ and set of output states Ω ⊆ Σ) that solves a disconnected SOS task TO must have a disconnected state: ∃ σ ∈ Σ : SOSGraph(Val(σ, Σ, Ω)) is a disconnected graph. Proof. By Definition 14, Σ must contain input/output states corresponding to every pair of input/output vectors in τ . By the fact that SOS tasks are validity-free (Definition 1), every input vector Vin of τ can yield all output vector Vout of τ . This implies that every input state can reach every output set o ∈ O, or more formally: ∀ σin ∈ InStates(Σ), ∀ o ∈
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
O, ∃ σout ∈ Ω, σin ⊆ σout : {v | invp ∈ σout } = o. By the definition of SOS valence (Definition 15), all input state therefore have the entire SOS O as their SOS valence, i.e., ∀ σin ∈ InStates : Val(σin , Σ, Ω) = O. By the fact that TO is a disconnected SOS task, SOSGraph(O) is a disconnected graph, and therefore any input state σin ∈ InStates is disconnected. ◀ ▶ Theorem 24 (Non-resilience of disconnected SOS tasks). A disconnected SOS task TO can be implemented asynchronously only if t = 0. Proof. By way of contradiction, let us assume that there is an algorithm A that implements any instance τ ∈ TO under asynchrony and t > 0, and where TO is a disconnected SOS task with SOS O. Let us consider the set of states Σ and the set of output states Ω ⊆ Σ of A. As communication is asynchronous, Asynchrony(Σ) is verified. Moreover, as t > 0, there can be at least one crash in the system, and Resilience(Σ, Ω) is verified. Finally, a task execution must terminate by definition, so Termination(Σ) is verified. By Lemma 23, disconnected states must exist. Let us consider any disconnected state σm ∈ Σ. We now inductively show that there exists what we call a critical state σc , i.e., a disconnected state that only has connected extensions: ∃ σc ∈ Σ : (SOSGraph(Val(σc , Σ, Ω)) is a disconnected graph) ∧ ( ∀ σ ′ ∈ Σ, σc ⊊ σ ′ : SOSGraph(Val(σ ′ , Σ, Ω)) is a connected graph). As σm has a disconnected SOS valence, Lemma 22 implies that is not an output state, i.e., σm ∈ / Ω. By Resilience(Σ, Ω), σm must have some extensions by one event. If all extensions have an connected SOS valence, then σm satisfies the property of a critical state and we set σc = σm . Otherwise, σm has some extension by one event σm ⊎ {e} ∈ Σ that has a disconnected SOS valence. Then, we make σm this new extension σm ⊎ {e} and repeat this procedure. Observe that this process must eventually end by finding a critical state, since otherwise, it means that an infinite state exists, which contradicts Termination(Σ). Let Oc = Val(σc , Σ, Ω). Since σc is disconnected, SOSGraph(Oc ) has at least two connected components (expressed as sets of vertices); fix two of them, C1 and C2 . We will now show that there exist two immediate 1-event extensions σ1 = σc ⊎ {ep } and σ2 = σc ⊎ {ep′ } in Σ such that Val(σ1 , Σ, Ω) ⊆ C1 and Val(σ2 , Σ, Ω) ⊆ C2 (and in particular Val(σ1 , Σ, Ω) ∩ Val(σ2 , Σ, Ω) = ∅). S S By Definition 15, Oc = σ′ ∈Σ, σc ⊊σ′ Val(σ ′ , Σ, Ω). In particular, Oc = σc ⊎{e}∈Σ Val(σc ⊎ {e}, Σ, Ω), since every extension of σc passes through some immediate 1-event extension. As Oc intersects both C1 and C2 , there exist immediate extensions σ1 , σ2 with Val(σ1 , Σ, Ω) ∩ C1 = ̸ ∅ and Val(σ2 , Σ, Ω) ∩ C2 ̸= ∅. By criticality of σc , both Val(σ1 , Σ, Ω) and Val(σ2 , Σ, Ω) have connected SOS graphs. Since Val(σ1 , Σ, Ω), Val(σ2 , Σ, Ω) ⊆ Oc , Lemma 20 implies that each is included in a single connected component of SOSGraph(Oc ). Hence Val(σ1 , Σ, Ω) ⊆ C1 and Val(σ2 , Σ, Ω) ⊆ C2 , so Val(σ1 , Σ, Ω) ∩ Val(σ2 , Σ, Ω) = ∅. We now derive a contradiction by considering two cases. Case 1: p ̸= p′ . Given that the processes of the two events are distinct, from Asynchrony(Σ), we have σ ′′ = σc ⊎ {ep , ep′ } ∈ Σ. Since σ ′′ extends both σ1 and σ2 , Definition 15 gives Val(σ ′′ , Σ, Ω) ⊆ Val(σ1 , Σ, Ω) ∩ Val(σ2 , Σ, Ω) = ∅. Thus Val(σ ′′ , Σ, Ω) = ∅, which contradicts Lemma 21. Case 2: p = p′ . By Resilience(Σ, Ω) (since σc ∈ / Ω by Lemma 22), there exists an immediate extension σ3 = σc ⊎ {ep′′ } ∈ Σ with p′′ ̸= p. By criticality of σc , Val(σ3 , Σ, Ω) has a connected SOS graph. Since Val(σ3 , Σ, Ω) ⊆ Oc , Lemma 20 implies Val(σ3 , Σ, Ω) ⊆ Cj for some j. Without loss of generality, suppose Val(σ3 , Σ, Ω) ∩ C1 = ∅ (if Val(σ3 , Σ, Ω) ⊆ C1 ,
21
22
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
use C2 and σ2 instead in the following). Then Val(σ3 , Σ, Ω) ∩ Val(σ1 , Σ, Ω) = ∅, since Val(σ1 , Σ, Ω) ⊆ C1 . As p′′ ̸= p, by Asynchrony(Σ), σc ⊎ {ep , ep′′ } ∈ Σ. Since this state extends both σ1 and σ3 , Definition 15 gives Val(σc ⊎ {ep , ep′′ }, Σ, Ω) ⊆ Val(σ1 , Σ, Ω) ∩ Val(σ3 , Σ, Ω) = ∅, contradicting Lemma 21. ◀
B.1.4
A special case: consensus
The impossibility of asynchronous resilient consensus follows directly from Theorem 24, as consensus has a disconnected SOS. More formally, validity-less consensus can be defined in our SOS approach as follows. ▶ Definition 25 (Validity-less consensus). Validity-less consensus is an SOS task TO with SOS O such that: 1. ∀ o ∈ O : |o| = 1, that is, every execution of consensus produces only one output value; 2. |O| ≥ 2, that is, consensus has at least two different executions that produce different output values. The first item of Definition 25 imposes that the system always agrees on one single output value, while the second item precludes trivial implementations that always output the same value across all executions. We can see that validity-less k-set agreement (Definition 5, page 9) boils down to validity-less consensus (Definition 25) when k = 1. ▶ Corollary 26 (Impossibility of asynchronous resilient consensus (FLP theorem [9])). Consensus is impossible under asynchrony and one crash. Proof. By Definition 25, validity-less consensus TO has an SOS O which contains at least two different singletons {v}, {v ′ } ∈ O. Neither of these two singletons can include the other, hence SOSGraph(O) is a disconnected graph. Therefore, Theorem 24 applies, which entails that validity-less consensus cannot be solved asynchronously with t > 0. It is easy to see that validity-less consensus (Definition 25) is an even weaker problem than validity-based consensus, which must also guarantee that every execution produces an output value taken from the input values. Therefore, the impossibility of validity-less consensus implies the impossibility of validity-based consensus. ◀
B.2
Sufficiency: A non-resilient algorithm for disconnected SOS tasks
In this section, we present Algorithm 3, a universal algorithm that implements any SOS task TO under asynchrony assuming n ≥ max{|o| : o ∈ O}, n ≥ 1, and t = 0 (no crash). The algorithm is instantiated by providing the SOS O as a parameter (line 1). At the initialization of the algorithm (line 2), a leader process pleader ∈ P is selected. We also let m be the size of the biggest output set in O, and create a partition of all processes P1 , ..., Pm containing m nonempty subsets (we can create this partition as we assume n ≥ max{|o| : o ∈ O} = m). To guarantee the existence of a leader, we assume that n ≥ 1. However, we show in Appendix B.2.2 that the case of n = 0 can be trivially addressed. First, for every output sets o ∈ O, the leader process pleader communicates choice(o) at line 4. Then, pleader waits for observing the first choice(o′ ) at line 5, and finally, pleader communicates outputSet(o′ ) at line 6. Besides, every process pi ∈ P (including pleader ) first waits for the outputSet(o) communicated by pleader (line 8). Then, pi computes its output value vi ∈ o based on its subset index i in the partition (1 ≤ i ≤ m): more precisely, pi sorts all values in o and takes the ((i mod |o|) + 1)-th one in this sequence (line 9). Finally, pi outputs vi (line 10).
Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang
B.2.1
Correctness of Algorithm 3
The correctness of Algorithm 3 is given in Theorem 28. We begin with an intermediary lemma. ▶ Lemma 27. If pleader communicates outputSet(o) at line 6, then the execution produces output set o. Proof. Let us assume that pleader communicates outputSet(o) at line 6. By C-LocalTermination, C-Global-Termination, and the fact that there are no crashes, all processes eventually observe outputSet(o) and pass the wait statement at line 8. By C-Validity and the fact that only pleader communicates information in the algorithm, outputSet(o) is the only information observed by the processes. We can first observe that the execution cannot produce output values that are not in o, by line 7. Since all subsets in the partition P1 , ..., Pm are nonempty and no process crashes, all processes p1 ∈ P1 pick the smallest value v1 ∈ o, all processes p2 ∈ P2 pick the second smallest value v2 , etc., and finally, all processes p|o| ∈ P|o| pick the biggest value v|o| ∈ o (recall that |o| ≤ m). After that, all processes pi ∈ Pi , i ∈ [1..|o|] output vi at line 7. Therefore, as a whole, all processes of P1 , ..., P|o| output all values in o, and the execution produces the output set o. ◀ ▶ Theorem 28. Algorithm 3 implements any SOS task TO with SOS O under asynchrony, assuming n ≥ max{|o| : o ∈ O}, n ≥ 1, and t = 0. Proof. The safety and completeness of Algorithm 3 are proved in the following. Safety Let o be an output set produced by an execution of Algorithm 3, we will now show that o ∈ O. Since there is no crash, pleader has observed at line 5 some choice(o′ ) that it has communicated before (by C-Validity) and therefore oj ∈ O (from line 4). After that, pleader communicated outputSet(o′ ) at line 6. By Lemma 27, the execution produces output set o′ , and o = o′ . As o′ ∈ O, then o ∈ O. Completeness For every o ∈ O, there must exist an execution where the first information observed by the leader process pleader is choice(o) due to asynchrony (since any timing of observations consistent with the communication properties is admissible, see Section 2.1). By Lemma 27, the execution must produce the output set o. ◀ Algorithm 3 Asynchronous algorithm implementing all possible SOS O assuming n ≥ max{|o| : o ∈ O}, n ≥ 1, and t = 0. instantiation parameter: SOS O. initialization: pick some leader process pleader ∈ P , let m = max{|o| : o ∈ O}, create a partition P1 , · · · , Pm of P s.t. ∀ i ∈ [1..m], |Pi | ≥ 1. 3 code of process pleader is 4 for all o ∈ O do communicate choice(o); 5 wait pleader observes first choice(o′ ); 6 communicate outputSet(o′ ).
1 2
code of every process pi ∈ Pi , i ∈ [1..m] is wait pi observes outputSet(o); 9 vi ← ((i mod |o|) + 1)-th largest value in o; 10 output vi . 7
8
23
24
Decidability of Distributed Tasks with Output Sets under Asynchrony and Crashes
B.2.2
The case of n = 0
If there is no process in the system (n = 0), then Algorithm 3 cannot work as it requires the existence of some leader pleader . However, with no process, the only SOS that can be produced is O = {∅}, and any execution of an algorithm with no process necessarily already produces the output set ∅. Therefore, such an algorithm is trivially safe and complete.
B.3
Tight conditions to implement disconnected SOS tasks
In this section, we combine the previous results to show that the two conditions n ≥ max{|o| : o ∈ O} and t = 0 are necessary and sufficient to implement any disconnected SOS task TO in asynchrony. In the following, we consider an arbitrary SOS task TO with a disconnected SOS O, i.e., SOSGraph(O) is a disconnected graph. Necessity of n ≥ max{|o| : o ∈ O} and t = 0 The necessity of t = 0 comes from Theorem 24. The necessity of n ≥ max{|o| : o ∈ O} comes from the fact that, if this condition is not satisfied, then there are not enough processes in the system to output all the values of the largest output set o ∈ O, violating completeness. Sufficiency of n ≥ max{|o| : o ∈ O} and t = 0 If SOSGraph(O) is a disconnected graph, then it necessarily contains several vertices, and SOS O cannot be {∅}. It implies that n ≥ 1. Finally, if we assume that conditions n ≥ max{|o| : o ∈ O} and t = 0 are satisfied, then we have all the sufficient conditions to use Algorithm 3 and implement the disconnected SOS task TO .