Updatable timed automata with one updatable clock

Updatable timed automata (UTAs) proposed by Bouyer et.al., is an extension of timed automata (TAs) having the extra ability to update clocks in a more elaborate way than simply reset them to zero. The reachability of UTAs is generally undecidable, which can be easily gained by regarding a pair of clocks as updatable counters. This paper investigates a subclass of UTAs by restricting the number of updatable clocks to be one. We will show that (1) the reachability of general UTAs with one updatable clock (UTA1s) is still undecidable, and (2) that of UTA1s under diagonal-free constraints is decidable, and the complexity is Pspace-complete. The former is achieved by encoding Minsky machines to the general UTA1s, where two counters are simulated by the updatable clock. The latter is gained by regarding a region of a UTA1 to be an unbounded digiword, and encoding sets of digiwords that are accepted by a one counter automaton where regions are generated as the value of the counter.     

Robust self-stabilizing weight-based clustering algorithm

Ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. Such networks cannot rely on centralized and organized network management. The clustering problem consists of partitioning network nodes into non-overlapping groups called clusters. Clusters give a hierarchical organization to the network that facilitates network management and that increases its scalability.In a weight-based clustering algorithm, the clusterheads are selected according to their weight (a node’s parameter). The higher the weight of a node, the more suitable this node is for the role of clusterhead. In ad hoc networks, the amount of bandwidth, memory space or battery power of a node could be used to determine weight values.A self-stabilizing algorithm, regardless of the initial system configuration, converges to legitimate configurations without external intervention. Due to this property, self-stabilizing algorithms tolerate transient faults and they are adaptive to any topology change.In this paper, we present a robust self-stabilizing weight-based clustering algorithm for ad hoc networks. The robustness property guarantees that, starting from an arbitrary configuration, after one asynchronous round, the network is partitioned into clusters. After that, the network stays partitioned during the convergence phase toward a legitimate configuration where the clusters verify the “ad hoc clustering properties”.     

Randomization adaptive self-stabilization

We present a scheme to convert self-stabilizing algorithms that use randomization during and following convergence to self-stabilizing algorithms that use randomization only during convergence. We thus reduce the number of random bits from an infinite number to an expected bounded number. The scheme is applicable to the cases in which there exits a local predicate for each node, such that global consistency is implied by the union of the local predicates. We demonstrate our scheme over the token circulation algorithm of Herman (Infor Process Lett 35:63–67, 1990) and the recent constant time Byzantine self-stabilizing clock synchronization algorithm by Ben-Or, Dolev and Hoch (Proceedings of the 27th Annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, (PODC), 2008). The application of our scheme results in the first constant time Byzantine self-stabilizing clock synchronization algorithm that eventually stops using random bits.     

Asynchronous phase synchronization in uniform unidirectional rings

We propose a self-stabilizing asynchronous phase synchronization protocol for uniform unidirectional rings. Consider applications with phase bound K, i.e., the phases are phase 0, phase 1, ...; phase K-1, phase 0, phase 1, etc. Under the protocol, when the ring is stabilized, it satisfies the following criterion: No node begins to execute phase (k+1) mod K until all nodes have executed phase k, and after all nodes have executed their phase k, each node eventually executes phase (k+1) mod K. Besides the variable used to denote the phase that a node is working on, each node maintains only one auxiliary variable with b states, where b can be any number greater than or equal to the ring size. Provided that K and b satisfy the limitation: K/spl times/b>n(b-1), the proposed protocol is correct under the parallel model and takes at most 2(K/spl times/b) rounds to stabilize.     

A self-stabilizing algorithm for cut problems in synchronous networks

Consider a synchronized distributed system where each node can only observe the state of its neighbors. Such a system is called self-stabilizing if it reaches a stable global state in a finite number of rounds. Allowing two different states for each node induces a cut in the graph. In each round, every node decides whether it is (locally) satisfied with the current cut. Afterwards all unsatisfied nodes change sides independently with a fixed probability $p$. Using different notions of satisfaction enables the computation of maximal and minimal cuts, respectively. We analyze the expected time until such cuts are reached on several graph classes and study the impact of the parameter $p$ and the initial cut.     

Possible and Impossible Self-Stabilizing Digital Clock Synchronization in General Graphs

We study digital clock synchronization for multiprocessor systems, where processors are triggered by a common clock pulse and communicate with others via shared memory.A self-stabilizing digital clock synchronization protocol for systems with a general communication graph is presented. The protocol can commence in an arbitrary non-consistent system state and converges to a legitimate state in which the clocks are synchronized and incremented by one in every subsequent pulse.To enhance the fault-tolerance of our protocol, we allow that during and following convergence processors may stop operating. Crash failures may partition the communication graph into several connected components. Our protocol synchronizes the clocks of the processors in every such connected component. For the case in which faulty processors can exhibit Byzantine behavior, we prove that there is no digital clock synchronization protocol that tolerates even one single faulty processor.     

Phase clocks for transient fault repair

Phase clocks are synchronization tools that implement a form of logical time in distributed systems. For systems tolerating transient faults by self-repair of damaged data, phase clocks can enable reasoning about the progress of distributed repair procedures. This paper presents a phase clock algorithm suited to the model of transient memory faults in asynchronous systems with read/write registers. The algorithm is self-stabilizing and guarantees accuracy of phase clocks within O(k) time following an initial state that is.     

Two-state self-stabilizing algorithms for token rings

A self-stabilizing system is a network of processors, which, when started from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite number of steps. This implies that the system can automatically deal with infrequent errors. One issue in designing self-stabilizing algorithms is the number of states required by each machine. This paper presents mutual exclusion algorithms which will be self-stabilizing while only requiring each machine in the network to have two states. The concept of a randomized central demon is also introduced in this paper. The first algorithm is a starting point where no randomization is needed (the randomized central demon is not necessary). The other two algorithms require randomization. The second algorithm builds on the first algorithm and reduces the number of network connections required. Finally, the number of necessary connections is again reduced yielding the final two-state, probabilistic algorithm for an asynchronous, unidirectional ring of processes     

When consensus meets self-stabilization

This paper presents a shared-memory self-stabilizing failure detector, asynchronous consensus and replicated state-machine algorithm suite, the components of which can be started in an arbitrary state and converge to act as a virtual state-machine. Self-stabilizing algorithms can cope with transient faults. Transient faults can alter the system state to an arbitrary state and hence, cause a temporary violation of the safety property of the consensus. Started in an arbitrary state, the long lived, memory bounded and self-stabilizing failure detector, asynchronous consensus, and replicated state-machine suite, presented in the paper, recovers to satisfy eventual safety and eventual liveness requirements. Several new techniques and paradigms are introduced. The bounded memory failure detector abstracts away synchronization assumptions using bounded heartbeat counters combined with a balance–unbalance mechanism. The practically infinite paradigm is introduced in the scope of self-stabilization, where an execution of, say, 2⁶⁴ sequential steps is regarded as (practically) infinite. Finally, we present the first self-stabilizing wait-free reset mechanism that ensures eventual safety and can be used to implement efficient self-stabilizing timestamps that are of independent interest.     

A Self-Stabilizing Leader Election Algorithm in Highly Dynamic Ad Hoc Mobile Networks

The classical definition of a self-stabilizing algorithm assumes generally that there are no faults in the system long enough for the algorithm to stabilize. Such an assumption cannot be applied to ad hoc mobile networks characterized by their highly dynamic topology. In this paper, we propose a self-stabilizing leader election algorithm that can tolerate multiple concurrent topological changes. By introducing the time interval-based computations concept, the algorithm ensures that a network partition can within a finite time converge to a legitimate state even if topological changes occur during the convergence time. Our simulation results show that our algorithm can ensure that each node has a leader over 99$\%$ of the time. We also give an upper-bound on the frequency at which network components merge to guarantee the convergence.     

Vertex-Ant-Walk – A robust method for efficient exploration of faulty graphs

We consider a problem of decentralized exploration of a faulty network by several simple, memoryless agents. The model we adopt for a network is a directed graph. We design an asynchronous algorithm that can cope with failures of network edges and nodes. The algorithm is self-stabilizing in the sense that it can be started with arbitrary initializations and scalable – new agents can be added while other agents are already running. This revised version was published online in August 2006 with corrections to the Cover Date.     

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.     

一种高速延时无关同异步转换接口电路

针对传统片上系统设计同步时钟引起的功耗大、IP核可重用性差等缺点,提出一种可用于多核片上系统和片上网络的快速延时无关同异步转换接口电路.接口由采用门限门的环形FIFO实现,移除了同步时钟,实现了数据从同步时钟模块到异步模块的高速传输,支持多种数据传输协议并保证数据在传输中延时无关.基于0.18μm标准CMOS工艺的Spice模型,对3级环形FIFO所构成的传输接口电路进行了仿真,传输接口的延时为613ps,每响应一个传输请求的平均能耗为3.05pJ?req,可满足多核片上系统和片上网络芯片速度高、功耗低、鲁棒性强和重用性好的设计要求.     

An efficient fault-containing self-stabilizing algorithm for finding a maximal independent set

An independent set is a useful structure because, in some situations, it defines a set of mutually compatible operations, i.e., operations that can be executed simultaneously. We design a fault-containing self-stabilizing algorithm that finds a maximal independent set for an asynchronous distributed system. Our algorithm is an improvement on the self-stabilizing algorithm in Shukla et al. [1995]. In the single-fault situation, the worst-case stabilization time of Shukla's algorithm is /spl Omega/(n), where n is the number of nodes in the system, whereas the worst-case stabilization time of our algorithm is O(/spl Delta/), where /spl Delta/ is the maximum node degree in the system. Compared also with the fault-containing algorithm that is induced from applying the general transformer in Ghosh et al. [1996] to Shukla's algorithm, our algorithm is also seen to be faster in stabilization time, in the single-fault situation. Therefore, our algorithm can be considered to be the most efficient fault-containing self-stabilizing algorithm for the maximal independent set finding up to this point.     

Dynamic Cesaro-Wardrop equilibration in networks

We analyze a routing scheme for a broad class of networks which converges (in the Cesaro sense) with probability one to the set of approximate Cesaro-Wardrop equilibria, an extension of the notion of a Wardrop equilibrium. The network model allows for wireline networks where delays are caused by flows on links, as well as wireless networks, a primary motivation for us, where delays are caused by other flows in the vicinity of nodes. The routing algorithm is distributed, using only the local information about observed delays by the nodes, and is moreover impervious to clock offsets at nodes. The scheme is also fully asynchronous, since different iterates have their own counters and the orders of packets and their acknowledgments may be scrambled. Finally, the scheme is adaptive to the traffic patterns in the network. The demonstration of convergence in a fully dynamic context involves the treatment of two-time scale distributed asynchronous stochastic iterations. Using an ordinary differential equation approach, the invariant measures are identified. Due to a randomization feature in the algorithm, a direct stochastic analysis shows that the algorithm avoids non-Wardrop equilibria. Finally, some comments on the existence, uniqueness, stability, and other properties of Wardrop equilibria are made.     

基于TSDPLL的时钟漂移补偿算法容错研究*

提出集成TSDPLL对系统节点本地时钟计时频率漂移进行有效补偿的时钟同步方法,大大提高了应用网络时间同步技术（如NTP、PTP等）的同步精度。为确保TSDPLL能在网络出现拥塞的情况下仍然正常工作,通过分析收敛函数基本特征,提出基于收敛函数的容错方案。仿真实验结果表明,该方案算法简单、容错效果明显,是基于DPLL时钟漂移补偿算法不可或缺的关键组成部分。     

A note on leader election in directed split-stars and directed alternating group graphs

A leader node is defined to be any node of the network unambiguously identified by some characteristics. In this paper, we first present a distributed algorithm for finding a leader node of a directed split-star. Moreover, an efficient self-stabilizing leader election algorithm that converges with linear rounds is proposed for directed split-stars. Actually, the distributed algorithm and the self-stabilizing algorithm are also applicable to the problem of directed alternating group graphs. As far as we know, no self-stabilizing leader election algorithm was known for the two graphs.     

Unison,canon, and sluggish clocks in networks controlled by a synchronizer

The effect of using a simple synchronizer on the performance of a directed, strongly connected, distributed network, is analysed. In this paper we assume that the time of message transmission is positive but negligible. It is shown that the synchronizer is sufficient to assure that a full rate of computation is achieved in networks with a global clock, in spite of the absence of a global start-up signal. In fact,unison is reached within linear time. A similar phenomenon occurs if there is no global clock, but all local clocks have the same rate. In case the local clocks do not have the same rate, it is shown that the computational rate is not slower than anysluggish clock; i.e., a clock such that between any two of its ticks, every local clock ticks at least once.The first author was supported by the Fund for the Promotion of Research at the Technion. The work of the second author was done while he was in the Computer Science Department of the Technion; he is presently visiting the Laboratory for Computer Science, MIT.     

Toward optimizing a self-creating neural network

This paper optimizes the performance of the growing cell structures (GCS) model in learning topology and vector quantization. Each node in GCS is attached with a resource counter. During the competitive learning process, the counter of the best-matching node is increased by a defined resource measure after each input presentation, and then all resource counters are decayed by a factor alpha. We show that the summation of all resource counters conserves. This conservation principle provides useful clues for exploring important characteristics of GCS, which in turn provide an insight into how the GCS can be optimized. In the context of information entropy, we show that performance of GCS in learning topology and vector quantization can be optimized by using alpha=0 incorporated with a threshold-free node-removal scheme, regardless of input data being stationary or nonstationary. The meaning of optimization is twofold: (1) for learning topology, the information entropy is maximized in terms of equiprobable criterion and (2) for leaning vector quantization, the use is minimized in terms of equi-error criterion.     

A self-stabilizing transformer for population protocols with covering

Developing self-stabilizing solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an automatic transformer for algorithms in an extended population protocol model. Population protocols is a model that was introduced recently for networks with a large number of resource-limited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication “speed”, which is reflected by their cover times. Second, we assume the existence of a special agent with an unbounded memory, the base station. The automatic transformer takes as an input an algorithm solving a static problem (and meeting some additional rather natural requirements) and outputs a self-stabilizing algorithm for the same problem. The transformer is built using a re-execution approach (the technique consisting of executing an algorithm repeatedly in order to obtain its self-stabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.