{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T17:12:34Z","timestamp":1756573954572},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T00:00:00Z","timestamp":1209427200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s00446-008-0060-6","type":"journal-article","created":{"date-parts":[[2008,4,28]],"date-time":"2008-04-28T12:58:05Z","timestamp":1209387485000},"page":"103-115","source":"Crossref","is-referenced-by-count":14,"title":["The space complexity of unbounded timestamps"],"prefix":"10.1007","volume":"21","author":[{"given":"Faith","family":"Ellen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiota","family":"Fatourou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Ruppert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,4,29]]},"reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.: On achieving consensus using a shared memory. In: Proc. 7th ACM Symposium on Principles of Distributed Computing, pp. 291\u2013302 (1988)","DOI":"10.1145\/62546.62594"},{"issue":"3","key":"60_CR2","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1145\/177492.177731","volume":"16","author":"Y. Afek","year":"1994","unstructured":"Afek, Y., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: A bounded first-in, first-enabled solution to the l-exclusion problem. ACM Trans. Program. Lang. Syst. 16(3), 939\u2013953 (1994)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"60_CR3","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0196-6774(90)90021-6","volume":"11","author":"J. Aspnes","year":"1990","unstructured":"Aspnes, J., Herlihy, M.: Fast, randomized consensus using shared memory. J. Algorithms 11(2), 441\u2013461 (1990)","journal-title":"J. Algorithms"},{"issue":"4","key":"60_CR4","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/792538.792541","volume":"50","author":"H. Attiya","year":"2003","unstructured":"Attiya, H., Fouren, A.: Algorithms adapting to point contention. J. ACM 50(4), 444\u2013468 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"60_CR5","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1006\/inco.1993.1065","volume":"107","author":"J. Burns","year":"1993","unstructured":"Burns, J., Lynch, N.: Bounds on shared memory for mutual exclusion. Inf. Comput. 107(2), 171\u2013184 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"60_CR6","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(91)90055-M","volume":"39","author":"B. Charron-Bost","year":"1991","unstructured":"Charron-Bost, B.: Concerning the size of logical clocks in distributed systems. Inf. Process. Lett. 39(1), 11\u201316 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"60_CR7","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/S0097539790192647","volume":"26","author":"D. Dolev","year":"1997","unstructured":"Dolev, D., Shavit, N.: Bounded concurrent time-stamping. SIAM J. Comput. 26(2), 418\u2013455 (1997)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"60_CR8","doi-asserted-by":"crossref","first-page":"1848","DOI":"10.1137\/S0097539793243685","volume":"28","author":"C. Dwork","year":"1999","unstructured":"Dwork, C., Herlihy, M., Plotkin, S., Waarts, O.: Time-lapse snapshots. SIAM J. Comput. 28(5), 1848\u20131874 (1999)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"60_CR9","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1145\/324133.324161","volume":"46","author":"C. Dwork","year":"1999","unstructured":"Dwork, C., Waarts, O.: Simple and efficient bounded concurrent timestamping and the traceable use abstraction. J. ACM 46(5), 633\u2013666 (1999)","journal-title":"J. ACM"},{"key":"60_CR10","doi-asserted-by":"crossref","unstructured":"Ellen, F., Fatourou, P., Ruppert, E.: The space complexity of unbounded timestamps. In: Proc. Distributed Computing, 21st International Symposium. LNCS, vol. 4731, pp. 223\u2013237 (2007)","DOI":"10.1007\/978-3-540-75142-7_19"},{"key":"60_CR11","doi-asserted-by":"crossref","unstructured":"Fatourou, P., Fich, F.E., Ruppert, E.: Time-space tradeoffs for implementations of snapshots. In: Proc. 38th ACM Symposium on Theory of Computing, pp. 169\u2013178 (2006)","DOI":"10.1145\/1132516.1132542"},{"issue":"5","key":"60_CR12","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1145\/290179.290183","volume":"45","author":"F. Fich","year":"1998","unstructured":"Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. J. ACM 45(5), 843\u2013862 (1998)","journal-title":"J. ACM"},{"issue":"8","key":"60_CR13","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/2.84874","volume":"24","author":"C. Fidge","year":"1991","unstructured":"Fidge, C.: Logical time in distributed computing systems. Computer 24(8), 28\u201333 (1991)","journal-title":"Computer"},{"issue":"3","key":"60_CR14","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s00446-007-0042-0","volume":"20","author":"R. Guerraoui","year":"2007","unstructured":"Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3), 165\u2013177 (2007)","journal-title":"Distrib. Comput."},{"issue":"1","key":"60_CR15","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1145\/505241.505246","volume":"49","author":"S. Haldar","year":"2002","unstructured":"Haldar, S., Vit\u00e1nyi, P.: Bounded concurrent timestamp systems using vector clocks. J. ACM 49(1), 101\u2013126 (2002)","journal-title":"J. ACM"},{"issue":"1","key":"60_CR16","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"60_CR17","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proc. 23rd IEEE International Conference on Distributed Computing Systems, pp. 522\u2013529 (2003)","DOI":"10.1109\/ICDCS.2003.1203503"},{"issue":"3","key":"60_CR18","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M.P. Herlihy","year":"1990","unstructured":"Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"4","key":"60_CR19","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF02242708","volume":"6","author":"A. Israeli","year":"1993","unstructured":"Israeli, A., Li, M.: Bounded time-stamps. Distrib. Comput. 6(4), 205\u2013209 (1993)","journal-title":"Distrib. Comput."},{"key":"60_CR20","doi-asserted-by":"crossref","unstructured":"Israeli, A., Pinhasov, M.: A concurrent time-stamp scheme which is linear in time and space. In: Proc. 6th International Workshop on Distributed Algorithms, pp. 95\u2013109 (1992)","DOI":"10.1007\/3-540-56188-9_7"},{"issue":"2","key":"60_CR21","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1137\/S0097539797317299","volume":"30","author":"P. Jayanti","year":"2000","unstructured":"Jayanti, P., Tan, K., Toueg, S.: Time and space lower bounds for nonblocking implementations. SIAM J. Comput. 30(2), 438\u2013456 (2000)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"60_CR22","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1145\/361082.361093","volume":"17","author":"L. Lamport","year":"1974","unstructured":"Lamport, L.: A new solution of Dijkstra\u2019s concurrent programming problem. Commun. ACM 17(8), 453\u2013455 (1974)","journal-title":"Commun. ACM"},{"issue":"7","key":"60_CR23","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/359545.359563","volume":"21","author":"L. Lamport","year":"1978","unstructured":"Lamport, L.: Time, clocks and the ordering of events in a distributed system. Commun. ACM 21(7), 558\u2013565 (1978)","journal-title":"Commun. ACM"},{"issue":"4","key":"60_CR24","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/234533.234556","volume":"43","author":"M. Li","year":"1996","unstructured":"Li, M., Tromp, J., Vit\u00e1nyi, P.M.B.: How to share concurrent wait-free variables. J. ACM 43(4), 723\u2013746 (1996)","journal-title":"J. ACM"},{"key":"60_CR25","unstructured":"Mattern, F.: Virtual time and global states of distributed systems. In: Proc. Workshop on Parallel and Distributed Algorithms, pp. 215\u2013226 (1989)"},{"key":"60_CR26","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., Michael, L., Spirakis, P.: Computing on a partially eponymous ring. In: Proc. 10th International Conference on Principles of Distributed Systems, pp. 380\u2013394 (2006)","DOI":"10.1007\/11945529_27"},{"key":"60_CR27","doi-asserted-by":"crossref","unstructured":"Vit\u00e1nyi, P.M.B., Awerbuch, B.: Atomic shared register access by asynchronous hardware. In: Proc. 27th IEEE Symposium on Foundations of Computer Science, pp. 233\u2013243 (1986)","DOI":"10.1109\/SFCS.1986.11"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-008-0060-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-008-0060-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-008-0060-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:26:37Z","timestamp":1559136397000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-008-0060-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,29]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["60"],"URL":"https:\/\/doi.org\/10.1007\/s00446-008-0060-6","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,29]]}}}