Arbitration-free synchronization

Implementing traditional forms of multiprocess synchronization requires a hardware arbiter. Here, we consider what kind of synchronization is achievable without arbitration. Several kinds of simple arbiter-free registers are defined and shown to have equal power, and the class of synchronization problems solvable with such registers is characterized. More powerful forms of arbiter-free communication primitives are described. However, the problem of characterizing the most general form of arbiter-free synchronization remains unsolved.Received: November 2001, Accepted: July 2002,     

A standard model for multimedia synchronization: PREMO synchronization objects

This paper describes an event-based synchronization mechanism, which is at the core of the inter-media synchronization in the upcoming standard for multimedia presentation, PREMO. The synchronization mechanism of PREMO is a powerful tool, based on a small number of concepts, and on cooperation among active objects, and represents a synthesis of various synchronization models described in the literature. This model can serve as a basis for the implementation of complex synchronization patterns in multimedia presentations, both purely event-based, as well as time-based.     

Low-cost clock synchronization

Summary We show how synchronized clocks can be realized in a distributed system as a byproduct of a common communication paradigm where processors periodically perform broadcasts. Our approach decouples theprecision concern of clock synchronization—limiting how much correct clocks can differ from each other—from theaccuracy concern—limiting the rate at which any correct clock may drift from real time. Given a system that guarantees only precision, we develop a protocol whereby high accuracy can be achieved on demand. In this manner, the lazy protocol we obtain incurs the cost of high accuracy only when needed while keeping the basic synchronization procedure extremely simple and cheap. Rogério Drummond is Associate Professor of Computer Science at the Universidade de Campinas (Unicamp), Brazil. He received his Ph.D. in computer science from Cornell University in 1986. He has previously worked on distributed fault-tolerant computing, such as the present paper. Currently, he heads the A_HAND project which aims to provide an object-oriented distributed programming environment for the development of very large software systems. Özalp Babaolu is Professor of Computer Science at the University of Bologna, Italy. His research interests include distributed algorithms, fault tolerance and parallel computing. He received a BS in electrical engineering from George Washington University, Washington, D.C. in 1976. From the University of California, Berkeley, he received a MS in 1977 and a Ph.D. in 1981, both in computer science. While at Berkeley, he designed and implemented the virtual memory extensions to BSD Unix. From 1981 to 1987 he was on the faculty at the Department of Computer Science, Cornell University.Partial support for this work was provided by the National Science Foundation under Grant DCR-86-01864, AT&T under a Foundation Grant, the Commission of the European Communities under the ESPRIT Programme Basic Research Action Number 3092 (Predictably Dependable Computing Systems) and the Italian Ministry of University and Research. Drummond was partially supported through a Fellowship from the CAPES Agency of the Government of Brazil     

Probabilistic clock synchronization

A probabilistic method is proposed for reading remote clocks in distributed systems subject to unbounded random communication delays. The method can achieve clock synchronization precisions superior to those attainable by previously published clock synchronization algorithms. Its use is illustrated by presenting a time service which maintains externally (and hence, internally) synchronized clocks in the presence of process, communication and clock failures. Flaviu Cristian is a computer scientist at the IBM Almaden Research Center in San Jose, California. He received his PhD from the University of Grenoble, France, in 1979. After carrying out research in operating systems and programming methodology in France, and working on the specification, design, and verification of fault-tolerant programs in England, he joined IBM in 1982. Since then he has worked in the area of fault-tolerant distributed protocols and systems. He has participated in the design and implementation of a highly available system prototype at the Almaden Research Center and has reviewed and consulted for several fault-tolerant distributed system designs, both in Europe and in the American divisions of IBM. He is now a technical leader in the design of a new U.S. Air Traffic Control System which must satisfy very stringent availability requirements.     

Cellular automata synchronization

The first part of this paper deals with the Firing Squad Synchronization problem extended to networks however connected. A new class of configurations called “flower graphs” is presented whose synchronization is useful to reduce synchronization time for any graph. The second part investigates the lower bounds for synchronization time from a theoretical point of view. Results are obtained that are valid for several classes of graphs.     

Hypercube clock synchronization

Algorithms for synchronizing the times and frequencies of the clocks of Intel and Ncube hypercube multiprocessors are presented. Bounds for the error in estimating clock offsets and frequencies are formulated in terms of the clock read error and message transmission time. Clock and communication performance of the Ncube and Intel hypercubes are analysed, and performance of the synchronization algorithms is presented.     

Cellular automata synchronization

The first part of this paper deals with the Firing Squad Synchronization problem extended to networks however connected. A new class of configurations called “flower graphs” is presented whose synchronization is useful to reduce synchronization time for any graph. The second part investigates the lower bounds for synchronization time from a theoretical point of view. Results are obtained that are valid for several classes of graphs.     

Functional density synchronization

Estimating an overall density function from repeated observations on each of a sample of independent subjects or experimental units is of interest. An example is provided by biodemographic studies, where one observes age-at-death for several cohorts of flies. Cohorts are kept in separate cages, which form the experimental units. Time variation then is likely to exist between the cohort densities and hazard rates due to cage effects on aging. Given the densities of age-at-death for the individual cohorts, one aims to obtain an estimate for the underlying overall density and hazard rate. In microarray gene expression experiments, similar problems arise when addressing the need for normalization of probe-level data from different arrays. Conventional methods, such as the cross-sectional average density, ignore time variation and hence are often not representative for such data. We view densities as functional data and model individual densities as warped versions of an underlying overall density, where the observed densities are assumed to be realizations of an underlying stochastic process. Quantile-synchronized distribution functions are obtained from an inverse warping mapping, based on quantile synchronization, leading to quantile-synchronized density and hazard functions. Kernel type smoothing methods with plug-in bandwidth selection can be used for estimating the components of the model. Asymptotic properties of the synchronized density estimates are derived. Simulation results show that functional density synchronization is often advantageous when compared to conventional density averaging or simple time-shift warping. Our approach complements previous quantile normalization methods used for microarray expression data and is illustrated with both longevity data obtained for 54 cohorts of mexflies (Mexican fruit flies) and gene expression data of the Ts1Cje mouse study for Down syndrome.     

Gradient clock synchronization

We introduce the distributed gradientclock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their hardware clocks and message exchanges, and the goal is to synchronize the nodes' logical clocks as closely as possible, while satisfying certain validity conditions. The new feature of gradient clock synchronization GCS for short) is to require that the skew between any two nodesy' logical clocks be bounded by a nondecreasing function of the uncertainty in message delay (call this the distance) between the two nodes, and other network parameters. That is, we require nearby nodes to be closely synchronized, and allow faraway nodes to be more loosely synchronized. We contrast GCS with traditional clock synchronization, and discuss several practical motivations for GCS, mostly arising in sensor and ad-hoc networks. Our main result is that the worst case clock skew between two nodes at distance d or less from each other is Ω(d + , where D is the diameter of the network. This means that clock synchronization is not a localproperty, in the sense that the clock skew between two nodes depends not only on the distance between the nodes, but also on the size of the network. Our lower bound implies, for example, that the TDMA protocol with a fixed slot granularity will fail as the network grows, even if the maximum degree of each node stays constant.     

复杂网络的脉冲同步

研究了具有有界耦合函数的不确定复杂动态网络的脉冲同步问题．根据脉冲控制的概念和脉冲微分方程的稳定性理论,我们利用一个灵活有效的脉冲控制实现了复杂动态网络的脉冲同步．最后,通过对混沌系统做网络节点的动态网络的数字模拟,验证了我们提出的脉冲控制方案的有效性和实用性．     

Control of chaos and synchronization

This note presents a brief introduction in the field of control of chaos and chaos synchronization. It is argued that both subjects, being very popular among physicists, also deserve to be studied from a control perspective.     

On the synchronization of traces

Trace theory has been developed to describe the behavior of concurrent systems. Synchronization of traces is of special interest for a modular approach. We characterize those trace monoids for which synchronization can be described locally.     

Julia集的广义同步

研究了两个不同的Julia集耦合实现广义同步的问题. 不同于以往对Julia集的研究仅限于对一个独立的Julia集的性质, 制图等方面的讨论, 本文提出了两个不同的Julia集广义同步的思想, 并以经典的复二次多项式系统z_n+1 = z²_n+c为例, 分别采用线性和非线性耦合的方法对该系统不同参数的Julia集进行了广义同步. 仿真结果表明了方法的有效性.     

The synchronization of independent processes

Summary This paper considers the problem of programming a multiple process system so that it continues to operate despite the failure of individual processes. A powerful synchronizing primitive is defined, and it is used to solve some sample problems. An algorithm is then given which implements this primitive under very weak assumptions about the nature of interprocess communication, and a careful informal proof of its correctness is given.     

同步精度稳定的多跳无线传感器网络时间同步算法

对无线传感器网络时间同步精度稳定性进行了研究，给出了OTSP算法中影响多跳同步精度的因素，在此基础上提出了一种新的同步精度稳定的算法。该算法估算出了不同节点间的晶振频率偏差，并使得多跳网络中的每个节点都能精确地同步到时间基准节点。实验结果证明该算法在同步精度的稳定性方面优于OTSP算法。