{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:03:56Z","timestamp":1775639036872,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:p>We present a logical timestamping mechanism for ordering transactions in distributed databases, eliminating the single point of failure (SPoF) that bother existing timestamp \"oracles\". The main innovation is a bipartite client-server architecture, where the servers do not communicate with each other. The result is a highly available timestamping \"service\" that guarantees the availability of time-stamps, unless half the servers are down at the same time.<\/jats:p>\n          <jats:p>\n            We study the fundamental needs of timestamping, and formalize its availability and correctness properties in a distributed setting. We then introduce the TaaS (timestamp as a service) algorithm, which defines a monotonic spacetime over multiple server clocks. We prove, mathematically: (i)\n            <jats:italic>Availability<\/jats:italic>\n            that the timestamps are always computable, provided any majority of the server clocks being observable; and (ii)\n            <jats:italic>Correctness<\/jats:italic>\n            that all the computed time-stamps must increase monotonically over time, even if some clocks become unobservable.\n          <\/jats:p>\n          <jats:p>We evaluate our algorithm by prototyping TaaS and benchmarking it against state of the art timestamp oracle in TiDB. Our experiment shows that TaaS is indeed immune to SPoF (as we have proven mathematically), while exhibiting a reasonable performance at the same order of magnitude with TiDB. We also demonstrate the stability of our bipartite architecture, by deploying TaaS across datacenters and showing its resilience to datacenter-level failures.<\/jats:p>","DOI":"10.14778\/3641204.3641210","type":"journal-article","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T22:05:43Z","timestamp":1714687543000},"page":"994-1006","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Timestamp as a Service, Not an Oracle"],"prefix":"10.14778","volume":"17","author":[{"given":"Yishuai","family":"Li","sequence":"first","affiliation":[{"name":"Alibaba Cloud, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunfeng","family":"Zhu","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chao","family":"Shi","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guanhua","family":"Zhang","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhong","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaolu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,2]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alibaba Cloud Documentation Center. 2022. Elastic Compute Service: Triplicate storage. https:\/\/www.alibabacloud.com\/help\/en\/elastic-compute-service\/latest\/triplicate-storage."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535930"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00259"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/andp.19053221004"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456236"},{"key":"e_1_2_1_7_1","unstructured":"etcd Authors. 2023. etcd. https:\/\/etcd.io\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/74850.74870"},{"key":"e_1_2_1_9_1","volume-title":"Linux Conf Au (May","author":"Hemminger Stephen","year":"2005","unstructured":"Stephen Hemminger. 2005. Network emulation with NetEm. Linux Conf Au (May 2005)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference","author":"Hunt Patrick","year":"2010","unstructured":"Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. 2010. ZooKeeper: Wait-Free Coordination for Internet-Scale Systems. In Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference (Boston, MA) (USENIXATC'10). USENIX Association, USA, 11."},{"key":"e_1_2_1_12_1","unstructured":"ISO\/IEC. 1998. Distributed Transaction Processing. ISO\/IEC 10026--1:1998."},{"key":"e_1_2_1_13_1","volume-title":"Principles of Distributed Systems, Marcos K","author":"Kulkarni Sandeep S.","unstructured":"Sandeep S. Kulkarni, Murat Demirbas, Deepak Madappa, Bharadwaj Avva, and Marcelo Leone. 2014. Logical Physical Clocks. In Principles of Distributed Systems, Marcos K. Aguilera, Leonardo Querzoni, and Marc Shapiro (Eds.). Springer International Publishing, Cham, 17--32."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Workshop on Parallel and Distributed Algorithms","author":"Mattern Friedemann","year":"1988","unstructured":"Friedemann Mattern. 1988. Virtual Time and Global States of Distributed Systems. Proceedings of the International Workshop on Parallel and Distributed Algorithms (1988)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2517350"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (Philadelphia, PA) (USENIX ATC'14). USENIX Association, USA, 305--320","author":"Ongaro Diego","year":"2014","unstructured":"Diego Ongaro and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (Philadelphia, PA) (USENIX ATC'14). USENIX Association, USA, 305--320."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation.","author":"Peng Daniel","year":"2010","unstructured":"Daniel Peng and Frank Dabek. 2010. Large-scale Incremental Processing Using Distributed Transactions and Notifications. In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation."},{"key":"e_1_2_1_20_1","unstructured":"The PostgreSQL Global Development Group. 2023. Postgres-XL. http:\/\/www.postgres-xl.org\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229868"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.3233\/JHS-160552"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_24_1","unstructured":"TPC. 1992. TPC Benchmark C. https:\/\/www.tpc.org\/tpcc\/."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314049"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554830"},{"key":"e_1_2_1_27_1","unstructured":"Yugabyte Inc. 2023. YugabyteDB. https:\/\/www.yugabyte.com\/."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3641204.3641210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T22:08:17Z","timestamp":1714687697000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3641204.3641210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["10.14778\/3641204.3641210"],"URL":"https:\/\/doi.org\/10.14778\/3641204.3641210","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,1]]},"assertion":[{"value":"2024-05-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}