Fault-Local Distributed Mending

doi:10.1006/jagm.1998.0972

Journal of Algorithms

Volume 30, Issue 1, January 1999, Pages 144-165

https://doi.org/10.1006/jagm.1998.0972 Get rights and content

Abstract

As communication networks grow, existing fault handling tools that involveglobalmeasures such as global time-outs or reset procedures become increasingly unaffordable, since their cost grows with the size of the network. Rather, for a fault handling mechanism to scale to large networks, its cost must depend only on the number of failed nodes (which, thanks to today's technology, grows much more slowly than the networks). Moreover, it should allow the nonfaulty regions of the networks to continue their operation even during the recovery of the faulty parts. This paper introduces the conceptsfault localityandfault-locally mendableproblems, which are problems for which there are correction algorithms (applied after faults) whose cost depends only on the (unknown) number of faults. We show thatanyinput-output problem is fault-locally mendable. The solution involves a novel technique combining data structures and “local votes” among nodes, which may be of interest in itself.

References (33)

Y. Afek et al.
Applying static network protocols to dynamic networks
Proceedings 28th IEEE Symposium on Foundations of Computer Science
(October 1987)
B. Awerbuch, I. Cidon, S. Kutten, Optimal maintenance of replicated informations, in, Proceedings 31st IEEE Symposium...
B. Awerbuch et al.
Optimal broadcasting with partial knowledge
SIAM J Comput.
(1998)
B. Awerbuch, B. Patt-Shamir, G. Varghese, Self-stabilization by local checking and correction, in, Proceedings of the...
Y. Afek, S. Kutten, M. Yung, Memory-efficient self-stabilizing protocols for general networks, in, Proceedings of the...
B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-Shamir, G. Varghese, Time-optimal self-stabilizing synchronization, in,...
D.E. Comer
Internetworking with TCP/IP
(1991)
A. Bar-Noy et al.
Designing broadcasting algorithms in the postal model for message-passing systems
Math. Systems Theory
(1994)
J-C. Bermond, D. Peleg, The power of small coalitions in graphs, in, Proceedings of the 2nd Colloquium on Structural...
J-C. Bermond, J. Bond, D. Peleg, S. Perennes, Tight bounds on the size of 2-monopolies, in, Proceedings of the 3rd...

I. Cidon et al.

Distributed control for fast networks

IEEE Trans. Commun.

(1995)

T. D. Chandra, S. Toueg, Unreliable failure detector for asynchronous systems, in, Proceedings of the 10th ACM...

S. Ghosh, A. Gupta, T. Herman, S. V. Pemmaraju, Fault-containing self-stabilizing algorithms, in, Proceedings of the...

T. D. Chandra, V. Hadzilacos, S. Toueg, The weakest failure detector for solving consensus, in, Proceedings of the 11th...

I. Cidon et al.

New models and algorithms for future networks

IEEE Trans. Inform. Theory

(1995)

I. Chlamtac, S. Kutten, A spatial reuse TDMA/FDMA for mobile multihop radio networks, in, Proceedings of IEEE INFOCOM,...

Cited by (36)

Error-sensitive proof-labeling schemes
2022, Journal of Parallel and Distributed Computing
Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state.
In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the Hamming distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., cycle-freeness, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs do not. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on $O (\log n)$ bits, and on $O (\log^{2} n)$ bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.
Dynamic networks of finite state machines
2020, Theoretical Computer Science
Like distributed systems, biological multicellular processes are subject to dynamic changes and a biological system will not pass the survival-of-the-fittest test unless it exhibits certain features that enable fast recovery from these changes. In most cases, the types of dynamic changes a biological process may experience and its desired recovery features differ from those traditionally studied in the distributed computing literature. In particular, a question seldomly asked in the context of distributed digital systems, and that is crucial in the context of biological cellular networks, is whether the system can keep the changing components confined so that only nodes in their vicinity may be affected by the changes, but nodes sufficiently far away from any changing component remain unaffected.
Based on this notion of confinement, we propose a new metric for measuring the dynamic changes recovery performance in distributed network algorithms operating under the Stone Age model (Emek and Wattenhofer, 2013) [1], where the class of dynamic topology changes we consider includes inserting/deleting an edge, deleting a node together with its incident edges, and inserting a new isolated node. Our main technical contribution is a distributed algorithm for maximal independent set (MIS) in synchronous networks subject to these topology changes that performs well in terms of the aforementioned new metric. Specifically, our algorithm guarantees that nodes which do not experience a topology change in their immediate vicinity are not affected and that all surviving nodes (including the affected ones) perform $O ((C + 1) \log^{2} n)$ computationally-meaningful steps, where C is the number of topology changes; in other words, each surviving node performs $O (\log^{2} n)$ steps when amortized over the number of topology changes. This is accompanied by a simple example demonstrating that the linear dependency on C cannot be avoided.
A computational study of f-reversible processes on graphs
2018, Discrete Applied Mathematics
An $f$ -reversible process on a graph $G = (V, E)$ is a graph dynamical system on $V (G)$ defined as follows. Given a function $f : V (G) \to N$ and an initial vertex labeling $c_{0} : V (G) \to {0, 1}$ , every vertex $v$ changes its label if and only if at least $f (v)$ of its neighbors have the opposite state, synchronously in discrete-time. For such processes, we present a new nondecreasing time function similar to the monotonically decreasing energy functions used to study threshold networks, which leads to a periodic behavior after a transient phase. Using this new function, we provide a tight upper bound on the transient length of $f$ -reversible processes. Furthermore, we prove that it is equal to $n - 3$ for trees with $n \geq 4$ vertices and $Im (f) = {2}$ . Moreover we present an algorithm that generates all the initial configurations attaining this bound and we prove that the number of such configurations is $O (n)$ . We also consider the problem of determining the smallest number $r_{f} (G)$ of vertices with initial label 1 for which all the vertices eventually reach label 1 after the complete evolution of the dynamics, which models consensus problems on networks. We prove that it is $N P$ -hard to compute $r_{f} (G)$ even for bipartite graphs with $Δ (G) \leq 3$ and $Im (f) = {1, 2, 3}$ . Finally, we prove that $β (G) \leq r_{f} (G) \leq β (G) + 1$ , when $f (v) = d (v)$ for all $v \in V (G)$ , where $β (G)$ is the size of a minimum vertex cover of $G$ .
An analysis of fault detection strategies in wireless sensor networks
2017, Journal of Network and Computer Applications
Citation Excerpt :
In a majority of cases, the faults are local to specific component of WSN. Faults are extremely local in the network and only affect a few components of the network (Kutten and Peleg, 1999). Generally, the entire WSN is not faulty.
Wireless sensor networks have emerged as a key technology which is used in many safety critical applications. The sensors in wireless sensor network have to be deployed in hostile, harsh and unattended environments for long periods of time. This creates a great challenge in providing a good quality of service. This results in introductions of faults, sensor failures, communication failures and changes in topology. Hence, efficient fault detection techniques are required for good quality of service. In this article, we survey various fault detection techniques and provide a new taxonomy to integrate new fault detection techniques. We perform a qualitative comparison of the latest fault detection algorithms. From a qualitative analysis, we select a list of techniques that are analyzed quantitatively. We also discuss the shortcomings, advantages and future research directions for fault detection in wireless sensor networks.
Irreversible conversion processes with deadlines
2014, Journal of Discrete Algorithms
Citation Excerpt :
The spreading of something like a property or a commodity within a network is a recurrent feature in many contexts such as social influence [8,12,16,20], gene expression networks [15], immune systems [1], cellular automata [2], percolation [4], marketing strategies [7,16], and distributed computing [5,10,17–19].
Given a graph G, a deadline $t_{d} (u)$ and a time-dependent threshold $f (u, t)$ for every vertex u of G, we study sequences $C = (c_{0}, c_{1}, \dots)$ of 0/1-labelings $c_{i}$ of the vertices of G such that for every $t \in N$ , we have $c_{t} (u) = 1$ if and only if either $c_{t - 1} (u) = 1$ or at least $f (u, t - 1)$ neighbors v of u satisfy $c_{t - 1} (v) = 1$ . The sequence $C$ models the spreading of a property/commodity within a network and it is said to converge to 1 on time, if $c_{t_{d} (u)} (u) = 1$ for every vertex u of G, that is, if every vertex u has the spreading property/received the spreading good by time $t_{d} (u)$ .
We study the smallest number $irr (G, t_{d}, f)$ of vertices u with initial label $c_{0} (u)$ equal to 1 that result in a sequence $C$ converging to 1 on time. If G is a forest or a clique, we present efficient algorithms computing $irr (G, t_{d}, f)$ . Furthermore, we prove lower and upper bounds relying on counting and probabilistic arguments. For special choices of $t_{d}$ and f, the parameter $irr (G, t_{d}, f)$ coincides with well-known graph parameters related to domination and independence in graphs.
Reversible iterative graph processes
2012, Theoretical Computer Science
Given a graph $G$ , a function $f : V (G) \to Z$ , and an initial $0 / 1$ -vertex-labelling $c_{1} : V (G) \to {0, 1}$ , we study an iterative $0 / 1$ -vertex-labelling process on $G$ where in each round every vertex $v$ changes its label if and only if at least $f (v)$ neighbours have a different label. For special choices of the values of $f$ , such processes model consensus issues and have been studied under names such as local majority processes or iterative polling processes in a large variety of contexts especially in distributed computing. Our contributions concern computational aspects related to the minimum cardinality $r_{f} (G)$ of sets of vertices with initial label $1$ such that during the process on $G$ all vertices eventually change their label to $1$ . Such sets are known as dynamic monopolies or dynamos for short. We establish a hardness result and describe efficient algorithms for restricted instances on paths and cycles.

View all citing articles on Scopus

^*: Alexander Goldberg lecturer.

^†: Supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israel Science Foundation. Part of the work was done while visiting the IBM T. J. Watson Research Center.