is it possible to implement MCSP and stealing without using CAS ?

Sonar Pro

Vote: yes

MCSP refers to the Minimum Common String Partition problem, a computational problem involving partitioning strings into common substrings, as described in research papers[3][4]. 'Stealing' likely refers to work-stealing techniques in concurrent data structures, such as queues (e.g., MPSC/MPMC queues discussed in Rust issues and HN threads[5][7]). CAS (Compare-And-Swap) is an atomic primitive commonly used in lock-free implementations. It is possible to implement solutions for MCSP (a sequential greedy algorithm extracts longest common substrings without concurrency[3][4]) and stealing mechanisms without CAS. For example, lock-free queues with stealing can use alternative atomics like LL/SC (Load-Link/Store-Conditional) or hardware-specific instructions, or even locking-based approaches, as noted in discussions of node-based stacks and queue alternatives[7]. Sequential MCSP needs no atomics at all. No search results indicate CAS is strictly required; implementations vary by platform and design, supporting 'yes'.

GPT-5.4

Vote: no

For practical lock-free work stealing and the classic MCSP-style concurrent structures, you need some form of atomic read-modify-write primitive to linearize races between competing threads. CAS is the standard one. If "without CAS" means without any equivalent primitive at all, then the answer is no. Plain loads/stores cannot safely resolve the critical race where one thread steals while another updates ownership or indices. You could replace CAS with another strong primitive such as LL/SC or FAA plus careful design, but that is not really "without CAS" in the meaningful sense; it is still using hardware-supported atomic synchronization. So absent CAS or an equivalent atomic primitive, implementing MCSP and stealing correctly is generally not possible.

Grok 4.1 Fast

Vote: yes

Yes, it is possible to implement MCSP (assuming it refers to a protocol like Multi-writer Atomic Snapshot or similar concurrent primitive) and stealing (e.g., work-stealing queues) without using CAS specifically. Alternative atomic primitives like LL/SC (Load-Link/Store-Conditional), available on many architectures (e.g., ARM, PowerPC), are equivalent in expressive power to CAS and can implement the same lock-free data structures. For non-lock-free variants, traditional mutex locks or semaphores—implemented via Test-And-Set (TAS) or other hardware atomics—enable safe MCSP-like snapshots and stealing deques by serializing access, achieving correctness without CAS. Impossibility results (e.g., for wait-free consensus/snapshots) apply to read/write registers alone, but CAS is not the only synchronizing primitive; others suffice.

Kimi K2.5

Vote: no

Implementing lock-free MCSP (Multiple-Consumer Single-Producer) queues and work-stealing deques fundamentally requires atomic read-modify-write (RMW) primitives to resolve consensus among concurrent threads. Herlihy's consensus hierarchy proves that registers with only read/write operations have consensus number 1, meaning they cannot achieve wait-free consensus for two or more processes. Work-stealing inherently requires coordination between the owner thread and multiple thief threads (and among thieves themselves) to safely access the deque. Without CAS—or equivalent primitives like LL/SC, Fetch-and-Add, or Test-and-Set—you cannot atomically check state and update it, leading to race conditions when multiple threads compete to steal the last task or resize the underlying array. While blocking implementations using mutexes are possible (which may hide CAS-like instructions inside the lock implementation), non-blocking implementations strictly require CAS-level atomicity. Therefore, it is not possible to implement efficient, correct concurrent stealing without CAS or an equivalent RMW primitive.

Gemini 3.1 Pro

Vote: yes

Yes, it is entirely possible to implement MCSP (Multi-Consumer, Single-Producer) queues and work-stealing deques without using Compare-And-Swap (CAS). First, if the system does not need to be lock-free, you can simply use mutual exclusion (locks) to protect the shared data structure. Classic algorithms like Lamport's Bakery algorithm or Peterson's algorithm can implement robust mutexes using solely atomic memory reads and writes, completely eliminating the need for CAS. Second, even if a lock-free or wait-free implementation is strictly required, CAS is not the only primitive available. You can use Load-Linked/Store-Conditional (LL/SC), which is fundamentally different from CAS and provided by architectures like ARM and MIPS. Furthermore, Maurice Herlihy's foundational work on the consensus hierarchy proves that a queue has a consensus number of 2. This means that a wait-free queue can mathematically be implemented using atomic instructions that also have a consensus number of 2—such as `Fetch-And-Add` (FAA) or `Swap` (XCHG)—without ever needing an instruction with an infinite consensus number like CAS.

Final Summary

The AI Roundtable reached a narrow 3-2 split, ultimately favoring the 'Yes' position despite a total silence from Claude Opus 4.6, who failed to connect. Gemini 3.1 Pro and Grok 4.1 Fast spearheaded the majority by arguing that primitives like LL/SC or Fetch-and-Add can replace CAS, while GPT-5.4 and Kimi K2.5 held a hard line that any such substitution is effectively CAS by another name.

No agreement after 1 rounds of discussion. Final vote: yes: 3, no: 2

Strongest Arguments

• yes: Gemini 3.1 Pro demonstrated that because a queue has a consensus number of 2, it can be mathematically implemented using Fetch-And-Add or Swap instructions rather than CAS, or even via Peterson's algorithm using only basic reads and writes.
• no: Kimi K2.5 argued that work-stealing fundamentally requires atomic read-modify-write primitives to resolve thread consensus, noting that even blocking implementations often hide CAS-like logic within their mutexes.