A Synchronization Strategy for a Time-Triggered

Multicluster Real-Time System

Hermann Kopetz
Andreas Kr?ger
Dietmar Millinger
Anton Schedl

Institut f?r Technische Informatik
Technische Universit?t Wien, Austria
email: [email protected]

Abstract
The provision of a system-wide global time base with a good precision and sufficient accuracy is a fundamental prerequisite for the design of a multicluster distributed real-time system. In this paper we investigate the issues of clock synchronization in a multicluster system, where every node can have a different oscillator. Based on the parameter of a typical automotive distributed system we show that a precision and accuracy in the msecond range is achievable without undue effort.

Key Words: Clock Synchonization, Distributed Systems, Real Time, Global Time, Fault Tolerance

Introduction

At present, the design of large real-time distributed systems is more an art than an engineering endeavor. Recent spectacular failures of some of these systems underscore our point [Wayt Gibbs 1994]. One key reason for the failures of these large systems is the complexity in the synchronization and coordination of the concurrently executing dynamically scheduled real-time tasks. It is very difficult to sufficiently test or to reason formally about [Rushby 1993] these data dependent dynamic control structures. The "random" occurrence of non reproducible unexpected and untested synchronization problems during the operation of these systems is a main cause for the encountered difficulties.

The situation is more encouraging if we look at the field of experience with safety critical real time systems. In most of these systems the time-triggered control structure is data independent and therefore static. It is thus possible to cleanly separate the validation of the

data transformations, i.e., the execution of sequential tasks, from the validation of the static control structure. At present, most of these time-triggered safety critical systems are relatively small and confined to a single cluster. It is thus a research challenge to extend the timetriggered technology to the design of large multicluster real-time systems.

A necessary service of a time-triggered architecture is the provision of a system-wide fault- tolerant global time base of sufficient precision. In multicluster systems--and sometimes even in a single cluster system--it cannot be assumed that all nodes will contain oscillators with the same nominal frequency. The design of a synchronization system within a set of clusters that will generate a uniform time base with a precision in the msec range despite the fact that each node may have an oscillator with a different nominal frequency, is an interesting research challenge.

The objectives of this paper are the presentation of a fault-tolerant synchronization strategy for a multicluster real-time system, where no assumptions are made about the base oscillator frequency in each node, and the integration of the internal and external clock synchronization into a single coherent time base.

The paper is organized as follows. In the next section we explain our architectural assumptions and introduce a uniform format for the representation of time in a multicluster real-time system. Section three focuses on the problem of internal synchronization and describes a macrotick generation logic that allows the generation of a global time base within the physical second standard from an arbitrary oscillator frequency. Section four is devoted to the topic of external synchronization and discusses the functions of a time-gateway. In section five we analyze the achievable precision and accuracy in a