TY - GEN

T1 - Effectiveness of delaying timestamp computation

AU - Kulkarni, Sandeep S.

AU - Vaidya, Nitin H.

N1 - Funding Information:
Acknowledgements: Kulkarni is supported in part by NSF CNS 1329807, NSF CNS 1318678, and XPS 1533802. Vaidya is supported in part by NSF 1409416 and Toyota InfoTechnology Center USA. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government. Œe authors thank Vijay Garg, Ajay Kshemkalyani and Jennifer Welch for their feedback. We thank Marek Zawirski for answering questions about Swi‰Cloud [25].

PY - 2017/7/26

Y1 - 2017/7/26

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85027872164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027872164&partnerID=8YFLogxK

U2 - 10.1145/3087801.3087818

DO - 10.1145/3087801.3087818

M3 - Conference contribution

AN - SCOPUS:85027872164

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 263

EP - 272

BT - PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 36th ACM Symposium on Principles of Distributed Computing, PODC 2017

Y2 - 25 July 2017 through 27 July 2017

ER -