Space-Time Trade-off in Bounded Iterated Memory
Preprint
Abstract
The celebrated asynchronous computability theorem (ACT) characterizes tasks solvable in the read-write shared-memory model using the unbounded full-information protocol, where in every round of computation, each process shares its complete knowledge of the system with the other processes. Therefore, ACT assumes shared-memory variables of unbounded capacity. It has been recently shown that boundedvariables can achieve the same computational power at the expense of extra rounds. However, the exact relationship between the bit capacity of the shared memory and the number of rounds required in order to implement one round of the full-information protocol remained unknown. In this paper, we focus on the asymptotic round complexity of bounded iterated shared-memory algorithms that simulate, up to isomorphism, the unbounded full-information protocol. We relate the round complexity to the number of processes $n$, the number of iterations of the full information protocol $r$, and the bit size per shared-memory entry $b$. By analyzing the corresponding protocol complex, a combinatorial structure representing reachable states, we derive necessary conditions and present a bounded full-information algorithm tailored to the bits available $b$ per shared memory entry. We show that for $n>2$, the round complexity required to implement the full-information protocol satisfies $Ω((n!)^{r-1} \cdot 2^{n-b})$. Our results apply to a range of iterated shared-memory models, from regular read-write registers to atomic and immediate snapshots. Moreover, our bounded full-information algorithm is asymptotically optimal for the iterated collect model and within a linear factor $n$ of optimal for the snapshot-based models.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- The Computational Power of Distributed Shared-Memory Models with Bounded-Size Registers2024
- On the Bit Complexity of Iterated Memory2024
- A generalized asynchronous computability theorem2014
- Distributed Computing Through Combinatorial Topology2014
- The topology of shared-memory adversaries2010
- Toward a Topological Characterization of Asynchronous ComplexitySIAM Journal on Computing, 2006
- The topological structure of asynchronous computabilityJournal of the ACM, 1999
- Shellability and the Upper Bound Theorem1995
- Immediate atomic snapshots and fast renaming1993
- Reducibility among Combinatorial Problems1972