The space complexity of long-lived and one-shot timestamp implementations
DOI10.1145/1993806.1993826zbMath1321.68358arXiv1103.5794OpenAlexW2043462337MaRDI QIDQ2943392
Eduardo Pacheco, Lisa Higham, Maryam Helmi, Philipp Woelfel
Publication date: 11 September 2015
Published in: Journal of the ACM, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.5794
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Related Items (3)
Cites Work
- Unnamed Item
- The space complexity of unbounded timestamps
- Gradient clock synchronization in dynamic networks
- Consensus algorithms with one-bit messages
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Broadcasting in dynamic radio networks
- Programming simultaneous actions using common knowledge
- Bounded time-stamps
- Bounds on shared memory for mutual exclusion
- Anonymous and fault-tolerant shared-memory computing
- Continuous consensus via common knowledge
- Distributed computation in dynamic networks
- Flooding time in edge-Markovian dynamic graphs
- On the space complexity of randomized synchronization
- Simple and efficient bounded concurrent timestamping and the traceable use abstraction
- Bounded concurrent timestamp systems using vector clocks
- Algorithms adapting to point contention
- Knowledge and common knowledge in a distributed environment
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
- Fault Tolerance in Networks of Bounded Degree
- Reaching Agreement in the Presence of Faults
- Perfectly secure message transmission
- Time, clocks, and the ordering of events in a distributed system
- Atomic snapshots of shared memory
- Bounded Concurrent Time-Stamping
- How to share concurrent wait-free variables
- A new solution of Dijkstra's concurrent programming problem
- Parsimonious flooding in dynamic graphs
- Optimal gradient clock synchronization in dynamic networks
- Almost-Everywhere Secure Computation
This page was built for publication: The space complexity of long-lived and one-shot timestamp implementations
