A self-stabilizing enumeration algorithm

This paper describes a self-stabilizing version of an algorithm presented by A. Mazurkiewicz [Inform. Process. Lett. 61 (1997) 233-239] for enumerating nodes by local rules on an anonymous network. The result improves the reliability aspects of the original algorithm and underlines the importance of a non-ambiguous topology for a network.     

A new self-stabilizing maximal matching algorithm

The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from O(n²)$O\left(n^2\right)$ and O(δm)$O\left(\delta m\right)$ to O(m)$O\left(m\right)$ where n$n$ is the number of processes, m$m$ is the number of edges, and δ$\delta$ is the maximum degree in the graph.     

A self-stabilizing algorithm for strong fairness

Self-stabilization is a novel technique to deal with faults in distributed systems. This paper presents a distributed self-stabilizing algorithm for implementing strong fairness in an arbitrary network. A desirable feature of this algorithm is that it can be used to enforce the strong fairness property on any distributed algorithm including self-stabilizing algorithms. In addition, the algorithm does not require any initialization and can withstand transient failures. At the end of the paper such issues as improving the time complexity of the proposed algorithm and the limitations on the efficiency of any implementation of strong fairness are discussed.     

A self-stabilizing algorithm for bridge finding

Summary. A self-stabilizing algorithm is presented in this paper that finds the bridges of a connected undirected graph on a distributed or network model of computation after moves. The algorithm is resilient to transient faults and does not require initialization. In addition, a correctness proof of the algorithm is provided. The paper concludes with remarks on the time complexity of the algorithm. Received: July 1997 / Accepted: January 1999     

A self-stabilizing algorithm for coloring planar graphs

Summary This paper describes an algorithm for coloring the nodes of a planar graph with no more than six colors using a self-stabilizing approach. The first part illustrates the coloring algorithm on a directed acyclic version of the given planar graph. The second part describes a selfstabilizing algorithm for generating the directed acyclic version of the planar graph, and combines the two algorithms into one. Sukumar Ghosh received his Ph.D. degree in Computer Science from Calcutta University in 1971. From 1969 to 1984, he taught at Jadavpur University, Calcutta. During 1976–77, he was a Fellow of the Alexander von Humboldt Foundation at the University of Dortmund, Germany. Since 1984, he is with the Department of Computer Science of the University of Iowa. His current research interests are in the areas of Distributed Systems, Petri Nets and Self-Stabilizating Systems. Mehmet Hakan Karaata received the Sc. B. degree in Computer Science and Engineering from Hacettepe University in Turkey in 1987, and the M.S. degree in Computer Science from the University of Iowa in 1990. He is currently studying towards his Ph.D. at the same university. His research interests are in the areas of Distributed Systems, Self-Stabilizing Systems and Database Systems.This research was supported in part by the National Science Foundation under grant CCR-9109078, and the Old Gold Summer Fellowship of the University of Iowa. An abstract of this paper was presented at the 29th Allerton Conference on Control, Communication & Computing in October 1991.     

A self-stabilizing algorithm to maximal 2-packing with improved complexity

In self-stabilization, each node has a local view of the distributed network system, in a finite amount of time the system converges to a global setup with desired property, in this case establishing a 2-packing set. Using a graph G=(V,E)$G=(V,E)$ to represent the network, a subset S⊆V$S\subseteq V$ is a 2-packing if ∀i∈V:|N[i]∩S|?1$\forall i\in V:|N[i]\cap S|?1$. In this paper, we first propose an ID-based, constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph. We show that the algorithm stabilizes in O(mn)$O(mn)$ moves under any scheduler (such as a distributed daemon). Secondly, we show that the algorithm stabilizes in O(n²)$O(n^2)$ rounds under a synchronous daemon where every privileged node moves at each round.     

A self-stabilizing algorithm for the maximum flow problem

Summary.  The maximum flow problem is a fundamental problem in graph theory and combinatorial optimization with a variety of important applications. Known distributed algorithms for this problem do not tolerate faults or adjust to dynamic changes in network topology. This paper presents a distributed self-stabilizing algorithm for the maximum flow problem. Starting from an arbitrary state, the algorithm computes the maximum flow in an acyclic network in finitely many steps. Since the algorithm is self-stabilizing, it is inherently tolerant to transient faults. It can automatically adjust to topology changes and to changes in other parameters of the problem. The paper presents results obtained by extensively experimenting with the algorithm. Two main observations based on these results are (1) the algorithm requires fewer than n ² moves for almost all test cases and (2) the algorithm consistently performs at least as well as a distributed implementation of the well-known Goldberg-Tarjan algorithm for almost all test cases. The paper ends with the conjecture that the algorithm correctly computes a maximum flow even in networks that contain cycles. Received: October 1995 / Accepted: February 1997     

A self-stabilizing algorithm to synchronize digital clocks in a distributed system

We have proposed a self-stabilizing algorithm to synchronize multiple digital clocks in a distributed system; whenever any of the clock values gets out of synchronization for any reason, the algorithm is automatically invoked and the system is brought back to a legitimate state in finite time.     

A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2ⁿ) (resp. O(3ⁿ)) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis, improving these bounds considerably. In particular it is shown that the algorithm stabilizes after O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms.     

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.     

A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O(nmA) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves.     

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.     

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.     

A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks

The maximum planarization problem is to find a spanning planar subgraph having the largest number of edges for a given graph. In this paper, we propose a self-stabilizing algorithm to solve this problem for complete bipartite networks. The proposed algorithm finds the maximum planar subgraph of 2n−4 edges in O(n) rounds, where n is the number of nodes.     

A memetic algorithm for the flexible flow line scheduling problem with processor blocking

This paper introduces an efficient memetic algorithm (MA) combined with a novel local search engine, namely, nested variable neighbourhood search (NVNS), to solve the flexible flow line scheduling problem with processor blocking (FFLB) and without intermediate buffers. A flexible flow line consists of several processing stages in series, with or without intermediate buffers, with each stage having one or more identical parallel processors. The line produces a number of different products, and each product must be processed by at most one processor in each stage. To obtain an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches and optimization tools is extremely difficult. Our proposed MA employs a new representation, operators, and local search method to solve the above-mentioned problem. The computational results obtained in experiments demonstrate the efficiency of the proposed MA, which is significantly superior to the classical genetic algorithm (CGA) under the same conditions when the population size is increased in the CGA.     

基于多核处理器并行系统的任务调度算法

针对多核处理器并行系统的特点,提出了相应的任务调度算法,该算法在任务调度之前加入了任务分配技术,通过合理的任务分配,可有效减少多个处理器间的通信开销,使任务调度效率更佳.仿真实现了该算法,并通过实验数据证明了该算法的优越性.