Maryam Helmi
ABSTRACT
This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen, Fatourou and Ruppert [7] showed that √n/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps).
We improve this existing lower bound in two ways. First we establish a lower bound of n/6 - O(1) registers for the obstruction-free long-lived timestamp problem. Previous such linear lower bounds were only known for constrained versions of the timestamp problem. This bound is asymptotically tight; Ellen, Fatourou and Ruppert [7] constructed a wait-free algorithm that uses n-1 registers. Second we show that √(n)-O(1) registers are required for any obstruction-free implementation of one-shot timestamp systems (meaning each processor can get a timestamp at most once). We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses fewer than 2√n registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.
- K. R. Abrahamson. On achieving consensus using a shared memory. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 291--302, 1988. Google Scholar
Digital Library
- Y. Afek, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. A bounded first-in, first-enabled solution to the $l$-exclusion problem. ACM Transactions on Programming Languages and Systems, 16(3):939--953, 1994. Google ScholarDigital Library
- H. Attiya and A. Fouren. Algorithms adapting to point contention. Journal of the ACM, 50(4):444--468, 2003. Google ScholarDigital Library
- J. E. Burns and N. A. Lynch. Bounds on shared memory for mutual exclusion. Information and Computation, 107(2):171--184, 1993. Google ScholarDigital Library
- D. Dolev and N. Shavit. Bounded concurrent time-stamping. SIAM Journal on Computing, 26(2):418--455, 1997. Google ScholarDigital Library
- C. Dwork and O. Waarts. Simple and efficient bounded concurrent timestamping and the traceable use abstraction. Journal of the ACM, 46(5):633--666, 1999. Google ScholarDigital Library
- F. Ellen, P. Fatourou, and E. Ruppert. The space complexity of unbounded timestamps. Distributed Computing, 21(2):103--115, 2008.Google ScholarDigital Library
- F. E. Fich, M. P. Herlihy, and N. Shavit. On the space complexity of randomized synchronization. Journal of the ACM, 45(5):843--862, 1998. Google ScholarDigital Library
- C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. In 11th Australian Computer Science Conference (ACSC'88), pages 56--66, 1988.Google Scholar
- M. J. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin. Distributed fifo allocation of identical resources using small shared space. ACM Transactions on Programming Languages and Systems, 11(1):90--114, 1989. Google ScholarDigital Library
- R. Gawlick, N. A. Lynch, and N. Shavit. Concurrent timestamping made simple. In 1st Israel Symposium on Theory of Computing Systems (ISTCS), pages 171--183, 1992. Google ScholarDigital Library
- R. Guerraoui and E. Ruppert. Anonymous and fault-tolerant shared-memory computing. Distributed Computing, 20(3):165--177, 2007.Google ScholarDigital Library
- S. Haldar and P. M. B. Vitányi. Bounded concurrent timestamp systems using vector clocks. Journal of the ACM, 49(1):101--126, 2002. Google ScholarDigital Library
- M. Helmi, L. Higham, E. Pacheco, and P. Woelfel. The space complexity of long-lived and one-shot timestamp implementations. 2011, arXiv:1103.5794 {cs.DC}.Google Scholar
- A. Israeli and M. Li. Bounded time-stamps. Distributed Computing, 6(4):205--209, 1993. Google ScholarDigital Library
- A. Israeli and M. Pinhasov. A concurrent time-stamp scheme which is linear in time and space. In Distributed Algorithms, 6th International Workshop (WDAG), pages 95--109, 1992. Google ScholarDigital Library
- L. Lamport. A new solution of dijkstra's concurrent programming problem. Communications of the ACM, 17(8):453--455, 1974. Google ScholarDigital Library
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, 1978. Google ScholarDigital Library
- M. Li, J. Tromp, and P. M. B. Vitányi. How to share concurrent wait-free variables. Journal of the ACM, 43(4):723--746, 1996. Google ScholarDigital Library
- F. Mattern. Virtual time and global states of distributed systems. In Proceedings of the International Workshop on Parallel and Distributed Algorithms, pages 215--226, 1989.Google Scholar
- G. Ricart and A. K. Agrawala. An optimal algorithm for mutual exclusion in computer networks. Communications of the ACM, 24(1):9--17, 1981. Google ScholarDigital Library
- S. K. Sarin and N. A. Lynch. Discarding obsolete information in a replicated database system. IEEE Transactions on Software Engineering, 13(1):39--47, 1987. Google ScholarDigital Library
- P. M. B. Vitányi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In 27th Annual Symposium on Foundations of Computer Science (FOCS), pages 233--243, 1986. Google ScholarDigital Library
- G. T. J. Wuu and A. J. Bernstein. Efficient solutions to the replicated log and dictionary problems. Operating Systems Review, 20(1):57--66, 1986. Google ScholarDigital Library
Index Terms
- The space complexity of long-lived and one-shot timestamp implementations
Recommendations
The Space Complexity of Long-Lived and One-Shot Timestamp Implementations
This article is concerned with the problem of implementing an unbounded timestamp object from multiwriter atomic registers, in an asynchronous distributed system of n processes with distinct identifiers where timestamps are taken from an arbitrary ...
The space complexity of unbounded timestamps
The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events throughout the system with timestamps that provide information about the real-time ordering of those events. We consider the ...
Time and Space Lower Bounds for Nonblocking Implementations
We show the following time and space complexity lower bounds. Let $\cal{I}$ be any randomized nonblocking n -process implementation of any object in set A from any combination of objects in set B , where A = {increment, fetch&add, modulo k ...
Comments