{"id":"c4bce564-a364-40b2-b26b-0556a9f8ef55","arxiv_id":"1908.02063","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Consensus remains universal in the infinite arrival model, where infinitely many anonymous processes may join and crash, via a new passive-helping weak log construction.","lead":"The paper shows that consensus, a basic agreement primitive, can still be used to build any shared object in an asynchronous system where an unbounded number of processes may arrive and crash. It gives a wait-free, linearizable construction using a new weak log building block, extending a classic 1988 result to a more realistic open system.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's proof of the weak log's forward progress relies on an invalid reads-implies-writes inference; since Lemma 7 and Lemma 8 depend on it, wait-freedom of the universal construction is not established.","rationale":"The reader's weakest-assumption analysis identifies the same load-bearing concern: the proof of Lemma 3 contains an unjustified inference, and the weak log's correctness depends on that lemma. My reading agrees, and I do not find a separate concern that changes the verdict. The paper's central theorem is plausible and the construction is novel, but as written the proof of wait-freedom relies on an unsupported step. The reader's CONDITIONAL verdict is therefore appropriate: the paper should be accepted only if the lemma can be given a correct proof, or a counterexample is found. The secondary issue about distinct invocation values and anonymity is real but more easily repaired; it does not alter the verdict.","tokens_in":9694,"tokens_out":23887,"duration_ms":272277,"concrete_test":"Independently re-derive Lemma 3 from Algorithm 2 with a well-founded argument that does not conflate reads and writes. In particular, define for each list value r the first time any process writes r.tail to last, and prove that every line-2 read of r occurs before that first write plus finitely many stale regressions. Then check whether the required bound on the number of processes reading the same last value can be established without the invalid 'reads implies writes' step. If this re-proof cannot be completed, Lemma 3 is unsupported and the wait-freedom of the weak log and of the universal construction remains unproven. A TLA+ or proof-assistant formalization of Algorithm 2 would make this check mechanized.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on the weak log implementation in Section 5, and specifically on Lemma 3, which is used to prove Eventual Visibility (Lemma 7) and Wait-freedom (Lemma 8) of the weak log. Those properties are then used in Lemma 2 to prove wait-freedom of the universal construction. The proof of Lemma 3 contains the following inference: '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 is invalid. A process that reads list at line 2 may lose the consensus at that list and thereby write a different tail (the winner's side list), or it may be delayed or crash before line 3. The paper's own Figure 1 illustrates exactly this phenomenon: p6 reads the same last value as p5, loses the consensus, and inserts its value into p5's side list, writing a value different from list.tail. Thus infinitely many reads of a given last value need not produce infinitely many writes of that same value to last. Since Lemma 3 is the load-bearing bound on how many processes can read a stale 'last' value, and no alternative argument is supplied, the proofs of Lemmas 7 and 8, and consequently Lemma 2 for Algorithm 1, do not go through as written. No machine-checked proof or independent verification is provided.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9953,"tokens_out":14942,"duration_ms":187472,"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":[{"comment":"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.","section":"Section 5, Lemma 3"},{"comment":"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":"Sections 2, 3, and 4 (Definition 3, Lemma 1)"},{"comment":"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":"Section 4, Lemma 2"},{"comment":"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.","section":"Section 6, Algorithm 3"}],"minor_comments":[{"comment":"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":"Section 5, Lemma 3 base case"},{"comment":"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":"Section 5, Algorithm 2"},{"comment":"The recursive definition of precedence is difficult to parse. A more direct inductive definition, or a small example, would improve readability.","section":"Section 3, Definition 4"},{"comment":"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.","section":"Section 6"},{"comment":"There are several typos and minor wording issues, including 'looses' for 'loses' and the ligature 'first' throughout the text; a careful proofreading pass is needed.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a real and interesting question and the high-level design is plausible, but the proof of Lemma 3 is not merely missing a detail: it contains a logical non sequitur that is central to the wait-freedom argument. The distinctness-of-invocations issue under anonymity also needs to be resolved. I do not recommend rejection, because both problems appear fixable within the scope of the paper, but this is not a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nTwo 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.\n\nBottom 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.","headline":"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.","tokens_in":10477,"tokens_out":8638,"would_cite":false,"duration_ms":82180,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Consensus is universal even in the infinite arrival model.","keywords":["consensus","universal construction","infinite arrival model","wait-free","linearizability","weak log","passive helping","compare-and-swap"],"falsifier":"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.","tokens_in":9478,"feed_emoji":"📋","tokens_out":5726,"duration_ms":56360,"temperature":0.7,"pith_summary":"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.","feed_headline":"Consensus stays universal with infinitely many arrivals","feed_subtitle":"A new weak log lets every arriving process register its operation, keeping wait-free implementations alive.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the classical universality theorem for a fixed set of processes, the result this paper extends.","marker":"[8]"},{"why":"It gives the standard universal construction whose per-process announcement array is replaced here by the weak log.","marker":"[11]"},{"why":"It defines linearizability, the consistency condition the construction must satisfy.","marker":"[12]"},{"why":"It introduces the infinite arrival model, the setting of the paper.","marker":"[13]"},{"why":"It establishes the impossibility of consensus with one crash, motivating consensus as the coordination primitive.","marker":"[7]"},{"why":"It uses a Collect object as a building block for a universal construction, the pattern followed by the weak log.","marker":"[6]"}],"fun_headline_variants":["Infinite arrivals? Consensus still universal","Consensus universality survives infinite arrivals","Wait-free universality with unbounded processes","Consensus suffices for any object, even with infinite arrivals","Infinitely many processes? Consensus still universal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Infinite arrivals? Consensus still universal","Consensus universality survives infinite arrivals","Wait-free universality with unbounded processes","Consensus suffices for any object, even with infinite arrivals","Infinitely many processes? Consensus still universal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000608,"raw_usage":{"total_tokens":2788,"prompt_tokens":854,"completion_tokens":1934,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":470,"completion_tokens_details":{"reasoning_tokens":1866}},"tokens_in":470,"tokens_out":1934,"duration_ms":15570,"temperature":1.0,"reasoning_tokens":1866,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:54:56.341800+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Impossibility and universality results for wait-fre e synchronization","cited_arxiv_id":null,"evidence_quote":"It supplies the classical universality theorem for a fixed set of processes, the result this paper extends."},{"cited_title":"The art of multiprocessor programming","cited_arxiv_id":null,"evidence_quote":"It gives the standard universal construction whose per-process announcement array is replaced here by the weak log."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines linearizability, the consistency condition the construction must satisfy."},{"cited_title":"Resilient consensus for in finitely many processes","cited_arxiv_id":null,"evidence_quote":"It introduces the infinite arrival model, the setting of the paper."},{"cited_title":"Fischer, Nancy A","cited_arxiv_id":null,"evidence_quote":"It establishes the impossibility of consensus with one crash, motivating consensus as the coordination primitive."},{"cited_title":"Kallimanis","cited_arxiv_id":null,"evidence_quote":"It uses a Collect object as a building block for a universal construction, the pattern followed by the weak log."}],"review_version":1}