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     

Building a global clock for observing computations in distributed memory parallel computers

A common time reference (i.e. global clock) is needed for observing the behavior of a distributed algorithm on a distributed computing system. The paper presents a pragmatic algorithm to build a global clock on any distributed system, which is optimal for homogeneous distributed memory parallel computers (DMPCs). In order to observe and sort concurrent events in common DMPCs, we need a global clock with a resolution finer than the message transfer time variance, which is better than what deterministic and fault-tolerant algorithms can obtain. Thus a statistical method is chosen as a building block to derive an original algorithm valid for any topology. Its main originality over related approaches is to cope with the problem of clock granularity in computing frequency offsets between local clocks to achieve a resolution comparable with the resolution of the physical clocks. This algorithm is particularly well suited for debugging distributed algorithms by means of trace recordings because after its acquisition step it does not induce message overhead: the perturbation induced on the execution remains as small as possible. It has been implemented on various DMPCs: Intel iPSC/2 hypercube and Paragon XP/S, Transputer-based networks and Sun networks, so we can provide some data about its behavior and performances on these DMPCs.     

Detecting global predicates in distributed systems with clocks

Summary. This paper proposes a framework for detecting global state predicates in systems of processes with approximately-synchronized real-time clocks. Timestamps from these clocks are used to define two orderings on events: “definitely occurred before” and “possibly occurred before”. These orderings lead naturally to definitions of 3 distinct detection modalities, i.e., 3 meanings of “predicate held during a computation”, namely: (“ possibly held”), (“ definitely held”), and (“ definitely held in a specific global state”). This paper defines these modalities and gives efficient algorithms for detecting them. The algorithms are based on algorithms of Garg and Waldecker, Alagar and Venkatesan, Cooper and Marzullo, and Fromentin and Raynal. Complexity analysis shows that under reasonable assumptions, these real-time-clock-based detection algorithms are less expensive than detection algorithms based on Lamport's happened-before ordering. Sample applications are given to illustrate the benefits of this approach. Received: January 1999 / Accepted: November 1999     

Mapping MMOFPS over heterogeneous distributed systems

This paper evaluates the effects on performance of taking the heterogeneity of nodes into account, in terms of number of cores, when MMOFPS (Massively Multiplayer Online First Person Shooter) game services are distributed. Two mapping strategies, Non_Heterogeneity_aware and Heterogeneity_aware, are integrated in a system, called OnDeGaS (On Demand Game Service), which is a hybrid between Client-Server and P2P topologies. Through simulation, we show that the Heterogeneity_aware mechanism has more impact in communication costs, but it is more efficient in exploiting the nodes of the P2P area, as it maps players faster and it creates less computing zones with latency values under the acceptable threshold for MMOFPS games.     

Computing global functions in asynchronous distributed systems with perfect failure detectors

A Global Data is a vector with one entry per process. Each entry must be filled with an appropriate value provided by the corresponding process. Several distributed computing problems amount to compute a function on a global data. This paper proposes a protocol to solve such problems in the context of asynchronous distributed systems where processes may fail by crashing. The main problem that has to be solved lies in computing the global data and in providing each noncrashed process with a copy of it, despite the possible crash of some processes. To be consistent, the global data must contain, at least, all the values provided by the processes that do not crash. This defines the Global Data Computation (GDC) problem. To solve this problem, processes execute a sequence of asynchronous rounds during which they construct, in a decentralized way, the value of the global data and eventually each process gets a copy of it. To cope with process crashes, the protocol uses a perfect failure detector. The proposed protocol has been designed to be time efficient: it allows early decision. Let t be the maximum number of processes that may crash, t相似文献   

Testing distributed real-time systems in the presence of inaccurate clock synchronizations

This article deals with testing distributed real-time systems. More precisely, we propose: (1) a model for describing the specification of the implementation under test, (2) a distributed architecture of the test system (TS), (3) an approach for coordinating the testers which constitute the TS, and (4) a procedure for deriving automatically the test sequence of each tester from a global test sequence. In comparison with a very recent work, the proposed test method has the following important advantage: the clocks used by the different testers are not assumed perfectly synchronized. Rather, we assume more realistically that each clock is synchronized with a reference clock with a given (nonnull) inaccuracy. This advantage is very relevant if, for example, the testers communicate through the Internet.     

Model checking LTL with regular valuations for pushdown systems

Recent works have proposed pushdown systems as a tool for analyzing programs with (recursive) procedures, and the model-checking problem for LTL has received special attention. However, all these works impose a strong restriction on the possible valuations of atomic propositions: whether a configuration of the pushdown system satisfies an atomic proposition or not can only depend on the current control state of the pushdown automaton and on its topmost stack symbol. In this paper we consider LTL with regular valuations: the set of configurations satisfying an atomic proposition can be an arbitrary regular language. The model-checking problem is solved via two different techniques, with an eye on efficiency. The resulting algorithms are polynomial in certain measures of the problem which are usually small, but can be exponential in the size of the problem instance. However, we show that this exponential blowup is inevitable. The extension to regular valuations allows to model problems in different areas; for instance, we show an application to the analysis of systems with checkpoints. We claim that our model-checking algorithms provide a general, unifying and efficient framework for solving them.     

Mining frequent itemsets over distributed data streams by continuously maintaining a global synopsis

Mining frequent itemsets over data streams has attracted much research attention in recent years. In the past, we had developed a hash-based approach for mining frequent itemsets over a single data stream. In this paper, we extend that approach to mine global frequent itemsets from a collection of data streams distributed at distinct remote sites. To speed up the mining process, we make the first attempt to address a new problem on continuously maintaining a global synopsis for the union of all the distributed streams. The mining results therefore can be yielded on demand by directly processing the maintained global synopsis. Instead of collecting and processing all the data in a central server, which may waste the computation resources of remote sites, distributed computations over the data streams are performed. A distributed computation framework is proposed in this paper, including two communication strategies and one merging operation. These communication strategies are designed according to an accuracy guarantee of the mining results, determining when and what the remote sites should transmit to the central server (named coordinator). On the other hand, the merging operation is exploited to merge the information received from the remote sites into the global synopsis maintained at the coordinator. By the strategies and operation, the goal of continuously maintaining the global synopsis can be achieved. Rooted in the continuously maintained global synopsis, we propose a mining algorithm for finding global frequent itemsets. Moreover, the correctness guarantees of the communication strategies and merging operation, and the accuracy guarantee analysis of the mining algorithm are provided. Finally, a series of experiments on synthetic datasets and a real dataset are performed to show the effectiveness and efficiency of the distributed computation framework.     

Model-based testing of global properties on large-scale distributed systems

ContextLarge-scale distributed systems are becoming commonplace with the large popularity of peer-to-peer and cloud computing. The increasing importance of these systems contrasts with the lack of integrated solutions to build trustworthy software. A key concern of any large-scale distributed system is the validation of global properties, which cannot be evaluated on a single node. Thus, it is necessary to gather data from distributed nodes and to aggregate these data into a global view. This turns out to be very challenging because of the system’s dynamism that imposes very frequent changes in local values that affect global properties. This implies that the global view has to be frequently updated to ensure an accurate validation of global properties.ObjectiveIn this paper, we present a model-based approach to define a dynamic oracle for checking global properties. Our objective is to abstract relevant aspects of such systems into models. These models are updated at runtime, by monitoring the corresponding distributed system.MethodWe conduce real-scale experimental validation to evaluate the ability of our approach to check global properties. In this validation, we apply our approach to test two open-source implementations of distributed hash tables. The experiments are deployed on two clusters of 32 nodes.ResultsThe experiments reveal an important defect on one implementation and show clear performance differences between the two implementations. The defect would not be detected without a global view of the system.ConclusionTesting global properties on distributed software consists of gathering data from different nodes and building a global view of the system, where properties are validated. This process requires a distributed test architecture and tools for representing and validating global properties. Model-based techniques are an expressive mean for building oracles that validate global properties on distributed systems.     

The imposition of protocols over open distributed systems

In order to facilitate enforcement of protocols, an architecture for distributed systems is introduced under which all interactions between objects are governed by an explicit and strictly enforced set of rules, called the law of the system. This law is global in the sense that all the objects of the system are made to obey it, but the maintenance of the law and its enforcement are performed locally, at each object (or node). The term law is used to emphasized that it not only provides the specification of protocols, but actually governs the system by enforcing them. In other words, under this architecture a protocol can be established simply by writing it into the law of a system, without having to worry about the programs that drive the various objects that might populate that system. The law, then, is the enforced specification of protocols. It is shown that various familiar protocols can be established under this architecture. A technique for online distributed updating of the global law of a system is presented     

Fixed-time distributed optimization for multi-agent systems with external disturbances over directed networks

This article considers the fixed-time distributed optimization problem of multi-agent systems with external disturbances, in which the global optimization objective is a convex combination of local objective functions. To solve this issue, a directed communication network is carefully designed, and an integral sliding mode control protocol is proposed based on the gradient of global objective function first. Moreover, two distributed optimal protocols are designed by using the gradient and the Hessian matrix of local objective function, respectively. By employing Lyapunov stability theory, graph theory, convex analysis, and inequality techniques, we prove that all proposed protocols can make agents achieve consensus and converge accurately to the optimal solution of the considered problem in some fixed-time intervals. Finally, some numerical simulations are given to verify the feasibility of the theoretical results.     

Event-triggered distributed state estimation for a class of time-varying systems over sensor networks with redundant channels

This paper is concerned with the distributed state estimation problem for a class of time-varying systems over sensor networks. An event-triggered communication scheme is utilized to save the constrained computation resource and network bandwidth while preserving the desired performance. The measurements on each node are transmitted to the estimators only when a certain triggering condition is satisfied. Moreover, in order to improve the reliability of data transmission services, we exploit redundant communication channels during the transmission process. The purpose of this paper is to design a set of time-varying state estimators such that the dynamics of the state estimation error satisfies the average H_∞ performance constraints. The specific gains of the estimator can be obtained by calculating a series of recursive linear matrix inequalities (RLMIs). Finally, a simulation example is presented to show the effectiveness of the state estimation method proposed in this paper.     

Event‐triggered MPC design for distributed systems toward global performance

This paper studies the coordination control problem of stabilizing large‐scale dynamically coupled systems via a novel event‐triggered distributed model predictive control (DMPC) approach. In order to achieve global performance, certain constraints relevant to the triggering instant are imposed on the DMPC optimization problem, and triggering mechanisms are designed by taking into account coupling influences. Specifically, the triggering conditions derived from the feasibility and stability analysis are based on the local subsystem state and the information received from its neighbors. Based on these triggering mechanisms, the event‐triggered DMPC algorithm is built, and a dual‐mode strategy is adopted. As a result, the controllers solve the optimization problem and coordinate with each other asynchronously, which reduces the amount of communication and lowers the frequency of controller updates while achieving global performance. The recursive feasibility of the proposed event‐triggered DMPC algorithm is proved, and sufficient parameter conditions about the prediction horizon and the triggering threshold are established. It shows that the system state can be gradually driven into the terminal set under the proposed strategy. Finally, an academic example and a realistic simulation problem to the water level of a 4‐tank system are provided to verify the effectiveness of the proposed algorithm.     

On coupling multiple systems with a global buffer

We conduct a performance study of coupling multiple systems with a global buffer, and present several results obtained from a multiple-system simulator. This simulator has been run against three workloads, and the coupled system behavior with these three different inputs is studied. Several statistics, including those on local and global buffer hits, page writes to the global buffer, cross-invalidations, and castouts are reported. Their relationship to the degree of data skew is explored. Moreover, in addition to the update-caching approach, a design alternative for the use of a global buffer, namely read-caching, is explored. In read-caching, not only updated pages but also pages read by each node are kept in the global buffer, thereby facilitating other nodes access to the same pages at the cost of a higher global buffer usage. Also investigated is the case of no-caching, i.e., without using a global buffer. Several simulation results are presented and analyzed     

Control of complex distributed systems with distributed intelligent agents

Control of spatially distributed systems is a challenging problem because of their complex nature, nonlinearity, and generally high order. The lack of accurate and computationally efficient model-based techniques for large, spatially distributed systems leads to challenges in controlling the system. Agent-based control structures provide a powerful tool to manage distributed systems by utilizing (organizing) local and global information obtained from the system. A hierarchical, agent-based system with local and global controller agents is developed to control networks of interconnected chemical reactors (CSTRs). The global controller agent dynamically updates local controller agent’s objectives as the reactor network conditions change. One challenge posed is control of the spatial distribution of autocatalytic species in a network of reactors hosting multiple species. The multi-agent control system is able to intelligently manipulate the network flow rates such that the desired spatial distribution of species is achieved. Furthermore, the robustness and flexibility of the agent-based control system is illustrated through examples of disturbance rejection and scalability with respect to the size of the network.     

Finding consistent global checkpoints in a distributed computation

Consistent global checkpoints have many uses in distributed computations. A central question in applications that use consistent global checkpoints is to determine whether a consistent global checkpoint that includes a given set of local checkpoints can exist. Netzer and Xu (1995) presented the necessary and sufficient conditions under which such a consistent global checkpoint can exist, but they did not explore what checkpoints could be constructed. In this paper, we prove exactly which local checkpoints can be used for constructing such consistent global checkpoints. We illustrate the use of our results with a simple and elegant algorithm to enumerate all such consistent global checkpoints     

Flatness-based feedforward control for parabolic distributed parameter systems with distributed control

This paper deals with distributed parameter systems being described by inhomogeneous parabolic partial differential equations in one space dimension with a distributed control. The distributed control is presented by the right part of an equation, i.e. the source function. The source function can depend on the time as well as spatial variable. The approach for design of a feedforward control for the purpose of exact output tracking is presented. The design of the feedforward control is based on the examination of inverse system dynamics. The proposed technique utilizes the method of the variables separation and the representation of a solution by the power series in the time domain. Some examples and numerical simulations are included and demonstrate the efficiency of the proposed approach for developing the feedforward control.