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 Ω(n) time in our model, and establish several additional lower bounds and algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)
Sha, L., Abdelzaher, T., Arzen, K.E., Cervin, A., Baker, T., Burns, A., Buttazzo, G., Caccamo, M., Lehoczky, J., Mok, A.K.: Real time scheduling theory: A historical perspective. Real-Time Systems Journal 28(2/3), 101–155 (2004)
Simons, B., Lundelius-Welch, J., Lynch, N.: An overview of clock synchronization. In: Simons, B., Spector, A.Z. (eds.) Fault-Tolerant Distributed Computing. LNCS, vol. 448, pp. 84–96. Springer, Heidelberg (1990)
Lundelius, J., Lynch, N.: An upper and lower bound for clock synchronization. Information and Control 62, 190–240 (1984)
Moser, H., Schmid, U.: Optimal clock synchronization revisited: Upper and lower bounds in real-time systems. Research Report 71/2006, Technische Universität Wien, Institut für Technische Informatik, Treitlstr. 1-3/182-1, 1040 Vienna, Austria (2006), http://www.vmars.tuwien.ac.at/php/pserver/extern/docdetail.php?DID=1973&viewmode=paper&year=2006
Lundelius, J., Lynch, N.: A new fault-tolerant algorithm for clock synchronization. In: Proc. 3rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 75–88 (1984)
Biaz, S., Welch, J.L.: Closed form bounds for clock synchronization under simple uncertainty assumptions. Information Processing Letters 80(3), 151–157 (2001)
Patt-Shamir, B., Rajsbaum, S.: A theory of clock synchronization (extended abstract). In: STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 810–819. ACM Press, New York (1994)
Attiya, H., Herzberg, A., Rajsbaum, S.: Optimal clock synchronization under different delay assumptions. In: PODC 1993: Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, pp. 109–120. ACM Press, New York (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moser, H., Schmid, U. (2006). Optimal Clock Synchronization Revisited: Upper and Lower Bounds in Real-Time Systems. In: Shvartsman, M.M.A.A. (eds) Principles of Distributed Systems. OPODIS 2006. Lecture Notes in Computer Science, vol 4305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945529_8
Download citation
DOI: https://doi.org/10.1007/11945529_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49990-9
Online ISBN: 978-3-540-49991-6
eBook Packages: Computer ScienceComputer Science (R0)