The celebrated Asynchronous Computability Theorem of Herlihy and Shavit (JACM 1999) provided a topological characterization of the tasks that are wait-free solvable by processes communicating through writing and reading shared registers. This characterization assumes the use of full-information protocols, in which each time a process writes in the shared memory, it communicates everything it learned since the beginning of the execution. Thus, each register in the shared memory is of unbounded size. Whether unbounded size registers are unavoidable for the model of computation to be universal is the central question studied in this paper. That is, is every task solvable wait-free also solvable wait-free when the registers in shared memory are of bounded size? More generally, when at most t out of n processes can crash, is the model with bounded size registers universal, i.e., is every task solvable in the t-resilient model also solvable in the t-resilient model when the registers are of bounded size? We show that when <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(1\le t<n/2\)</EquationSource> </InlineEquation> registers of size O(t) bits are sufficient to solve any task that is solvable by a full-information protocol. The situation is radically different when <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n/2<t <n\)</EquationSource> </InlineEquation>, which includes the wait-free case. We show that bounded registers are not universal. Specifically, we show that, for any bound <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(f:\mathbb {N}\rightarrow \mathbb {N}\)</EquationSource> </InlineEquation>, and for any <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(n>2\)</EquationSource> </InlineEquation>, there exists a task that cannot be solved by n processes communicating via registers of size f(n) bits, but is solvable by n processes using unbounded registers. The case <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(n = 2\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(t=1\)</EquationSource> </InlineEquation>, where 1-resilient computing and wait-free computing coincide, displays a radically different behavior. We show that any task solvable by 2 processes in the wait-free shared-memory model with unbounded-size registers can be solved by 2 processes in the wait-free shared-memory model with constant size registers. Finally, we consider the iterated shared memory model, which has played a crucial role since Herlihy and Shavit’s characterization. We show that 1-bit registers (per iteration) are sufficient for solving wait-free any task that is solvable by a full-information wait-free protocol. Therefore, while the wait-free read/write shared-memory model is known to be computationally equivalent to the iterated model, this equivalence only holds if registers are unbounded.

The computational power of distributed shared-memory models with bounded-size registers

期刊论文
发表日期：

2026年1月19日

查看全文

Carole Delporte-Gallet,
Hugues Fauconnier,
Pierre Fraigniaud,
Sergio Rajsbaum,
Corentin Travers

摘要

The celebrated Asynchronous Computability Theorem of Herlihy and Shavit (JACM 1999) provided a topological characterization of the tasks that are wait-free solvable by processes communicating through writing and reading shared registers. This characterization assumes the use of full-information protocols, in which each time a process writes in the shared memory, it communicates everything it learned since the beginning of the execution. Thus, each register in the shared memory is of unbounded size. Whether unbounded size registers are unavoidable for the model of computation to be universal is the central question studied in this paper. That is, is every task solvable wait-free also solvable wait-free when the registers in shared memory are of bounded size? More generally, when at most t out of n processes can crash, is the model with bounded size registers universal, i.e., is every task solvable in the t-resilient model also solvable in the t-resilient model when the registers are of bounded size? We show that when \(1\le t<n/2\) registers of size O(t) bits are sufficient to solve any task that is solvable by a full-information protocol. The situation is radically different when \(n/2<t <n\) , which includes the wait-free case. We show that bounded registers are not universal. Specifically, we show that, for any bound \(f:\mathbb {N}\rightarrow \mathbb {N}\) , and for any \(n>2\) , there exists a task that cannot be solved by n processes communicating via registers of size f(n) bits, but is solvable by n processes using unbounded registers. The case \(n = 2\) , \(t=1\) , where 1-resilient computing and wait-free computing coincide, displays a radically different behavior. We show that any task solvable by 2 processes in the wait-free shared-memory model with unbounded-size registers can be solved by 2 processes in the wait-free shared-memory model with constant size registers. Finally, we consider the iterated shared memory model, which has played a crucial role since Herlihy and Shavit’s characterization. We show that 1-bit registers (per iteration) are sufficient for solving wait-free any task that is solvable by a full-information wait-free protocol. Therefore, while the wait-free read/write shared-memory model is known to be computationally equivalent to the iterated model, this equivalence only holds if registers are unbounded.