Self-stabilizing 2^m-clock for unidirectional rings of odd size

Summary. In this paper, we propose a self-stabilizing K-clock protocol for unidirectional rings with odd size, where and m is any positive integer. Besides the variable for maintaining the clock, the proposed protocol only requires one additional bit. The worst-case stabilizing time is ), where n is the ring size. Received: July 1998 / Accepted: January 1999     

Phase synchronization on asynchronous uniform rings with odd size

This paper proposes a self-stabilizing phase synchronization protocol for uniform rings with an odd size. Nodes in the ring work asynchronously and proceed in a cyclic sequence of K phases, where K is even. The phase values of all the nodes are required to be no more than one apart. A system state which satisfies the requirement is therefore called a legitimate state. The proposed protocol guarantees that no matter with which initial state the system may start, the ring stabilizes eventually at a state after which the closure property on the legitimate state holds. Phase values should never go backward. The closure property on the legitimate states commonly used in previous works on self-stabilization cannot capture this requirement. This paper defines two terms, legitimate step and illegitimate step, to address this issue. An execution step that brings the ring from a legitimate state to another legitimate state in a way that the phase values of the nodes only advance is called a legitimate step. An execution step that observes the closure property on the legitimate states but makes some phase values go backward is modeled as an illegitimate step. It is shown that, for the proposed protocol, only a finite number of illegitimate steps are possible. After all possible illegitimate steps have occurred, the closure property on the legitimate steps holds     

Alternators in read/write atomicity

The alternator problem requires that in legitimate states no two neighboring processes are enabled and between two executions of a process, its neighbors execute at least once. In this paper, we present a solution for the alternator problem that has the following properties: (1) If the underlying topology is arbitrary and the program is executed in read/write atomicity then it is stabilizing fault-tolerant, i.e., starting from an arbitrary state, it recovers to states from where its specification is satisfied, (2) If the underlying topology is bipartite and the program is executed in the concurrent execution model then it provides stabilizing fault-tolerance and maximal concurrency, (3) If the underlying topology is linear or tree then the program provides both these properties, and (4) The program uses bounded state if the network size is known. To our knowledge, this is the first alternator program that achieves these properties.     

Dynamic FTSS in asynchronous systems: The case of unison

Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient faults hit the system. FTSS (Fault-Tolerant Self-Stabilizing) protocols combine the best of both worlds since they tolerate simultaneously transient and (permanent) crash faults. To date, deterministic FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components.In this paper, we present the first study of deterministic FTSS solutions for dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present several impossibility results for this difficult problem and propose an FTSS solution (when the problem is solvable) for the state model that exhibits optimal fault-containment.     

Self-stabilizing byzantine asynchronous unison

We explore asynchronous unison in the presence of systemic transient and permanent Byzantine faults in shared memory. We observe that the problem is not solvable under a less than strongly fair scheduler or for system topologies with maximum node degree greater than two.     

Wait-Free Clock Synchronization

Multiprocessor computer systems are becoming increasingly important as vehicles for solving computationally expensive problems. Synchronization among the processors is achieved with a variety of clock configurations. A new notion of fault-tolerance for clock synchronization algorithms is defined, tailored to the requirements and failure patterns of shared memory multiprocessors. Algorithms in this class can tolerate any number of napping processors, where a napping processor can fail by repeatedly ceasing operation for an arbitrary time interval and then resume operation without necessarily recognizing that a fault has occurred. These algorithms guarantee that, for some fixed k, once a processor P has been working correctly for at least k time, then as long as P continues to work correctly, (1) P does not adjust its clock, and (2) P's clock agrees with the clock of every other processor that has also been working correctly for at least k time. Because a working processor must synchronize in a fixed amount of time regardless of the actions of the other processors, these algorithms are called wait-free. Another useful type of fault-tolerance is called self-stabilization: starting with an arbitrary state of the system, a self-stabilizing algorithm eventually reaches a point after which it correctly performs its task. Two wait-free clock synchronization algorithms are presented for a model with global clock pulses. The first one is self-stabilizing; the second one is not but it converges more quickly than the first one. The self-stabilizing algorithm requires each processor's communication register contents to be a part of the processor's state. This last requirement is proven necessary. A wait-free clock synchronization algorithm is also presented for a model with local clock pulses. This algorithm is not self-stabilizing. Received December 20, 1993; revised January 1995.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.     

Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings

We present a randomized self-stabilizing leader election protocol and a randomized self-stabilizing token circulation protocol under an arbitrary scheduler on anonymous and unidirectional rings of any size. These protocols are space optimal. We also give a formal and complete proof of these protocols. To this end, we develop a complete model for probabilistic self-stabilizing distributed systems which clearly separates the non deterministic behavior of the scheduler from the randomized behavior of the protocol. This framework includes all the necessary tools for proving the self- stabilization of a randomized distributed system: definition of a probabilistic space and definition of the self-stabilization of a randomized protocol. We also propose a new technique of scheduler management through a self-stabilizing protocol composition (cross-over composition). Roughly speaking, we force all computations to have a fairness property under any scheduler, even under an unfair one. This work was done while Maria Gradinariu was working at LRI, Univ. Paris-Sud, CNRS.     

A note on mixed tree coloring

In this note we observe that the problem of mixed graph coloring can be solved in linear time for trees, which improves the quadratic algorithm of Hansen et al. [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].     

Online coloring of hypergraphs

We give a tight bound on randomized online coloring of hypergraphs. The bound holds even if the algorithm knows the hypergraph in advance (but not the ordering in which it is presented). More specifically, we show that for any n and k, there is a 2-colorable k-uniform hypergraph on n vertices for which any randomized online coloring uses Ω(n/k) colors in expectation.     

卫星星间自主时间同步方法研究

卫星时间同步是实现自主导航的关键技术之一.提出了利用高轨卫星的转发和跟踪功能实现星间连续、实时双向时间同步的方法.详细阐述了这种方法的原理,分析了该同步方法的误差.结果表明该方法可用于星间自主相对时间同步.     

基于分布式系统实现时钟同步的统计平均算法

讨论了分布式系统中时钟同步的系统模型,远端时钟读取方法以及双向通信传输过程,给出了3种不同的时钟同步方案,同时,对基于多次同步消息的冗余传输,提出了新的基于统计平均的时钟同步算法。通过多步时间传输协议,在较短同步周期内对时钟进行同步。     

对一种公平非否认协议的新改进

Zhou-Gollmann协议是一种公平非否认协议,近年来得到广泛讨论.Kim发现该协议在时限公平性方面存在缺陷,针对该缺陷提出一种改进的协议,但其改进方法高度依赖于网络时钟的同步.通过详细分析,发现在缺乏时钟同步时Kim的改进协议也可导致不公平.针对此问题,提出一种新的改进方案.新的改进消除了协议对时钟同步的依赖性,保持了协议的公平非否认性,且不会降低协议的效率.     

A survey on self-stabilizing algorithms for independence,domination, coloring,and matching in graphs

Dijkstra defined a distributed system to be self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in a finite time. Even though the concept of self-stabilization received little attention when it was introduced, it has become one of the most popular fault tolerance approaches. On the other hand, graph algorithms form the basis of many network protocols. They are used in routing, clustering, multicasting and many other tasks. The objective of this paper is to survey the self-stabilizing algorithms for dominating and independent set problems, colorings, and matchings. These graph theoretic problems are well studied in the context of self-stabilization and a large number of algorithms have been proposed for them.     

An improved algorithm for online coloring of intervals with bandwidth

We present an improved online algorithm for coloring interval graphs with bandwidth. This problem has recently been studied by Adamy and Erlebach and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use variants of an optimal online coloring algorithm due to Kierstead and Trotter.