Optimal clock synchronization revisited: upper and lower bounds in real-time systems

摘要: This paper introduces a simple real-time distributed computing model for message-passing systems, which reconciles the and systems perspective: By just replacing instantaneous steps with of non-zero duration, we obtain that both facilitates scheduling analysis retains compatibility classic techniques results. As by-product, it also allows us to investigate whether/which properties real are inaccurately or even wrongly captured when resorting zero step-time models. We revisit well-studied problem deterministic internal clock synchronization this purpose, show that, contrary model, no algorithm constant running time can achieve optimal precision in our model. prove is only achievable algorithms take Ω(n) establish several additional lower bounds algorithms.