{"id":"71e5625b-6484-4f1c-94d4-69d3dae5e06b","arxiv_id":"2501.18447","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A ticket-based semaphore augmented with a waiting array, TWA-Semaphore, preserves FIFO admission while improving throughput over plain ticket semaphores in a microbenchmark.","lead":"The paper adapts a ticket-lock design to create a semaphore, then layers on a 'waiting array' to reduce spinning, aiming for a scalable, compact, and fair semaphore. It measures the new design against a simple ticket semaphore and the pthread semaphore on a 72-thread Intel Xeon.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"TWA-Semaphore deadlocks when LongTermThreshold is set to 0, a configuration the paper explicitly recommends to eliminate spinning; the wake-up scheme pokes the bucket indexed by the new grant value, which only transitions a waiter into short-term spinning, a mode disabled when LongTermThreshold is…","rationale":"The reader's verdict is CONDITIONAL, citing lack of formal proof, benchmark details, and identifying collision rarity as the weakest assumption. That is a valid concern: the hash is heuristic and collisions cause spurious wakeups. But the more load-bearing flaw is a concrete liveness bug in the advertised LongTermThreshold=0 configuration. The paper explicitly recommends this setting to eliminate spinning, yet with LTT=0 any taker that cannot be admitted immediately waits forever because SemaPost's notification targets the bucket of the new grant value (the successor-of-successor), which only makes sense when the poked thread can then spin on grant. With LTT=0, the poked thread re-enters the waiting array on the same bucket, which is never poked again. This is not a performance nuance; it is a deadlock, reproducible from the published listing. It also indicates that the paper's claim to 'show a working example' in Listing 2 is too broad. The collision concern remains important for the scalability claim, but a correctness failure in a recommended configuration is more decisive; hence the verdict should move from CONDITIONAL to REJECT (or at minimum major revision with the bug fixed and the LTT=0 claim corrected).","tokens_in":25,"tokens_out":22401,"duration_ms":384400,"concrete_test":"Set LongTermThreshold to 0 in Listing 2. Initialize Ticket=0 and Grant=0. Spawn one thread that calls SemaTake and then signals completion; sleep 10 ms; call SemaPost; wait up to 1 second for completion. If the taker does not complete, the deadlock is confirmed. To show the failure is not a fast-path artifact, repeat with two takers and one post; after the post, the second taker is woken, finds dx=0, and re-sleeps on bucket 1, while the first taker is never poked, so neither completes.","verdict_should_be":"REJECT","load_bearing_attack":"Section 2 states: 'If we desire that all threads wait by futex and need to eliminate all spinning, then we simply set LongTermThreshold to 0.' Listing 2 contradicts this. With LongTermThreshold=0, SemaTake never spins: any taker with dx<=0 immediately waits on UpdateSequence for its own bucket, TWAHash(S,tx). SemaPost, after Grant.fetch_add(1) to a new value g, pokes TWAHash(S,g) (when the fast-path check does not return). Bucket g corresponds to the waiter with ticket g, i.e., the second waiter. When grant moves from G to G+1, the thread with ticket G is admitted, but it is waiting on bucket G and is never poked; the thread with ticket G+1 is poked, rechecks, finds dx=0 (not >0), and re-enters the UpdateSequence wait on bucket G+1, which no future post will poke (the next post pokes G+2). With a single waiter, the fast-path returns without any poke because g - Ticket.load() >= 0. In both cases the waiting thread is never awakened. Thus any taker beyond the initial count never completes when LongTermThreshold=0, invalidating the paper's explicit claim that this setting simply eliminates spinning. The root cause is that the notification scheme assumes the poked thread can fall back to short-term spinning (LongTermThreshold>=1); when that assumption is removed, liveness fails. Collision-induced spurious wakeups are a related but secondary fragility: they cause extra rechecks, but the LTT=0 case shows the design is not merely unpredictable but incorrect for an advertised parameter.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two semaphore algorithms: Ticket-Semaphore, a direct adaptation of ticket locks, and TWA-Semaphore, which applies the waiting-array idea from the authors' earlier TWA lock to reduce global spinning. The abstract and text claim that TWA-Semaphore is compact, scalable, of extremely low latency, and fair, with first-come-first-served (or, more precisely, first-come-first-enabled) admission order. Additional waiting-chain and monitor-style variants are sketched in Listings 3-5, intended to support futex- or park-based waiting. The evaluation reports median throughput on one Oracle X5-2 machine, comparing TWA-Semaphore with Ticket-Semaphore and with the pthread semaphore.","tokens_in":21990,"tokens_out":19423,"duration_ms":177533,"significance":"If the algorithm were correct as printed, TWA-Semaphore would be a useful compact FIFO-style semaphore: it preserves the two-counter state of a ticket semaphore, diffuses waiting across a shared array, and is accompanied by a thoughtful discussion of futex, park-unpark, and monitor-style waiting strategies, as well as an explicit acknowledgment of the collision/predictability tradeoff. The paper also includes a direct comparison against an external baseline (pthread), which is a strength. However, as written, the core Listing 2 has a liveness bug that prevents the algorithm from working for more than two concurrent waiters, so the central scalability claim cannot be accepted without correction and re-evaluation.","major_comments":[{"comment":"The notification scheme in SemaPost is shifted by one relative to the admission predicate, so the algorithm is not live even with the default LongTermThreshold=1. Before a post, let Grant=G. SemaTake admits a waiter only when Grant>tx, and it long-term-waits on bucket TWAHash(S,tx) whenever Grant-tx+LongTermThreshold<=0. Hence a waiter with ticket G spins, while a waiter with ticket G+1 is long-term-waiting on bucket G+1. When a post sets Grant=G+1, the waiter with ticket G is admitted and the waiter with ticket G+1 is exactly the one that must be re-awakened to take over the spin role. SemaPost, however, pokes TWAHash(S, g) with g=(G+1)+LongTermThreshold, i.e., bucket G+2 with the default, and the fast-path test g-Ticket.load()>=0 returns without poking when the highest assigned ticket is G+1. Consequently the G+1 waiter is never awakened; with three threads this deadlocks on the first post. The same off-by-one invalidates the explicit statement in Section 2 that setting LongTermThreshold to 0 simply eliminates spinning: with LTT=0 the post pokes bucket G+1 while the waiter needing the wakeup holds ticket G. The notification index should be TWAHash(S, (G+1)+LongTermThreshold-1) and the fast-path cut should be g-Ticket.load()>0. As printed, the benchmark results in Section 3 cannot have been produced by Listing 2.","section":"Listing 2; Section 2 (LongTermThreshold discussion)"},{"comment":"The performance claim is not supported with the reported methodology. Only a median of 11 runs on one X5-2 machine is shown, without error bars, without any direct latency measurement, and without comparison to a second scalable semaphore baseline; the pthread semaphore is not a scalable FIFO implementation. The abstract's 'extremely low latency' is never measured directly, since the throughput of a critical-section loop conflates handover latency, queueing delay, and post cost. The authors should report per-run dispersion, add at least one additional platform, and include a scalable semaphore baseline, or they should temper the 'state-of-the-art performance at both low and high contention levels' claim in the Conclusion.","section":"Section 3, Figure 1"},{"comment":"The fairness claim is stated in the abstract as 'first-come-first-served (FCFS) admission order', but the text then narrows this to 'first-come-first-enabled'. These are different properties: once a thread is enabled by the grant condition it can be preempted before returning from SemaTake, so a later thread may enter the critical section first. Moreover, no proof or invariant is given even for the weaker first-come-first-enabled property. The argument should at least state the invariant that Grant is monotonically increasing and that SemaTake returns only when Grant>tx, and it should address whether the futex/chain variants in Listings 3-5 preserve this property under hash collisions and spurious wakeups.","section":"Abstract; Section 'TWA-Semaphore'"}],"minor_comments":[{"comment":"There are numerous typographical and OCR-like artifacts, including 'Lo ng Te rm Thr es ho ld' in Listing 2, 'MONITOR-MW AIT', 'magntitude', 'semphore', 'taylored', and 'implemeneted'; these should be cleaned before publication.","section":"Throughout"},{"comment":"TWAHash(S, tx) accepts a uint32_t ticket value while Ticket and Grant are declared as uint64_t; the listing should state the intended truncation behavior or widen the parameter, otherwise the hash changes if ticket values ever reach 2^32.","section":"Listing 2, TWAHash"},{"comment":"The assertion assert(e->Gate == 0) in Poke is racy: a concurrent flush can set Gate between the check and the store. Either remove the assertion or justify it under the claimed synchronization discipline.","section":"Listings 3 and 4, Poke"},{"comment":"Poke reads e->Who, but the WaitElement field is declared as 'who'; as written, the snippet does not compile.","section":"Listing 3, WaitElement"},{"comment":"The paper would benefit from stating whether the experimental code is available for reproduction, since the printed listings appear inconsistent with the reported results.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"The liveness bug in Listing 2 is severe, and I would normally lean toward rejection if the algorithm as printed cannot produce the reported results. I am recommending major revision rather than rejection because the defect is a clear off-by-one in the notification index and fast-path threshold, and a corrected variant may restore liveness. However, the authors must provide corrected listings, clarify whether the benchmark used a variant that differs from the printed code, and re-verify the experimental claims. I would also ask the editor to ensure that the fairness claim is aligned with the weaker first-come-first-enabled property actually argued."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—this one has a real liveness bug in a configuration the paper explicitly advertises. Listing 2's TWA-Semaphore, run with LongTermThreshold=0, never wakes waiting threads: with that setting no one takes the short-term spin path, and SemaPost's fast-path (g - Ticket.load() >= 0) suppresses the poke when the only waiter is the one whose ticket equals g-1. The stress-test note is correct; I replayed the code. The paper's claim that setting LTT=0 simply eliminates spinning is false.\n\nWhat's new: the TWA-Semaphore idea itself—porting the TWA waiting-array trick from ticket locks to semaphores—is a genuine extension, and the waiting-chain variant using a lock-free pop-stack is a nice piece of engineering. The benchmark, despite being one machine with no error bars, does show TWA-Semaphore holding up far better than a plain ticket semaphore under high contention.\n\nWhere it gets soft: the LTT=0 bug is the big one, and it is load-bearing in the text, not a footnote. Beyond that, the FCFS claim is argued informally rather than proved, the hash's collision behavior is dismissed with 'we expect,' and the paper doesn't compare against other scalable semaphores (MCS-style queue semaphores, for instance). Some of the novelty is borrowed: ticket-semaphore is the Reed-Kanodia sequencer/eventcount construction, and the paper doesn't acknowledge that equivalence. The benchmark would be much stronger with variance, latency percentiles, and a second platform. There are also editing artifacts throughout—stray notes, broken identifiers like 'Lo ng Te rm Thr es ho ld'—that suggest this was rushed.\n\nThe default threshold (1) makes the main algorithm work, so the core idea isn't hollow. But as written, the paper overclaims. It needs: (1) either remove or fix the LTT=0 configuration (with a proof that some waiter is always poked when threshold is 0), (2) a real correctness argument, and (3) a benchmark with more rigor.\n\nAudience: people who implement synchronization primitives in kernels and runtimes; this is squarely a systems paper. I'd send it to peer review—the idea is worth referee time—but I'd expect the referee to flag the LTT=0 deadlock before anything else. If that gets fixed and the claims are reined in, it could be a solid workshop or short-conference paper.","headline":"TWA-Semaphore has a real liveness bug when LongTermThreshold=0, a configuration the paper itself recommends; the core idea is still plausible but the claims need reining in.","tokens_in":22541,"tokens_out":5073,"would_cite":false,"duration_ms":42218,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Ticket-lock ideas give semaphores fairness and scalable throughput.","keywords":["semaphores","ticket locks","waiting array","scalable synchronization","mutual exclusion","concurrency control","futex","first-come-first-served"],"falsifier":"Instrument the waiting array to count how often a bucket holds more than one waiting thread while running semabench with a single semaphore at high thread counts and with many semaphores whose post operations are synchronized so their ticket streams advance in lockstep; if the collision rate grows with thread count or with the number of lockstep semaphores, and throughput falls toward ticket-semaphore levels, the general scalability claim fails.","tokens_in":21401,"feed_emoji":"🚦","tokens_out":5844,"duration_ms":49286,"temperature":0.7,"pith_summary":"The paper sets out to show that semaphores can be made both fair and scalable by borrowing the ticket-lock idea and then adding a shared hashed waiting array. The first step is the ticket-semaphore, which uses two counters, ticket and grant, to give strict first-come-first-served admission but suffers from global spinning under contention. The second step, the TWA-semaphore, replaces most of that global spinning with semi-local waiting on hashed buckets, so only the thread nearest the front spins on the shared counters. If the central claim holds, the result is a semaphore that is compact, fair in admission order, and degrades far more gracefully than a plain ticket-semaphore as threads pile up.","feed_headline":"Ticket-lock ideas give semaphores fairness and scalable throughput","feed_subtitle":"A shared hashed waiting array replaces global spinning, keeping ticket-order admission with near-zero extra state.","key_machinery":"The machinery is a pair of counters, ticket and grant, plus a fixed table of wait buckets with a ticket-aware hash. In take, a thread fetch-and-adds the ticket counter to get its admission number; in post, a thread atomically increments grant. The hash adds the semaphore address to 17 times the ticket value and masks the result into a 2048- or 4096-entry table, so consecutive tickets from one semaphore walk through the table and waiting is diffused. Two-phase waiting is governed by a tunable LongTermThreshold: waiters close to the head spin directly on grant, while distant waiters watch a per-bucket UpdateSequence counter for notification. This arrangement concentrates global coherent traffic on at most one thread per semaphore and overlaps handover with staging of the next long-term waiter.","core_discovery":"The central claim is that the TWA-Semaphore delivers first-come-first-served, or more precisely first-come-first-enabled, admission order while remaining compact and offering very low latency, because long-term waiters wait on a fixed shared array instead of hammering the semaphore's counters. A thread takes a ticket with fetch-and-add and immediately enters if its ticket is already covered by the grant count; otherwise it spins briefly on grant when it is near the front, and, when it is far from the front, waits on the bucket selected by hashing the semaphore address plus its ticket value. A post increments grant and then pokes the bucket corresponding to the new grant value, staging the successor's successor to shift from long-term to short-term waiting. The benchmark against a ticket-semaphore and the pthread semaphore shows the TWA version matching at low thread counts and pulling ahead as contention rises.","pith_inferences":["The scalability result is workload-dependent: if many semaphores release in lockstep, their ticket streams can entrain, and the fixed table could produce sustained collisions that push the algorithm back toward global spinning; a stress test with synchronized releases across many semaphores would quantify this.","A table sized to the number of logical CPUs, or a hash that rotates through sub-pages of the table, may make the waiting pattern more predictable for streams of consecutive tickets; the paper sketches these variants but does not evaluate them.","Because collisions cause spurious wakeups, the waiting-chain design could double as a general address-based waiting service, so the same scalability might transfer to condition variables and other blocking primitives, not just semaphores."],"forward_implications":["A semaphore can be built from two counters and a shared table, with no per-semaphore queue nodes, while still giving ticket-order admission.","Under high thread counts the TWA-semaphore's throughput degrades more gracefully than the ticket-semaphore's, because only the front waiter spins on the grant counter.","The same transform can be applied to other ticket-based constructs, such as eventcounts and sequencers, to give them the same scalability.","Long-term waiters can be blocked in the kernel via futexes or park-unpark without adding per-semaphore kernel objects, because waiting is already dispersed over many addresses.","Setting the long-term threshold to zero removes all spinning; tuning it trades handover latency against coherence traffic."],"supporting_citations":[{"why":"Supplies the TWA ticket-lock algorithm with a waiting array that this paper adapts to semaphores.","marker":"[4]"},{"why":"Alternate version of the TWA ticket-lock paper providing the same waiting-array mechanism.","marker":"[5]"},{"why":"Establishes the ticket-based resource-allocation idea that the ticket-semaphore is built from.","marker":"[11]"},{"why":"Introduces eventcounts and sequencers, the ticket-style constructs the paper says the transform also applies to.","marker":"[16]"},{"why":"Describes futex waiting, the kernel blocking mechanism used for polite long-term waiting in the variants.","marker":"[12]"},{"why":"Defines the first-come-first-enabled fairness property that the paper claims for TWA-Semaphore.","marker":"[1]"},{"why":"Surveys waiting strategies and motivates the hybrid spin-then-park and threshold design choices.","marker":"[3]"},{"why":"Provides the MutexBench benchmark that the paper modifies into semabench for its evaluation.","marker":"[7]"}],"fun_headline_variants":["Semaphores get fair scaling with a ticket-based waiting array","Ticket-semaphore transform cuts global spinning for low-latency waits","Waiting array makes semaphores scalable without losing ticket fairness","Fairness and scalability meet in semaphores via hashed waiting slots"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that collisions in the shared waiting array are rare, meaning that in general only one thread waits on a given bucket at a time; if unrelated semaphores advance tickets in lockstep or the table is too small, the scalability advantage erodes.","fun_headline_variants_meta":{"raw":{"variants":["Semaphores get fair scaling with a ticket-based waiting array","Ticket-semaphore transform cuts global spinning for low-latency waits","Waiting array makes semaphores scalable without losing ticket fairness","Fairness and scalability meet in semaphores via hashed waiting slots"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000715,"raw_usage":{"total_tokens":3186,"prompt_tokens":885,"completion_tokens":2301,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":2228}},"tokens_in":501,"tokens_out":2301,"duration_ms":13248,"temperature":1.0,"reasoning_tokens":2228,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:26:56.195643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument the waiting array to count how often a bucket holds more than one waiting thread while running semabench with a single semaphore at high thread counts and with many semaphores whose post operations are synchronized so their ticket streams advance in lockstep; if the collision rate grows with thread count or with the number of lockstep semaphores, and throughput falls toward ticket-semaphore levels, the general scalability claim fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the TWA ticket-lock algorithm with a waiting array that this paper adapts to semaphores."},{"cited_title":"TWA -- Ticket Locks Augmented with a Waiting Array","cited_arxiv_id":"1810.01573","evidence_quote":"Alternate version of the TWA ticket-lock paper providing the same waiting-array mechanism."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the ticket-based resource-allocation idea that the ticket-semaphore is built from."},{"cited_title":"Reed and Rajendra K","cited_arxiv_id":null,"evidence_quote":"Introduces eventcounts and sequencers, the ticket-style constructs the paper says the transform also applies to."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes futex waiting, the kernel blocking mechanism used for polite long-term waiting in the variants."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the first-come-first-enabled fairness property that the paper claims for TWA-Semaphore."},{"cited_title":"Malthusian Locks","cited_arxiv_id":"1511.06035","evidence_quote":"Surveys waiting strategies and motivates the hybrid spin-then-park and threshold design choices."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the MutexBench benchmark that the paper modifies into semabench for its evaluation."}],"review_version":1}