Combination of clock-state and clock-rate correction in fault-tolerant distributed systems. (English) Zbl 1103.68384
Summary: This paper proposes the integration of internal and external clock synchronization by a combination of a fault-tolerant distributed algorithm for clock state correction with a central algorithm for clock rate correction. By means of hardware and simulation experiments it is shown that this combination improves the precision of the global time base in a distributed single cluster system while reducing the need for high-quality oscillators. Simulation results have shown that the rate-correction algorithm contributes not only in the internal clock synchronization of a single cluster system, but it can be used for external clock synchronization of a multi-cluster system with a reference clock. Therefore, deployment of the rate-correction algorithm integrates internal and external clock synchronization in one mechanism. Experimental results show that a failure in the clock rate correction will not hinder the distributed fault-tolerant clock state synchronization algorithm, since the state correction operates independently from the rate correction. The paper introduces new algorithms and presents experimental results on the achieved improvements in the precision measured in a time-triggered system. Results of simulation experiments of the new algorithms in single-cluster and multi-cluster configurations are also presented.
MSC:
| 68M14 | Distributed systems |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
real-time system; global time; clock synchronization; rate adaptation; fault-tolerant time baseReferences:
| [1] | Ademaj A (2002) Slightly-Off-Specification failures in the time-triggered architecture. In Proceesdings of the 7th Anual IEEE International Workshop on High Level Design Validation and Test, Cannes, France |
| [2] | Anceaume E and Puaut I (1998) Performance evaluation of clock synchronization algorithms. Technical report 3526, Institut de Recherche en Informatique et Systèmes Aléatoires. |
| [3] | Anceaume E, Puaut I (1997) A Taxonomy of Clock Synchronization Algorithms, Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Research Report 1103, Available at: http://citeseer.ist.psu.edu/anceaume97taxonomy.html |
| [4] | Barak B, Halevi S, Herzberg A, Naor D (2000) Clock synchronization with faults and recoveries. Symposium on Principles of Distributed Computing, p.133–142. · Zbl 1314.68367 |
| [5] | Belschner R, Berwanger J, Ebner C, Führer T, Hartwitsch F et al. FlexRay Requirements Specification Version 2.1. Available at: http://www.flexray-group.com/ |
| [6] | Cristian F, Aghili H, Strong R (1994) Clock synchronization in the presence of omission and performance failures, and processor joins. Zhonghua Yang and T. Anthony Marsland (eds), Global States and Time in Distributed Systems, IEEE Computer Society Press. |
| [7] | Cristian F, Fetzer C (1985) Fault-tolerant external clock synchronization. Proceedings of the 15th International Conference on Distributed Computing Systems. IEEE, pp. 70–77. |
| [8] | Cristian F, Fetzer C (1994) Probabilistic internal clock synchronization. Symposium on Reliable Distributed Systems, 22–31. |
| [9] | Dana PH (1997) Global positioning system (GPS) time dissemination for real-time applications. Real-Time Systems Journal 12:9–40. · doi:10.1023/A:1007906014916 |
| [10] | Fetzer C, Cristian F (1995) An optimal internal clock synchronization algorithm. compass 95: 10th Annual Conference on Computer Assurance, National Institute of Standards and Technology, Gaithersburg, Maryland, pp. 187–196 |
| [11] | Fetzer C, Cristian F (1997) Integrating external and internal clock synchronization. Real-Time Systems, 12(2): 123–171. · doi:10.1023/A:1007905917490 |
| [12] | Führer T, Möller B, Dieterle W, Hartwich F, Hugel R, Walther RB GmbH (2000) Time triggered communication on CAN. Proceedings of 7th International CAN Conference. |
| [13] | Halpern JY, Simons B, Strong R, Dolev D (1984) Fault-tolerant clock synchronization. Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing, pp. 89–102 · Zbl 0886.68008 |
| [14] | Hanzlik A (2003) SIDERA–a simulation model for the time-triggered architecture. Research Report, Vienna University of Technology, Real-Time Systems Group, Vienna, Austria |
| [15] | F. Cristian. Probabilistic Clock Synchronization. Distributed Computing, Vol. 3, pp. 146–158, 1989 · Zbl 0703.68018 · doi:10.1007/BF01784024 |
| [16] | Kopetz H (1997) Real-time systems, design principles for distributed embedded applications. ISBN: 0–7923-9894–7, Sixth printing 2002., Boston: Kluwer Academic Publishers |
| [17] | Kopetz H, Ademaj A, Grillinger P, Steinhammer K (2005) The time-triggered ethernet (TTE) design. 8th IEEE International Symposium on Object-oriented Real-time distributed Computing (ISORC), Seattle, Washington, 18–20 |
| [18] | Kopetz H, Bauer G (2003) The time-triggered architecture. Proceedings of the IEEE, Vol. 91, pp 112–126 · doi:10.1109/JPROC.2002.805821 |
| [19] | Kopetz H, Krüger A, Millinger D, and Schedl A (1995) A Synchronization Strategy for a Time-Triggered Multicluster Real-Time System. In Proceedings of the 14th IEEE Symposium on Reliable Distributed Systems, Bad Neuenahr, Germany, pp 154–161 |
| [20] | Lamport L, Melliar Smith PM (1978) Synchronizing Clocks in the Presence of Faults. Journal of the ACM, 32(1): 52–78 · Zbl 0629.68025 · doi:10.1145/2455.2457 |
| [21] | Lundelius-Welch J, Lynch N (1988) A new fault-tolerant algorithm for clock synchronization. Information and Computation 77(1):136 · Zbl 0646.68029 |
| [22] | Lamport L, Shostak R, Pease M (1982) The Byzantine Generals Problem. Advances in Ultra-Dependable Distributed Systems. Suri N, Walter CJ, Hugue MM (eds) In: IEEE computer society press · Zbl 0483.68021 |
| [23] | Mahaney SR, Schneider FB (1985) Inexact agreement: Accuracy, Precision and Graceful Degradation. 4th ACM Symposium on Principles of Distributed Computing, Minaki, Canada, pp 237–249 |
| [24] | Maier M W, Eberhardt R (2002) The Art of Systems Architecting. CRC press, Boca Raton, USA · Zbl 0914.68217 |
| [25] | Mills DL (1994) Internet Time Synchronization: The Network Time Protocol. In: Yang Z, Anthony MT (eds) Global States and Time in Distributed Systems, IEEE Computer Society Press |
| [26] | Pauli B, Meyna A, Heitmann P (1998) Reliability of Electronic Components and Control Units in Motor Vehicle Applications, Verein Deutcher Ingenieure (VDI) Reports 1415, Electronic Systems for Vehicles, pp. 1009–1024 |
| [27] | Paulitsch M, Bauer G (2000) External Clock Synchronization in the TTA. Research Report, Vienna University of Technology, real-Time Systems Group, Vienna, Austria |
| [28] | Paulitsch M, Steiner W (2003) Fault-Tolerant Clock Synchronization for Embedded Distributed Multi-Cluster Systems. In: Proceedings of the 15th Euromicro Conference on Real-Time Systems. Porto, Portugal. |
| [29] | Pease M, Shostak R, Lamport L (1980) Reaching Agreement in the Presence of Faults. Journal of the ACM, 27(2): 228–234 · Zbl 0434.68031 · doi:10.1145/322186.322188 |
| [30] | Pfeifer H, Schwier D, Henke FW (1999) Formal Verification for Time-Triggered Clock Synchronization. in Dependable Computing for Critical Applications 7. IEEE Press |
| [31] | Ramanathan P, Shin KG, Butler RW (1990) Fault-tolerant Clock Synchronization in Distributed Systems. IEEE Computer 23(10): 33–42 |
| [32] | Schedl A (1995). The Short-Term Stability of Crystal Oscillators: Experimental results. Research Report 1/95, real-Time Systems group, Vienna University of Technology, Vienna, Austria |
| [33] | Schneider FB (1986) A Paradigm for Reliable Clock Synchronization. In Proceedings of Advanced Seminar Real-Time Local Area Networks. Bandol, France: INRIA |
| [34] | Specification of the TTP/C Protocol. TTTech Computertechnik AG, Schönbrunner Strasse 7, 1040 Vienna, Austria, 1999 |
| [35] | Schwabl W (1988) The Effect of Random and Systematic Errors on Clock Synchronizatin in Distributed Systems. Technical University of Vienna, A 1040 Vienna, Treitlstrasse 3/182 |
| [36] | Schossmaier K, Weiss B (1999) An Algorithm for Fault-Tolerant Clock State and Rate Synchronization. In: Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems (SRDS), Lausanne, Switzerland, pp 36–47 |
| [37] | Schreiber FA (1994) Is Time a Real Time? An Overview of Time Ontology in Informatics. In: Halang WA, Stoyenko AD (eds) Real Time Computing, pp 283–307 |
| [38] | Srikanth TK, Toueg S (1987) Optimal clock synchronization. Journal of the ACM, 34(3): 626–645 · doi:10.1145/28869.28876 |
| [39] | Schmuck F, Cristian F (1990) Continuous Clock Amortization need not affect the Precision of a Clock Synchronization Algorithm. In: Proceedings of the ninth annual ACM symposium on principles of distributed computing, Quebec City, Quebec, Canada, pp 504–511 |
| [40] | Schedl AV (1996) Design and Simulation of Clock Synchronization in Distributed Systems. Ph D Thesis, Technische Universität Wien, Institut für Technische Informatik, Treitlstr. 1–3/182–1, 1040 Vienna, Austria |
| [41] | Schmid U (1995) Synchronized Universal Time Coordinated for Distributed Real-Time Systems. Control Engineering Practice 3(6): 877–884 · doi:10.1016/0967-0661(95)00073-4 |
| [42] | Verissimo P, Rodrigues L, Casimiro A (1997) Cesiumspray: a precise and accurate global clock service for large-scale systems. Journal of Real-Time Systems, No. 3, 12(1): 241–294. · doi:10.1023/A:1007949113722 |
| [43] | Kopetz H, Ademaj A, Hanzlik A (2004) Clock-State and Clock-Rate Correction in Fault-Tolerant Distributed Systems. The 25th IEEE International Real-Time Systems Symposium, Lisbon, Portugal · Zbl 1103.68384 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
