[ main ] [ back ]

77/2008 : Towards a real-time distributed computing model

RR Number
77/2008
Comment
Also published online: Theoretical Computer Science (2008), http://dx.doi.org/10.1016/j.tcs.2008.10.012
Conference
Theoretical Computer Science, Volume 410, Issues 6-7, 28 February 2009, Pages 629-659
Author(s)
Heinrich Moser
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. We provide general simulations and validity conditions for transforming algorithms from the classic synchronous model to our real-time model and vice versa, and 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 drift- and failure-free internal clock synchronization for this purpose, and show that no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. Since such an algorithm is known for the classic model, this is an instance of a problem where the standard distributed computing analysis gives too optimistic results. We prove that optimal precision is only achievable with algorithms that take Ω(n) time in our model, and establish several additional algorithms and lower bounds.
Bibtex
@article{ moser:2008-77,
  author =       "Heinrich Moser",
  title =        "Towards a real-time distributed computing model",
  journal =      "Theoretical Computer Science, Volume 410, Issues 6-7",
  url = "http://dx.doi.org/10.1016/j.tcs.2008.10.012",
  year =         "2009",
  month =        "Feb."
}
Download
Get journal.pdf - Adobe PDF-format, (487.9033 KB; posted at July 09 2013; )

[ main ] [ back ]