Distributed Computing Вычислительная теория и математика

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

Delporte-Gallet, Carole, Fauconnier, Hugues, Fraigniaud, Pierre, Rajsbaum, Sergio, Travers, Corentin
Springer Nature · 2026-01-19 · DOI 10.1007/s00446-025-00492-w

Аннотация

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 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.

Читать у издателя →