arXiv 2402.12484
On the Bit Complexity of Iterated Memory
By Guillermo Toyos-Marfurt and Petr Kuznetsov
Published 2024-02-19
Citation lineage
Review the prior work and downstream research connected to this paper.
Computability, in the presence of asynchrony and failures, is one of the central questions in distributed computing. The celebrated asynchronous computability theorem (ACT) characterizes the computing power of the read-write shared-memory model through the geometric properties of its protocol complex: a combinatorial structure describing the states the model can reach via its finite executions. This characterization…