Effectiveness of delaying timestamp computation

Sandeep S. Kulkarni, Nitin H. Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Practical algorithms for determining causality by assigning times-tamps to events have focused on online algorithms, where a permanent timestamp is assigned to an event as soon as it is created. We address the problem of reducing size of the timestamp by utilizing the underlying topology (which is often not fully connected since not all processes talk to each other) and deferring the assignment of a timestamp to an event for a suitably chosen period of time after the event occurs. Specifically, we focus on inline timestamps, which are a generalization of offine timestamps that are assigned after the computation terminates. We show that for a graph with vertex cover VC, it is possible to assign inline timestamps which contains only 2/VC/+2 elements. In particular, for a system with n processes and K events per process, the size of a timestamp for any event is at most log2 n+(2/VC/+1) log2(K+1) bits. By contrast, if online timestamps are desired, then even for a star network, vector timestamp of length n (for the case of integer elements) or n - 1 (for the case of real-valued elements) is required. Moreover, in addition to being efficient, the inline timestamps developed can be used to solve typical problems such as predicate detection, replay, recovery that are solved with vector clocks.

Original languageEnglish (US)
Title of host publicationPODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages263-272
Number of pages10
ISBN (Electronic)9781450349925
DOIs
StatePublished - Jul 26 2017
Event36th ACM Symposium on Principles of Distributed Computing, PODC 2017 - Washington, United States
Duration: Jul 25 2017Jul 27 2017

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing
VolumePart F129314

Other

Other36th ACM Symposium on Principles of Distributed Computing, PODC 2017
CountryUnited States
CityWashington
Period7/25/177/27/17

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Effectiveness of delaying timestamp computation'. Together they form a unique fingerprint.

  • Cite this

    Kulkarni, S. S., & Vaidya, N. H. (2017). Effectiveness of delaying timestamp computation. In PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing (pp. 263-272). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. Part F129314). Association for Computing Machinery. https://doi.org/10.1145/3087801.3087818