[ main ] [ back ]

109/2006 : Optimal Clock Synchronization Revisited: Upper and Lower Bounds in Real-Time Systems

RR Number
109/2006
Conference
Proceedings of the International Conference on Principles of Distributed Systems (OPODIS'06)
Author(s)
Heinrich Moser, Ulrich Schmid
Abstract
This paper introduces a simple real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: By just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time scheduling analysis and retains compatibility with classic distributed computing analysis techniques and results. As a by-product, it also allows us to investigate whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models. We revisit the well-studied problem of deterministic internal clock synchronization for this purpose, and show that, contrary to the classic model, no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. We prove that optimal precision is only achievable with algorithms that take Omega(n) time in our model, and establish several additional lower bounds and algorithms.
Bibtex
@InProceedings{MS06,
  author = 	 {Heinrich Moser and Ulrich Schmid},
  title = 	 {Optimal clock synchronization revisited: {U}pper and lower bounds in real-time systems},
  booktitle =    {Proceedings of the International Conference on
                  Principles of Distributed Systems (OPODIS)},
  year = 	 2006,
  address =	 {Bordeaux \& Saint-Emilion, France},
  month = 	 {Dec},
  series =       {LNCS},
  publisher =    {Springer Verlag}
}
Download
Get paper.pdf - Adobe PDF-format, (179.1797 KB; posted at July 09 2013; )

[ main ] [ back ]