Fault-tolerant clock synchronization in distributed systems

Existing fault-tolerant clock synchronization algorithms are compared and contrasted. These include the following: software synchronization algorithms, such as convergence-averaging, convergence-nonaveraging, and consistency algorithms, as well as probabilistic synchronization; hardware synchronization algorithms; and hybrid synchronization. The worst-case clock skews guaranteed by representative algorithms are compared, along with other important aspects such as time, message, and cost overhead imposed by the algorithms. More recent developments such as hardware-assisted software synchronization and algorithms for synchronizing large, partially connected distributed systems are especially emphasized     

Probabilistic clock synchronization in distributed systems

Presents and analyzes a new probabilistic clock synchronization algorithm that can guarantee a much smaller bound on the clock skew than most existing algorithms. The algorithm is probabilistic in the sense that the bound on the clock skew that it guarantees has a probability of invalidity associated with it. However, the probability of invalidity may be made extremely small by transmitting a sufficient number of synchronization messages. It is shown that an upper bound on the probability of invalidity decreases exponentially with the number of synchronization messages transmitted. A closed-form expression that relates the probability of invalidity to the clock skew and the number of synchronization messages is also derived     

Proactive resource allocation for asynchronous real-time distributed systems in the presence of processor failures

We present two proactive resource allocation algorithms, RBA^*-FT and OBA-FT, for fault-tolerant asynchronous real-time distributed systems. The algorithms consider an application model where task timeliness is specified by Jensen's benefit functions and the anticipated application workload during future time intervals is described by adaptation functions. In addition, we assume that reliability functions of processors are available a priori. Given these models, our objective is to maximize aggregate task benefit and minimize aggregate missed deadline ratio in the presence of processor failures. Since determining the optimal solution is computationally intractable, the algorithms heuristically compute sub-optimal resource allocations, but in polynomial time. Experimental results reveal that RBA^*-FT and OBA-FT outperform their non-fault-tolerant counterparts in the presence of processor failures. Furthermore, RBA^*-FT performs better than OBA-FT, although OBA-FT incurs better worst-case and amortized computational costs. Finally, we observe that both algorithms robustly withstand errors in the estimation of anticipated failures.     

Monitoring distributed real-time systems

This paper emphasizes the power ofmonitoring of distributed real-time systems as a promising tool for both scientific work and practical purposes. Starting out from a number of well-known problems with today's (industrial) real-time systems, a classification of remedial monitoring applications is given. The most important features of a monitoring system suitable for such purposes are discussed and related to the current research into monitoring of (general) distributed systems. Finally, some of the resulting conceptual issues underlying our prototype VTA monitoring system—currently being under development at our department—are presented.     

Task scheduling in distributed real-time systems

An approach to the flow shop scheduling of the computation process in distributed realtime systems is considered. This approach is based on the concept of a solvable class of systems for which simple optimal scheduling algorithms exist.     

Static analysis of real-time distributed systems

A static analysis for reasoning about the temporal behaviors of programs in real-time distributed programming languages is proposed. The analysis is based on the action set semantics using the pure maximal parallelism model. It is shown how to specify and verify various timing properties of real-time programs. The approach provides only an approximate timing behavior, because the state information is ignored. However, many interesting properties such as parallel actions, deadlocks, livelocks, terminations, temporal errors, and failures, can be identified. Furthermore, the approach is compositional and thus makes it possible to reason about the timing properties incrementally. The method not only leads to efficient algorithms for the static analysis of CSP programs but also applies to many other languages     

实时性分布嵌入式系统设计

分布嵌入式系统的应用通常具有实时性要求,其实时性需要从任务调度、通信协议、调用接口和嵌入式操作系统四个方面得到支持。采用两阶段调度策略既可以保证调用的透明性,又可以简化任务调度算法;基于优先级的线路竞争算法可以改进以太网使其符合实时性要求;采用微型Java虚拟机作为分布式中间件可以为系统调用接口提供一个统一的支持平台。     

Fundamental issues in testing distributed real-time systems

This paper examines the fundamental problems that one faces when testing a distributed, hard real-time system. It specifically identifies the influences of the distributedness and of the real-time requirements of the systems considered. We show how the usual problems of testing become more difficult, and which additional problems are introduced, because of these additional system characteristics.We identify six such fundamental problems: Organization, Observability, Reproducibility, Host/Target Approach, Environment Simulation, and Representativity. These, as well as their interrelations, are presented in a general framework that is independent of a particular system architecture or application. This framework could serve as a starting point for all activities geared towards a particular system architecture or a specific application.As an example, we illustrate how these test problems have been handled when developing a test methodology for the distributed real-time system MARS. Finally, the additional issues of test data generation and test result analysis are briefly discussed.     

Language constructs for real-time distributed systems

The paper observes syntactic and semantic requirements for a language for programming real-time distributed systems. A proposal for language features that meet these requirements is offered, and the features are applied to an example.     

Synchronized UTC for distributed real-time systems

We present a novel technique for establishing a highly accurate global time in fault-tolerant, large-scale distributed real-time systems. Unlike the usual clock synchronization approaches, our clock validation technique provides a precise system time that also relates to an external time standard like UTC with high accuracy. The underlying idea is to validate time information of external time sources like GPS-receivers against a global time maintained by the local clocks in the system. As an example, a promising interval-based clock validation algorithm ICV that exhibits excellent fault-tolerance properties is outlined and analyzed. It requires only a few high-accurate external time sources and provides each node with the actual accuracy of its clock.     

Virtual machines for distributed real-time systems

The steady increase in raw computing power of the processors commonly adopted for distributed real-time systems leads to the opportunity of hosting diverse classes of tasks on the same hardware, for example process control tasks, network protocol stacks and man–machine interfaces.This paper describes how virtualization techniques can be used to concurrently run multiple operating systems on the same physical machine, although they are kept fully separated from the security and execution timing points of view, and still have them exhibit acceptable real-time execution characteristics.With respect to competing approaches, the main advantages of this method are that it requires little or no modifications to the operating systems it hosts, along with a better modularity and clarity of design.     

Model continuity in the design of dynamic distributed real-time systems

Model continuity refers to the ability to transition as much as possible a model specification through the stages of a development process. In this paper, the authors show how a modeling and simulation environment, based on the discrete event system specification formalism, can support model continuity in the design of dynamic distributed real-time systems. In designing such systems, the authors restrict such continuity to the models that implement the system's real-time control and dynamic reconfiguration. The proposed methodology supports systematic modeling of dynamic systems and adopts simulation-based tests for distributed real-time software. Model continuity is emphasized during the entire process of software development $the control models of a dynamic distributed real-time system can be designed, analyzed, and tested by simulation methods, and then smoothly transitioned from simulation to distributed execution. A dynamic team formation distributed robotic system is presented as an example to show how model continuity methodology effectively manages the complexity of developing and testing the control software for this system.     

Efficiently tolerating failures in asynchronous real-time distributed systems

We present a proactive resource allocation algorithm, called BEA, for fault-tolerant asynchronous real-time distributed systems. BEA considers an application model where trans-node application timeliness requirements are expressed using benefit functions, and anticipated workload during future time intervals are expressed using adaptation functions. Furthermore, BEA considers an adaptation model where subtasks of application tasks are replicated at run-time for tolerating failures as well as for sharing workload increases. Given such models, the objective of the algorithm is to maximize the aggregate real-time benefit and the ability to tolerate host failures during the time window of adaptation functions. Since determining the optimal solution is computationally intractable, BEA heuristically computes suboptimal resource allocations in polynomial-time. We show that BEA can achieve almost the same fault-tolerance ability as full replication, and accrue most of real-time benefit that full replication can accrue. In the meanwhile, BEA requires much fewer replicas than full replication, and hence is cost effective.     

Maintaining data temporal consistency in distributed real-time systems

Previous works on maintaining temporal consistency of real-time data objects mainly focuses on real-time database systems in which the transmission delays (jitters) of update jobs are simply ignored. However, this assumption does not hold in distributed real-time systems where the jitters of the update jobs can be large and change unpredictably with time. In this paper, we examine the design problems when the More-Less (ML) approach (Xiong and Ramamritham in Proc. of the IEEE real-time systems symposium 1999; IEEE Trans Comput 53:567?C583, 2004), known to be an efficient scheme for maintaining temporal consistency of real-time data objects, is applied in a distributed real-time system environment. We propose two new extensions based on ML, called Jitter-based More-Less (JB-ML) and Statistical Jitter-based More-Less (SJB-ML) to address the jitter problems. JB-ML assumes that in the system the jitter is a constant for each update task, and it provides a deterministic guarantee in temporal consistency of the real-time data objects. SJB-ML further relaxes this restriction and provides a statistical guarantee based on the given QoS requirements of the real-time data objects. We demonstrate through extensive simulation experiments that both JB-ML and SJB-ML are effective approaches and they significantly outperform ML in terms of improving schedulability.     

Concurrency control in mobile distributed real-time database systems

This paper presents DMVOCC-2PLV (Distributed Multiversion Optimistic Concurrency Control with Two-Phase Local Validation) protocol for processing mobile distributed real-time transactions in mobile broadcast environments. In DMVOCC-2PLV protocol, transaction validation is performed at two levels: local validation and global validation. Local validation of transactions is performed in two phases: local pre-validation and local final validation. At the MHs (Mobile Hosts), all mobile transactions perform local pre-validation of transactions by using a backward validation mechanism. The local pre-validation process is carried out against committed transactions at the server in the last broadcast cycle. Such an early data conflict detection feature can save processing and communication resources. Transactions that survive in local pre-validation must be submitted to the server for local final validation. In global validation distributed update transactions have to check to ensure distributed serializability in all participants. The protocol can eliminate conflicts between mobile read-only and mobile update transactions, and resolve data conflicts flexibly using multiversion dynamic adjustment of serialization order to avoid unnecessary restarts of transactions. Mobile read-only transactions can be committed with no-blocking, and respond time of mobile read-only transactions is greatly reduced. The tolerance of mobile transactions of disconnections from the broadcast channel is increased. The results of simulation experiment show that the new protocol proposed offers better performance in terms of miss rate, restart rate, commit rate and throughput.     

Performance estimation for real-time distributed embedded systems

Many embedded computing systems are distributed systems: communicating processes executing on several CPUs/ASICs. This paper describes a performance analysis algorithm for a set of tasks executing on a heterogeneous distributed system. Tight bounds are essential to the synthesis and verification of application-specific distributed systems, such as embedded computing systems. Our bounding algorithms are valid for a general problem model: The system can contain several tasks with hard real-time deadlines and different periods; each task is partitioned into a set of processes related by data dependencies. The periods of tasks and the computation times of processes are not necessarily constant and can be specified by a lower bound and an upper bound. Such a model requires a more sophisticated algorithm, but leads to more accurate results than previous work. Our algorithm both provides tighter bounds and is faster than previous methods     

Modular abstractions for verifying real-time distributed systems

In this work we present a verification methodology for real-time distributed systems, based on their modular decomposition into processes. Given a distributed system, each of its components is reduced by abstracting away from details that are irrelevant for the required specification. The abstract components are then composed to form an abstract system to which a model checking procedure is applied. The abstraction relation and the specification language guarantee that if the abstract system satisfies a specification, then the original system satisfies it as well.The specification languageRTL is a branching-time version of the real-time temporal logicTPTL presented in Alur and Henzinger [1]. Its model checking is linear in the size of the system and exponential in the size of the formula. Two notions of abstraction for real-time systems are introduced, each preserving a sublanguage ofRTL.     

Modeling distributed real-time systems with MAST 2

Switched networks have an increasingly important role in real-time communications. The IEEE Ethernet standards have defined prioritized traffic (802.1p) and other QoS mechanisms (802.1q). The Avionics Full-Duplex Switched Ethernet (AFDX) standard defines a hard real-time network based on switched Ethernet. Clock synchronization is also an important service in some real-time distributed systems because it allows a global notion of time for event timing and timing requirements. In the process of defining the new MAST 2 model, clock synchronization modeling capabilities have been added, and the network elements have been enhanced to include switches and routers. This paper introduces the schedulability model that will enable an automatic schedulability analysis of a distributed application using switched networks and clock synchronization mechanisms.     

Runtime monitoring of timing constraints in distributed real-time systems

Embedded real-time systems often operate under strict timing and dependability constraints. To ensure responsiveness, these systems must be able to provide the expected services in a timely manner even in the presence of faults. In this paper, we describe a run-time environment for monitoring of timing constraints in distributed real-time systems. In particular, we focus on the problem of detecting violations of timing assertions in an environment in which the real-time tasks run on multiple processors, and timing constraints can be either inter-processor or intra-processor constraints. Constraint violations are detected at the earliest possible time by deriving and checking intermediate constraints from the user-specified constraints. If the violations must be detected as early as possible, then the problem of minimizing the number of messages to be exchanged between the processors becomes intractable. We characterize a sub-class of timing constraints that occur commonly in distributed real-time systems and whose message requirements can be minimized. We also take into account the drift among the various processor clocks when detecting a violation of a timing assertion. Finally, we describe a prototype implementation of a distributed run-time monitor.This work was done while the first two authors were at the IBM T.J. Watson Research Center.Supported in part by the Office of Naval Research under grant number N00014-89-J-1040 and by National Science Foundation under grant number CCR-9200858.     

Testing real-time systems using genetic algorithms

The development of real-time systems is an essential industrial activity whose importance is increasing. The most important analytical method to assure the quality of real-time systems is dynamic testing. Testing is the only method which examines the actual run-time behaviour of real-time software, based on an execution in the real application environment. Dynamic aspects like the duration of computations, the memory actually needed, or the synchronization of parallel processes are of major importance for the correct function of real-time systems and have to be tested. A comprehensive investigation of existing software test methods shows that they mostly concentrate on testing for functional correctness. They are not suited for an examination of temporal correctness which is essential to real-time systems. Very small systems show a wide range of different execution times. Therefore, existing test procedures must be supplemented by new methods, which concentrate on determining whether the system violates its specified timing constraints. In general, this means that outputs are produced too early or their computation takes too long. The task of the tester is to find the inputs with the longest or shortest execution times to check whether they produce a temporal error. If the search for such inputs is interpreted as a problem of optimization, genetic algorithms can be used to find the inputs with the longest or shortest execution times automatically. The fitness function is the execution time measured in processor cycles. Experiments using genetic algorithms on a number of programs with up to 1511 LOC and 843 integer input parameters have successfully identified new longer and shorter paths than had been found using random testing or systematic testing. Genetic algorithms are able therefore to check large programs and they show considerable promise in establishing the validity of the temporal behaviour of real-time software.