License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2015.34
URN: urn:nbn:de:0030-drops-66771
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6677/
Go to the corresponding LIPIcs Volume Portal

Yingchareonthawornchai, Sorrachai ; Kulkarni, Sandeep S. ; Demirbas, Murat

Analysis of Bounds on Hybrid Vector Clocks

pdf-format:
LIPIcs-OPODIS-2015-34.pdf (0.9 MB)

Abstract

Hybrid vector clocks (HVC) implement vector clocks (VC) in a space-efficient manner by exploiting the availability of loosely-synchronized physical clocks at each node. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, epsilon: uncertainty window, delta: minimum message delay, alpha: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases.

Our model and simulations show the HVC size is a sigmoid function with respect to increasing epsilon; it has a slow start but it grows exponentially after a phase transition. We present equations to identify the phase transition point and show that for many practical applications and deployment environments, the size of HVC remains only as a couple entries and substantially less than n. We also find that, in a model with random unicast message transmissions, increasing n actually helps for reducing HVC size.

BibTeX - Entry

@InProceedings{yingchareonthawornchai_et_al:LIPIcs:2016:6677,
  author =	{Sorrachai Yingchareonthawornchai and Sandeep S. Kulkarni and Murat Demirbas},
  title =	{{Analysis of Bounds on Hybrid Vector Clocks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6677},
  URN =		{urn:nbn:de:0030-drops-66771},
  doi =		{10.4230/LIPIcs.OPODIS.2015.34},
  annote =	{Keywords: Vector Clocks, Physical Clocks, Large Scale Systems}
}

Keywords: Vector Clocks, Physical Clocks, Large Scale Systems
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI