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 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 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 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 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 distributed algorithm for the bounded lattice domination problems under the distance-2 model

The domination problem is one of the fundamental graph problems, and there are many variations. In this article, we propose a new problem called the minus -domination problem where , and are integers such that , , and . The problem is to assign a value from for each vertex in a graph such that the local summation of values is greater than or equal to . We also propose a framework named the bounded lattice domination for a class of domination problems, including the minus -domination problem. Then, we present a self-stabilizing distributed algorithm under the distance-2 model for the bounded lattice domination. Here, self-stabilization is a class of fault-tolerant distributed algorithms that tolerate transient faults. The time complexity for convergence is $$, where $$ is the number of processes in a network if the cardinality of the domain of process values is finite and constant. Otherwise, the time complexity for convergence is $$.     

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”.     

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 energy-efficient,self-stabilizing and distributed algorithm for maximal independent set construction in wireless sensor networks

Maximal independent set (MIS) is a very important structure that provides data aggregation, topology control and routing for wireless sensor networks (WSNs). Energy-efficient and fault-tolerant construction of MIS on WSNs is one of the vital tasks. A distributed sensor network is self-stabilizing if it can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilization is a considerable method to provide fault tolerance in WSNs. This paper presents a distributed self-stabilizing MIS algorithm which is an improved version of Turau’s algorithm under a fully distributed scheduler for WSNs. The proposed algorithm is theoretically analyzed and evaluated with its counterparts. The proposed algorithm is compared with the other studies through testbed experiments on IRIS nodes and simulations on TOSSIM environment. It is shown that the proposed algorithm outperforms other algorithms in terms of move count and energy consumption.     

Secure and self-stabilizing clock synchronization in sensor networks

In sensor networks, correct clocks have arbitrary starting offsets and nondeterministic fluctuating skews. We consider an adversary that aims at tampering with the clock synchronization by intercepting messages, replaying intercepted messages (after the adversary’s choice of delay), and capturing nodes (i.e., revealing their secret keys and impersonating them). We present an efficient clock sampling algorithm which tolerates attacks by this adversary, collisions, a bounded amount of losses due to ambient noise, and a bounded number of captured nodes that can jam, intercept, and send fake messages. The algorithm is self-stabilizing, so if these bounds are temporarily violated, the system can efficiently stabilize back to a correct state. Using this clock sampling algorithm, we construct the first self-stabilizing algorithm for secure clock synchronization in sensor networks that is resilient to the aforementioned adversarial attacks.     

Optimal task scheduling algorithm for cyclic synchronous tasks in general multiprocessor networks

We develop an optimal task allocation and scheduling algorithm which minimizes the computing period for multiprocessor systems with general network structures considering task execution time and communication contentions and routing delays explicitly. We presented new ideas of scheduling: (i) individual start allowing overlapping two different iterations, (ii) the scheduling space and the scheduling graph representing feasible schedules, and (iii) the check-and-diffusion algorithm utilizing property of the start-time difference vs. the computing period. With concrete examples of scheduling spaces, segments, and schedules for various multiprocessor network architectures, we showed that individual start reduces the computing period, and our algorithm can find the optimal computing period without exhaustive search.     

Parameterized synthesis of self-stabilizing protocols in symmetric networks

Self-stabilization in distributed systems is a technique to guarantee convergence to a set of legitimate states without external intervention when a transient fault or bad initialization occurs. Recently, there has been a surge of efforts in designing techniques for automated synthesis of self-stabilizing algorithms that are correct by construction. Most of these techniques, however, are not parameterized, meaning that they can only synthesize a solution for a fixed and predetermined number of processes. In this paper, we report a breakthrough in parameterized synthesis of self-stabilizing algorithms in symmetric networks, including ring, line, mesh, and torus. First, we develop cutoffs that guarantee (1) closure in legitimate states, and (2) deadlock-freedom outside the legitimate states. We also develop a sufficient condition for convergence in self-stabilizing systems. Since some of our cutoffs grow with the size of the local state space of processes, scalability of the synthesis procedure is still a problem. We address this problem by introducing a novel SMT-based technique for counterexample-guided synthesis of self-stabilizing algorithms in symmetric networks. We have fully implemented our technique and successfully synthesized solutions to maximal matching, three coloring, and maximal independent set problems for ring and line topologies.     

基于超图的同步无线传感器网络路由算法研究

采用超图理论,将大规模,高连通度的无线传感器网络拓扑抽象为超图模型,从而有效减少网络控制消息。通过建立数据汇聚的最小能耗超树,提出同步无线传感器网络最小生成超树路由算法。理论证明MSHT-SN算法的正确性和有效性。通过仿真,基于超图模型的MSHT-SN算法较优于基于最短路树策略路由算法,能够有效地提高数据传输成功率,并节省网络总能耗,延长网络生存周期。     

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 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.