Wait-Free Universality of Consensus in the Infinite Arrival Model

Achour Most\'efaoui; Gr\'egoire Bonin; Matthieu Perrin

REVIEW 4 major objections 5 minor 16 references

Wait-Free Universality of Consensus in the Infinite Arrival Model

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Consensus is universal even in the infinite arrival model.

desk verdict Genuinely new passive-helping weak log, but Lemma 3's proof has an invalid reads-implies-writes step, so the paper's wait-freedom result is not established as written. read the letter →

arxiv 1908.02063 v1 pith:Q6U2LH6C submitted 2019-08-06 cs.DC

Grégoire Bonin , Achour Mostéfaoui , Matthieu Perrin This is my paper · ORCID

classification cs.DC

keywords consensusuniversalconstructioninfinitearrivalmodelwait-freelinearizabilityweaklogpassivehelpingcompare-and-swap

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether consensus keeps its universal power when the set of processes is not fixed but can grow without bound, with newcomers arriving at any time. It answers yes: every object that has a sequential specification admits a wait-free linearizable implementation using only consensus objects and read/write registers. This extends the classical universality theorem from a system with a fixed finite set of processes to one with anonymous, unbounded arrivals. The proof works through a new abstraction, the weak log, in which each arriving process announces its operation and is eventually noticed by all later processes.

What carries the argument

The load-bearing object is the weak log, a wait-free distributed list abstraction defined in the paper: each process appends a distinct value and receives a finite sequence of previously appended values, with a total order on shared values and eventual visibility of every terminated append. The mechanism that makes it work under infinite arrivals is passive helping. When a process wins the consensus on the log's end, it allocates a side list; processes that lose that same consensus insert their values into the side list rather than competing again on the main chain. Because only finitely many processes can have read the old end value when the winner installed its node, every contender eventually finds a finite place.

What would settle it

Run Algorithm 2 with a slow process that repeatedly reads `last`, loses every consensus it enters, and is forced to follow the side lists; if an adversarial schedule keeps that process looping forever while others terminate, the weak log is not wait-free and the universality proof fails. More simply, any execution in which infinitely many append operations read the same value of `last` and all terminate would directly contradict Lemma 3.

Watch

Extended reading notes

Core claim

The central claim is that consensus is universal in the infinite arrival model: for any object with a sequential specification, there is a wait-free and linearizable implementation built solely from consensus objects and atomic read/write registers. Previous universal constructions relied on a per-process announcement array, which cannot work when infinitely many anonymous processes may arrive. The paper replaces that array with a weak log, a list-like distributed task in which each process appends its invocation; the construction also supplies two implementations of the weak log, one from consensus objects and one from compare-and-swap. The ordering of operations is the order in which they appear in the linked list of consensus objects, and termination is guaranteed by passive helping, in which a process that wins a consensus creates a side list that hosts the values of concurrent losers.

Load-bearing premise

The construction stands or falls on the claim that the shared pointer to the end of the log moves forward permanently, so no single value of that pointer can be read by infinitely many processes.

Editorial extensions

If this is right

Any object with a sequential specification, such as a stack, queue, or register, has a wait-free linearizable implementation in the infinite arrival model from consensus plus read/write registers.
Processes need not know how many others will arrive, and they may be anonymous; the construction does not rely on a bound on participation.
The weak log can be realized both by consensus objects and by a compare-and-swap stack, so the universality result carries over to systems whose hardware provides CAS.
Each operation terminates in a finite number of its own steps regardless of how many processes join later.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The passive-helping pattern suggests that other constructions that use dedicated per-process memory could be ported to unbounded arrivals by replacing the array with a consensus-built append-only structure.
A natural next step, not taken in the paper, is garbage collection of the two lists; the weak log grows forever because its design keeps all past operations reachable.
If the weak log can be implemented by primitives weaker than consensus, the same universal construction would show those primitives are also universal in the infinite arrival model.
The CAS-based weak log is a stack rather than a queue, so it may offer different performance trade-offs in practice; a direct comparison of the two implementations is not part of this paper.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this paper has a genuinely new idea and a serious proof gap. It asks the right question—whether Herlihy's universality survives infinite arrivals—and the passive-helping construction is the right kind of tool for that model. But the proof as written does not establish wait-freedom.

What the paper does well: it defines a weak log abstraction that replaces per-process announce registers, and it gives two implementations, one from consensus and one from CAS. The passive-helping idea—letting the winner of a consensus host losers in a side list—is a real contribution, and the CAS variant suggests the mechanism is not tied to one primitive. The universal construction itself is a clean extension of Herlihy-Shavit and would be correct if the weak log actually satisfied its specification.

The problem is Lemma 3. The proof argues that since writing list.tail to last requires reading list at line 2, infinitely many writes of list.tail imply infinitely many writes of list. That inference is false. A process can read list at line 2, lose the consensus, and write the winner's tail instead—exactly what Figure 1 shows. So infinitely many reads of a stale last value can generate infinitely many writes of the same tail without ever writing the list itself. Since Lemma 7 and Lemma 8 both lean on Lemma 3, and Lemma 2 leans on them, the wait-freedom argument for Algorithm 1 does not go through. This is not a nitpick; it is the central forward-progress proof.

Two smaller issues. First, the weak log requires all proposed values to be distinct, but processes are anonymous, and the paper never explains how distinctness is obtained. Freshly allocated memory references could probably do it, but that step is missing. Second, Algorithm 2's line 3 looks off as printed: a successful proposer writes nodei.tail, which was proposed as ⊥, so last would be overwritten with null. I might be misreading the type notation, but it needs a clean explanation.

Bottom line: this is a paper for distributed-computing theorists. The high-level program is plausible and the passive-helping mechanism is worth knowing about, but this version should not be accepted. It deserves a serious referee, because the question is important and the construction may be repairable. If I were the editor, I would send it to a careful reader and ask them to focus on Lemma 3.

Referee Report

4 major / 5 minor

Summary. The paper studies the infinite arrival model, in which infinitely many anonymous processes may arrive, leave, or crash, and asks whether consensus remains universal for wait-free linearizable implementations of arbitrary sequential objects. It introduces a 'weak log' abstraction, proposes a universal construction (Algorithm 1) that reduces any sequential object to a weak log plus consensus objects, and supplies two implementations of the weak log: Algorithm 2 using consensus and read/write registers, and Algorithm 3 using compare&swap. The central claim is that every object with a sequential specification has a wait-free linearizable implementation from consensus and read/write registers in this model, based on the claimed properties of the weak log.

Significance. An affirmative answer would be a substantive extension of Herlihy's classic universality theorem, moving from a fixed set of processes to an unbounded, anonymous, crash-prone population. The high-level reduction in Algorithm 1 is elegant, and the 'passive helping' idea—letting the winner of a consensus create a side list for concurrent losers—is original and interesting. The paper is self-contained and makes its proof obligations explicit. However, the wait-freedom argument for the weak log implementation is not established as written, and the handling of distinct input values under anonymity needs explicit justification. If these gaps can be repaired, the result would be a valuable contribution.

major comments (4)

[Section 5, Lemma 3] The proof of Lemma 3 contains an unjustified inference. The contrapositive step argues: 'In order to write list.tail in last, a process needs to read list in last at line 2. As list.tail is written an infinite number of times and list is read an infinite number of times, then necessarily, list is written an infinite number of times as well.' This does not follow: a value can be read infinitely often after a single write, and a process that reads list at line 2 and loses the consensus writes a different tail, as Figure 1 itself illustrates for p6. The final paragraph of the proof repeats the same mistake, concluding from infinitely many reads of last returning list that list is written infinitely often in last. Lemma 3 is load-bearing: Lemma 7 (eventual visibility) and Lemma 8 (wait-freedom) of the weak log, and hence Lemma 2 for Algorithm 1, all rely on it. Since no alternative argument is supplied, the wait-freedom of the central construction is not established.
[Sections 2, 3, and 4 (Definition 3, Lemma 1)] The weak log specification assumes that all processes propose distinct values, and the proof of Lemma 1 uses 'as all invoc values are different.' In an anonymous system, two different processes may legitimately invoke the same operation on the implemented object, e.g., two increments of a counter; the values appended to the weak log would then be equal. The paper does not explain how Algorithm 1 or Algorithm 2 obtains distinct values in the absence of process identifiers. The authors should either specify an explicit tagging mechanism, such as attaching a freshly allocated memory reference to each invocation, or state precisely that the universality claim is restricted to pairwise distinguishable operation invocations.
[Section 4, Lemma 2] The proof of wait-freedom for Algorithm 1 is not fully justified even if the weak-log lemmas are granted. It applies eventual visibility to the value wi,k, but eventual visibility applies to values of processes that terminate their append invocation; here pi is still running, and wi,k may be the invocation of another process that has not terminated. The proof also asserts that the first case of the dichotomy covers only a finite number of winj terms without a detailed argument. These steps need a precise treatment before the central theorem can be considered proven.
[Section 6, Algorithm 3] The compare&swap-based weak log is presented as a contribution, but no proof is given for its wait-freedom, eventual visibility, or total order. If this section is intended as an illustration or remark, that should be stated; if it is claimed as a valid implementation, it needs lemmas analogous to Lemmas 3–8 for Algorithm 2. As written, the claim that Algorithm 3 implements a weak log is unsupported.

minor comments (5)

[Section 5, Lemma 3 base case] The sentence 'first is never proposed' is confusing because, when last.read() returns first, a process does invoke propose on first at line 2. Please clarify that this means first is never proposed as a value to another consensus object, not that no process ever calls propose on it.
[Section 5, Algorithm 2] The allocation of new consensus objects (the ⊥ tails) is implicit. Since the system model allows memory allocation to create a finite number of locations per invocation, the algorithms should state explicitly when new consensus objects are allocated and how references are propagated.
[Section 3, Definition 4] The recursive definition of precedence is difficult to parse. A more direct inductive definition, or a small example, would improve readability.
[Section 6] The progress argument for Algorithm 3 is compressed into a single sentence ('pi eventually succeeds because it only competes in this task with the finite set of processes that read last before pj won its compare&swap'). This needs expansion, especially because the infinite arrival model makes the finiteness of that set nontrivial.
[General] There are several typos and minor wording issues, including 'looses' for 'loses' and the ligature 'ﬁrst' throughout the text; a careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the universal construction and weak log implementations are self-contained reductions from consensus and read/write registers.

full rationale

The paper's derivation chain is self-contained and does not reduce to its own inputs. The central claim is that consensus is universal in the infinite arrival model. This is established by giving a universal construction (Algorithm 1) that assumes a weak log and consensus objects, and then separately implementing the weak log directly from consensus objects (Algorithm 2) or from compare-and-swap (Algorithm 3). There is no fitting of parameters, no quantity is defined in terms of the quantity it is supposed to predict, and no empirical benchmark is involved. The reliance on prior work is limited to standard background results such as Herlihy's universality theorem and classical definitions of linearizability and wait-freedom, which are used as definitions and baseline facts, not as circular support for the new claim. The proof of Lemma 3 contains an inference that the skeptic identifies as invalid, namely that infinitely many reads of a given last value imply infinitely many writes of that value to last; however, that is a potential correctness gap in the proof, not a circularity. A proof gap does not make the derivation circular unless the claimed conclusion is assumed or the reasoning reduces to the statement being proved. That is not the case here: Lemma 3 is intended to be proven from the algorithm's structure, and its alleged failure does not show that the theorem is equivalent to an input. Therefore, no circular step can be exhibited, and the paper merits a circularity score of 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

The paper's central claim rests on the weak log abstraction and on the assumption that distinct values can be proposed; the proof of the weak log's wait-freedom (Lemma 3) is under-specified. No free parameters are fit to data.

assumptions (3)

domain assumption The system model allows an infinite set of anonymous processes, infinite memory, and a memory allocation mechanism that creates new locations when invoked.
Section 2 defines the model; the universal construction relies on these primitives and on the ability to create new memory locations to store nodes.
domain assumption Values appended to the weak log are distinct.
Definition 3 states this requirement; the proof of Lemma 1 uses it explicitly, but no mechanism for anonymous processes to generate distinct values is provided.
domain assumption Consensus objects behave as sticky bits, returning the first proposed value to all subsequent readers.
Section 2 defines consensus objects this way and notes in a footnote that this can be implemented from a standard consensus task and one read/write register.

invented entities (1)

Weak log abstraction independent evidence
purpose: A shared log in which every process can announce its own proposed value, satisfying validity, suffixing, total order, eventual visibility, and wait-freedom; used as the announcement mechanism in the universal construction.
The paper provides two concrete implementations (from consensus and from CAS), so the abstraction has operational content and is not just a black box.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Wait-Free Universality of Consensus in the Infinite Arrival Model." pith.science (2026). https://pith.science/paper/Q6U2LH6C

@misc{pith2026190802063,
  author       = {Pith},
  title        = {Pith review of: Wait-Free Universality of Consensus in the Infinite Arrival Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q6U2LH6C}},
  note         = {Machine review of arXiv:1908.02063}
}

read the original abstract

In classical asynchronous distributed systems composed of a fixed number n of processes where some proportion may fail by crashing, many objects do not have a wait-free linearizable implementation (e.g. stacks, queues, etc.). It has been proved that consensus is universal in such systems, which means that this system augmented with consensus objects allows to implement any object that has a sequential specification. To this end, many universal constructions have been proposed in systems augmented with consensus objects or with different equivalent objects or special hardware instructions (compare&swap, fetch&add, etc.). In this paper, we consider a more general system model called infinite arrival model where infinitely many processes may arrive and leave or crash during a run. We prove that consensus is still universal in this more general model. For that, we propose a universal construction. As a first step we build a weak log for which we propose two implementations using consensus objects for the first and the compare&swap special instruction for the other.

Figures

Figures reproduced from arXiv: 1908.02063 by the authors.

**Figure 1.** In this example, p5 inserting v5 and p6 inserting v6 both read the same value hhv4, ⊥i, ⊥i of last. Process p5 wins the consensus and inserts v5 after v4, and p6 looses the consensus, so, it inserts v6 in the side list created by p5. This is a contradiction meaning the assumption of a non-wait-free execution is absurd. 5 From Consensus to the Weak Log The main difficulty in the implementation of a weak log lies in t… view at source ↗

**Figure 2.** In this example, p4 inserting v4 and p5 inserting v5 both read the same value v3 of last. Process p4 wins its compare&swap and inserts v4 before v3, and p5 looses the compare&swap to p4 and inserts v5 after v4. Processes share a unique CAS register last, that stores either the initial value, empty, or nodes of the form hhead,taili, where head is a value appended by a process and tail has the same type as last. When … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

From bounded t o unbounded concurrency ob- jects and back

Yehuda Afek, Adam Morrison, and Guy Wertheim. From bounded t o unbounded concurrency ob- jects and back. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , pages 119–128. ACM, 2011. 2

work page 2011
[2]

Wait-free consens us with inﬁnite arrivals

James Aspnes, Gauri Shah, and Jatin Shah. Wait-free consens us with inﬁnite arrivals. In Proceedings of the thiry-fourth annual ACM symposium on Theory of comput ing, pages 524–533. ACM, 2002. 2

work page 2002
[3]

Lon g-Lived Tasks

Armando Casta˜ neda, Michel Raynal, and Sergio Rajsbaum. Lon g-Lived Tasks. In NETYS 2017 - 5th International Conference on NETworked sYStems , volume 10299, pages 439–454, Mar- rakech, Morocco, May 2017. Springer. URL: https://hal.archives-ouvertes.fr/hal-01660646 , doi:10.1007/978-3-319-59647-1\_32 . 4

work page doi:10.1007/978-3-319-59647-1 2017
[4]

Help! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing , pages 241–250

Keren Censor-Hillel, Erez Petrank, and Shahar Timnat. Help! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing , pages 241–250. ACM, 2015. 2

work page 2015
[5]

Active disk paxos with inﬁnitely m any processes

Gregory Chockler and Dahlia Malkhi. Active disk paxos with inﬁnitely m any processes. Distributed Computing, 18(1):73–84, 2005. 2

work page 2005
[6]

Kallimanis

Panagiota Fatourou and Nikolaos D. Kallimanis. Highly-eﬃcient wait- free synchronization. Theory Comput. Syst. , 55(3):475–520, 2014. 3

work page 2014
[7]

Fischer, Nancy A

Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Imposs ibility of distributed consensus with one faulty process. J. ACM , 32(2):374–382, 1985. 1

work page 1985
[8]

Impossibility and universality results for wait-fre e synchronization

Maurice Herlihy. Impossibility and universality results for wait-fre e synchronization. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distrib uted Computing, Toronto, Ontario, Canada, August 15-17, 1988 , pages 276–290, 1988. 2

work page 1988

Show all 16 references

[9]

Wait-free synchronization

Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS) , 13(1):124–149, 1991. 2

1991
[10]

Power and limits of distributed computing shared memory models

Maurice Herlihy, Sergio Rajsbaum, and Michel Raynal. Power and limits of distributed computing shared memory models. Theor. Comput. Sci. , 509:3–24, 2013. 1

2013
[11]

The art of multiprocessor programming

Maurice Herlihy and Nir Shavit. The art of multiprocessor programming . Morgan Kaufmann, 2008. 1, 4, 5

2008
[12]

Maurice Herlihy and Jeannette M. Wing. Linearizability: A correct ness condition for concurrent objects. ACM Trans. Program. Lang. Syst. , 12(3):463–492, 1990. 1, 2

1990
[13]

Resilient consensus for in ﬁnitely many processes

Michael Merritt and Gadi Taubenfeld. Resilient consensus for in ﬁnitely many processes. In Inter- national Symposium on Distributed Computing , pages 1–15. Springer, 2003. 2

2003
[14]

Concurrent Programming - Algorithms, Principles, and Foun dations

Michel Raynal. Concurrent Programming - Algorithms, Principles, and Foun dations. Springer,
[15]

Distributed universal constructions: a guided t our

Michel Raynal. Distributed universal constructions: a guided t our. Bulletin of the EATCS , 121,
[16]

Distributed Computing Pearls

Gadi Taubenfeld. Distributed Computing Pearls . Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2018. doi:10.2200/S00845ED1V01Y201804DCT014. 1 10

2018 doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

From bounded t o unbounded concurrency ob- jects and back

Yehuda Afek, Adam Morrison, and Guy Wertheim. From bounded t o unbounded concurrency ob- jects and back. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , pages 119–128. ACM, 2011. 2

work page 2011

[2] [2]

Wait-free consens us with inﬁnite arrivals

James Aspnes, Gauri Shah, and Jatin Shah. Wait-free consens us with inﬁnite arrivals. In Proceedings of the thiry-fourth annual ACM symposium on Theory of comput ing, pages 524–533. ACM, 2002. 2

work page 2002

[3] [3]

Lon g-Lived Tasks

Armando Casta˜ neda, Michel Raynal, and Sergio Rajsbaum. Lon g-Lived Tasks. In NETYS 2017 - 5th International Conference on NETworked sYStems , volume 10299, pages 439–454, Mar- rakech, Morocco, May 2017. Springer. URL: https://hal.archives-ouvertes.fr/hal-01660646 , doi:10.1007/978-3-319-59647-1\_32 . 4

work page doi:10.1007/978-3-319-59647-1 2017

[4] [4]

Help! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing , pages 241–250

Keren Censor-Hillel, Erez Petrank, and Shahar Timnat. Help! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing , pages 241–250. ACM, 2015. 2

work page 2015

[5] [5]

Active disk paxos with inﬁnitely m any processes

Gregory Chockler and Dahlia Malkhi. Active disk paxos with inﬁnitely m any processes. Distributed Computing, 18(1):73–84, 2005. 2

work page 2005

[6] [6]

Kallimanis

Panagiota Fatourou and Nikolaos D. Kallimanis. Highly-eﬃcient wait- free synchronization. Theory Comput. Syst. , 55(3):475–520, 2014. 3

work page 2014

[7] [7]

Fischer, Nancy A

Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Imposs ibility of distributed consensus with one faulty process. J. ACM , 32(2):374–382, 1985. 1

work page 1985

[8] [8]

Impossibility and universality results for wait-fre e synchronization

Maurice Herlihy. Impossibility and universality results for wait-fre e synchronization. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distrib uted Computing, Toronto, Ontario, Canada, August 15-17, 1988 , pages 276–290, 1988. 2

work page 1988