pith. sign in

arxiv: 2604.06920 · v1 · submitted 2026-04-08 · 💻 cs.DC

On the Decidability of Distributed Tasks with Output Sets under Asynchrony and Any Number of Crashes

Timoth\'e Albouy , Antonio Fern\'andez Anta , Chryssis Georgiou , Nicolas Nicolaou , Junlang Wang This is my paper

Pith reviewed 2026-05-10 17:59 UTC · model grok-4.3

classification 💻 cs.DC
keywords SOS tasksdistributed task decidabilityasynchronous crash failuresset agreementoutput setsgraph connectivityd-disagreement
0
0 comments X

The pith

SOS tasks are solvable under any crashes exactly when the graph of their output sets under inclusion is connected.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines SOS tasks by the finite collection O of output sets they are allowed to produce. It proves that solvability in asynchronous message-passing systems with crash failures is completely decidable: every such task is solvable when there are no crashes, and solvable with crashes if and only if the undirected graph with vertices O and edges between any two sets where one contains the other is connected. The same criterion yields immediate corollaries for well-known tasks when no validity condition is required. The authors further relate the implementability of the new d-disagreement family to the harmonic series.

Core claim

An SOS task is given by a set O of distinct output sets. In the standard asynchronous model with up to t crashes, every SOS task is solvable for t = 0. For t > 0 it is solvable if and only if the graph G = (O, ⊂) is connected, where two vertices are adjacent precisely when one output set is included in the other.

What carries the argument

The SOS graph whose vertices are the members of O and whose edges link any two output sets related by inclusion; connectivity of this graph is necessary and sufficient for solvability under crashes.

If this is right

  • k-set agreement is solvable under any number of crashes whenever k > 1 and no validity requirement is imposed.
  • Consensus (k = 1) remains unsolvable under even a single crash.
  • The d-disagreement task, which must always produce at least d distinct values, has an implementability condition governed by the harmonic series.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Removing validity turns many classic agreement problems into trivial tasks once more than one output is permitted.
  • The same connectivity test may classify additional families of tasks once they are expressed purely in terms of allowed output sets.
  • Constructing explicit disconnected examples and attempting to solve them would provide a direct experimental check of the necessity direction.

Load-bearing premise

Task solvability is defined with no validity condition that would restrict which output set from O may appear in a given execution.

What would settle it

An explicit algorithm that solves some SOS task whose inclusion graph is disconnected under one crash, or a formal argument showing that some connected-graph SOS task cannot be solved under crashes, would refute the claimed if-and-only-if criterion.

read the original 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,\subset)$ 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 \geq 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper introduces SOS tasks, specified solely by a finite set O of permissible output sets (with no validity or input-output relation required). It proves that, in the asynchronous message-passing model with crash failures, every SOS task is solvable when t=0; when t>0, solvability holds if and only if the SOS graph G=(O,⊂) is connected, where edges exist between output sets related by inclusion. The criterion is applied to show that k-set agreement (without validity) is solvable for every k>1 and any t, while remaining unsolvable for k=1 when t>0; a new d-disagreement family is also analyzed, with its solvability threshold linked to the harmonic series.

Significance. If the characterization holds, the result supplies a simple, effective, graph-theoretic decision procedure for a broad class of tasks whose only constraint is the allowed output sets. This is a clear contribution to distributed computability. The separation between consensus and higher k-set agreement in the absence of validity, together with the harmonic-series connection for d-disagreement, are noteworthy corollaries. The paper ships a parameter-free criterion and an explicit graph construction, both of which strengthen its technical value.

major comments (2)
  1. [§4, Theorem 1] §4, Theorem 1 (necessity direction): the argument that a disconnected component implies impossibility proceeds by partitioning processes into two groups that cannot reach each other’s output sets; the reduction is only sketched for t=1 and does not explicitly handle the case t>1 when the partition must survive additional crashes while still forcing the output sets to remain in separate components.
  2. [§5.2] §5.2 (k-set agreement application): the claim that the corresponding SOS graph is connected for k>1 is stated without exhibiting the precise collection O of output sets used for k-set agreement; it is therefore unclear whether the connectivity property follows directly from the standard definition or requires an auxiliary construction that might re-introduce a validity-like constraint.
minor comments (3)
  1. [Notation] The symbol ⊂ is used both for proper and non-proper inclusion in different paragraphs; a single consistent definition (or explicit statement that equality is allowed) would remove ambiguity.
  2. [§6] The d-disagreement construction in §6 invokes the partial sums of the harmonic series without stating the precise threshold function; adding the closed-form expression or a short lemma would improve readability.
  3. [Figure 2] Figure 2 (SOS graph examples) lacks a caption explaining the vertex labels and the meaning of the dashed versus solid edges.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: [§4, Theorem 1] §4, Theorem 1 (necessity direction): the argument that a disconnected component implies impossibility proceeds by partitioning processes into two groups that cannot reach each other’s output sets; the reduction is only sketched for t=1 and does not explicitly handle the case t>1 when the partition must survive additional crashes while still forcing the output sets to remain in separate components.

    Authors: We agree that the necessity direction requires a more explicit treatment for general t. The core partitioning argument—assigning processes to disconnected components of the SOS graph so that each group is confined to outputs from one component—extends naturally, but we will expand the proof in the revision to handle arbitrary t. Specifically, we will show that for any t > 0, one can partition the n processes into two sufficiently large groups (each of size at least t+1) such that the adversary can crash up to t processes while ensuring that the surviving processes in each group have no path connecting their permissible output sets. This forces the global output set to lie entirely within one component, contradicting connectivity. The revised proof will include the necessary execution constructions and induction on the number of crashes. revision: yes

  2. Referee: [§5.2] §5.2 (k-set agreement application): the claim that the corresponding SOS graph is connected for k>1 is stated without exhibiting the precise collection O of output sets used for k-set agreement; it is therefore unclear whether the connectivity property follows directly from the standard definition or requires an auxiliary construction that might re-introduce a validity-like constraint.

    Authors: We thank the referee for this clarification request. For k-set agreement without validity, the set O is defined directly as the collection of all subsets of the value domain V with cardinality at most k (taking V infinite or |V| > k to avoid boundary effects). This matches the standard definition stripped of validity: any output set of size ≤ k is permissible, with no requirement that outputs relate to inputs. We will state this O explicitly in §5.2 of the revision. Connectivity for k > 1 follows because the inclusion poset on subsets of size ≤ k is connected in the undirected sense: any two sets A, B (|A| ≤ k, |B| ≤ k) are joined by a path. When A and B are incomparable, a path can be constructed by ascending to a common superset of size at most k (when possible) or descending to singletons and ascending through an intermediate 2-element set; since k > 1 permits such 2-element bridges, a finite path always exists. For k = 1 the graph reduces to isolated singletons and is disconnected. No validity constraint is re-introduced, as membership in O depends solely on cardinality. revision: yes

Circularity Check

0 steps flagged

No significant circularity; decidability criterion derived from model assumptions

full rationale

The paper introduces SOS tasks via the set O of output sets and proves decidability by showing solvability iff the graph G=(O,⊂) is connected (for t>0). This is a direct theorem under the stated asynchronous crash model with no validity requirement. No equations reduce to inputs by construction, no parameters are fitted and renamed as predictions, and no load-bearing self-citations or uniqueness theorems from prior author work are invoked. The connectivity condition is an independent graph-theoretic property of the task definition, not smuggled via ansatz or renaming. The derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The result rests on the standard asynchronous crash model and the definition of task solvability without validity. No numerical parameters are fitted.

axioms (2)
  • domain assumption Standard asynchronous message-passing model with crash failures (no Byzantine faults, no timing assumptions).
    Invoked implicitly when stating solvability under t crashes.
  • domain assumption Task solvability is defined without a validity condition on outputs.
    Explicitly used in the k-set agreement implication.
invented entities (2)
  • SOS task no independent evidence
    purpose: Class of tasks specified solely by the set of allowed output sets.
    New definition introduced to obtain the decidability result.
  • SOS graph G=(O, ⊂) no independent evidence
    purpose: Graph whose connectivity decides solvability for t>0.
    Constructed directly from the output sets O.

pith-pipeline@v0.9.0 · 5557 in / 1356 out tokens · 25665 ms · 2026-05-10T17:59:28.730520+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

  1. [1]

    AMECOS: a modular event-based framework for concurrent object specification

    1 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. InProc. 28th Int’l Conference on Principles of Distributed Systems (OPODIS’24), volume 324 ofLIPIcs, pages 4:1–4:29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,...

    work page 2024

  2. [2]

    The topological structure of asynchronous computability.J

    Albouy, Fernández Anta, Georgiou, Nicolaou, and Wang 15 15 Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability.J. ACM, 46(6):858–923, 1999. 16 Damien Imbs, Sergio Rajsbaum, and Michel Raynal. The universe of symmetry breaking tasks. InProc. 18th Int’l Colloquium on Structural Information and Communication Complexity (SI...

    work page 1999