We consider the problem of gathering in finite time and at the same location, not known beforehand, a set of deterministic semi-synchronous robots, starting from an arbitrary initial configuration that may even be bivalent (that is, a configuration where the robots are evenly split on two different locations). This problem is known to be unsolvable when the robots are oblivious, that is, when they cannot remember their past actions. We present two deterministic gathering algorithms where robots may remember and communicate a single bit of memory. This bit may be arbitrarily (and adversarially) set in the initial configuration. Our solutions are thus memory optimal and self-stabilizing. The first algorithm makes use of multiplicity detection, while the second solely uses robot colors. Their proof of correctness is formally certified by the Coq proof assistant using the Pactole framework.

In this paper, we address the problem of uniformly deploying mobile robots in complete bipartite graphs. Specifically, when n robots are positioned arbitrarily at distinct nodes in a complete bipartite graph K_{n,n}, which consists of two n-node sets V_L and V_R, the uniform deployment problem requires the robots to achieve one of the following configurations: (a) each node in V_L is occupied by exactly one robot, with no robots in V_R, or (b) each node in V_R is occupied by exactly one robot, with no robots in V_L. In either configuration, the distance between any two robots is 2, ensuring that the robots are uniformly deployed. In this paper, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we characterize solvable and unsolvable initial configurations under the assumption that robots have an infinite visibility range. Next, we demonstrate that visibility range 1 (meaning robots can only observe nodes at a distance of 1 and the robots positioned on them) is insufficient, proving the impossibility of solving the problem under this constraint. Conversely, we show that visibility range Θ(log n) is sufficient by presenting an algorithm that solves the uniform deployment problem in O(1) rounds, starting from any solvable initial configuration. Finally, we briefly introduce an example showing that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a native way.

Hierarchical federated learning (HFL) has attracted academic attention to improve the efficiency of federated learning (FL) in real-world applications, however, little research has been done to explore the structural advantages of HFL against Byzantine attacks and to investigate how to make HFL immune to top-level server Single Point of Failure (SPOF). To explore this field and improve the robustness of HFL, we propose a novel generalized paradigm ABD-HFL for asynchronous Byzantine-resistant decentralized hierarchical federated learning, a multi-tier structure without a central server for FL tasks with a large number of devices. Based on the layered structure, an innovative universal Byzantine resistance mechanism is designed in ABD-HFL, which enables it to apply a combination of multiple Byzantine robust techniques, making ABD-HFL more powerful than any single application of such techniques. Besides, ABD-HFL is a fully decentralized HFL, there is no central server, but rather multiple nodes at the top level agree on the global model where malicious model updates are excluded. A new concept of pipeline learning workflow is also introduced to study communication efficiency in ABD-HFL, which is based on asynchronous communication between various levels to train and propagate the global model. Our numerical evaluation validates the advantage of ABD-HFL in terms of robustness and communication efficiency.

ABSTRACT We consider the network construction process by selfish players. Each player is associated with a vertex of a communication graph and can simultaneously remove one incident edge and add a new incident edge. Each player is interested in a subset of players and the goal of each player is to minimize the average or maximum distance to these players. Starting from a given initial communication graph, a sequence of selfish edge swaps generates an evolution of the communication graph. Due to non‐uniform communication interest, this game may converge to a disconnected Nash equilibrium, which may attain infinite social costs. In this paper, we focus on the dynamics of this game. We first give theoretical analysis such as the existence of a best response cycle and a sufficient condition for keeping connectivity in dynamics. We then present simulation results to show the ratio of Nash equilibria with infinite cost, diameters of Nash equilibria, social cost, price of anarchy, price of stability, and convergence time.

Network-based Intrusion Detection Systems (NIDS) are crucial in cybersecurity, but evaluation methodologies are outdated and lack standardization, resulting in incomplete and unreliable assessments. To address these issues, we first proposed a comprehensive evaluation framework for Machine Learning-based Intrusion Detection Systems [1]. This framework accounts for the unique aspects, strengths, and weaknesses of ML algorithms. However, the initial proposition lacked practicality, as it presented an abstract methodology without a substantive solution. In this paper, we present a demo of FREIDA a precise and concrete implementation of our framework, featuring an easy-to-use graphical interface. We also outline FREIDA's evaluation methodology and demonstrate its application in evaluating IDS using a dataset from the literature.

In this paper we propose and evaluate an innovative algorithm that enables the creation of Peer-to-Peer network overlays characterized by emergent multi-hubs. This approach generates overlays that balance between the randomness of a graph and the structure of a star network, resulting in networks that not only feature prominent hubs but also exhibit strong resilience to failures. By leveraging principles of preferential attachment and random attachment, our method allows hubs to form spontaneously, offering a decentralized and fault-tolerant solution ideal for applications requiring both low network diameter and high robustness. The protocol is entirely decentralized, operates asynchronously, and depends exclusively on local information. Nodes organically evolve into hubs and remain indistinguishable from other nodes (except in terms of the number of incoming links). The quantity of hubs that emerge can be predetermined by the application as a network parameter.

The deployment of 5G networks has significantly improved connectivity, providing remarkable speed and capacity. These networks rely on Software-Defined Networking (SDN) to enhance control and flexibility. However, this advancement poses critical challenges including expanded attack surface due to network virtualization and the risk of unauthorized access to critical infrastructure. Since traditional cybersecurity methods are inadequate in addressing the dynamic nature of modern cyber attacks, employing artificial intelligence (AI), and deep reinforcement learning (DRL) in particular, was investigated to enhance 5G networks security. This interest arises from the ability of these techniques to dynamically respond and adapt their defense strategies according to encountered situations and real-time threats. Our proposed mitigation system uses a DRL framework, enabling an intelligent agent to dynamically adjust its defense strategies against a range of DDoS attacks, exploiting ICMP, TCP SYN, and UDP, within an SDN environment designed to mirror real-life user behaviors. This approach aims to maintain the network’s performance while concurrently mitigating the impact of the real-time attacks, by providing adaptive and automated countermeasures according to the network’s situation.

We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.

Abstract We consider the problem of constructing a maximum independent set with mobile myopic luminous robots on a grid network whose size is finite but unknown to the robots. In this setting, the robots enter the grid network one by one from a corner of the grid, and they eventually have to be disseminated on the grid nodes so that the occupied positions form a maximum independent set of the network. We assume that robots are asynchronous, anonymous, silent and they execute the same distributed algorithm. In this paper, we propose two algorithms: The first one assumes that the number of light colors of each robot is three and the visible range is two, but uses the additional assumption that a local edge-labeling exists for each node. To remove this assumption, the second one assumes that the number of light colors of each robot is seven, and that the visible range is three. In both algorithms, the number of movements is $O(n(L+l))$ steps, where $n$ is the number of nodes and $L$ and $l$ are the grid dimensions.

We study a novel graph path planning problem for multiple agents that may crash at runtime, and block part of the workspace. In our setting, agents can detect neighboring crashed agents, and change followed paths at runtime. The objective is then to prepare a set of paths and switching rules for each agent, ensuring that all correct agents reach their destinations without collisions or deadlocks, despite unforeseen crashes of other agents. Such planning is attractive to build reliable multi-robot systems. We present problem formalization, theoretical analysis such as computational complexities, and how to solve this offline planning problem.

Summary In this paper, we consider the problem of semi‐uniform deployment for mobile robots in perfect ‐ary trees. This problem requires robots to spread in the tree so that, for some positive integer and some fixed integer , each node of depth is occupied by a robot. Robots have an infinite visibility range but are opaque, and each robot can emit a light color visible to itself and other robots, taken from a set of colors, at each time step. Then, we clarify the solvability of the semi‐uniform deployment problem, focusing on the number of available light colors. First, we consider robots with . In this setting, we show that there is no collision‐free algorithm to solve the problem. Next, relax the number of available light colors, that is, we consider robots with . In this setting, we propose a collision‐free algorithm that can solve the problem. From these results, we can show that the semi‐uniform deployment problem can be solved when , and our proposed algorithm is optimal with respect to the number of used light colors (i.e., 2).

In this paper, we consider the Byzantine reliable broadcast problem on authenticated and partially connected networks. The state-of-the-art method to solve this problem consists in combining two algorithms from the literature. Handling asynchrony and faulty senders is typically done thanks to Gabriel Bracha's authenticated double-echo broadcast protocol, which assumes an asynchronous fully connected network. Danny Dolev's algorithm can then be used to provide reliable communications between processes in the global fault model, where up to f processes among N can be faulty in a communication network that is at least 2f+1-connected. Following recent works that showed how Dolev's protocol can be made more practical thanks to several optimizations, we show that the state-of-the-art methods to solve our problem can be optimized thanks to layer-specific and cross-layer optimizations. Our simulations with the Omnet++ network simulator show that these optimizations can be efficiently combined to decrease the total amount of information transmitted or the protocol's latency (e.g., respectively, −25% and −50% with a 16B payload, N=31 and f=4) compared to the state-of-the-art combination of Bracha's and Dolev's protocols.

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

Abstract We consider swarms of asynchronous oblivious robots evolving into an anonymous grid-shaped network. In this context, we investigate optimal (w.r.t. the number of robots) deterministic solutions for the terminating exploration problem. We first show lower bounds in the semi-synchronous model. Precisely, we show that at least three robots are required to explore any grid of at least three nodes, even in the probabilistic case. Then, we show that at least four (resp. five) robots are necessary to deterministically explore a $\bf(2,2)$-Grid (resp. a $\bf(3,3)$-Grid). We then propose deterministic algorithms in the asynchronous model. This latter being strictly weakest than the semi-synchronous model, all the aforementioned bounds still hold in that context. Our algorithms actually exhibit the optimal number of robots that is necessary to explore a given grid. Overall, our results show that except in two particular cases, three robots are necessary and sufficient to deterministically explore a grid of at least three nodes and then terminate. The optimal number of robots for the two remaining cases is four for the $\bf(2,2)$-Grid and five for the $\bf(3,3)$-Grid, respectively.

In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of arbitrary communication graphs. As a result, we investigate the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.

A wide diversity of IoT devices are connected in various smart homes with an extremely rapid growth. Identifying IoT devices as they connect to the network enables better devices and services management. However, autonomous identification is very challenging in such heterogeneous environments. In this paper, we present a near-real time classification approach, based on network features that are extracted both from characteristics of traffic flows and from the payloads of the packets, to discriminate device types. Our solution automatically identifies a newly connected device to the home network. Furthermore, we evaluate the performance of our method using a representative and heterogeneous set of real IoT devices. Our results show autonomous recognition with 97% average accuracy, based on decision tree models using the one-vs.-all method.

In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of \emph{arbitrary} communication graphs. As a result, we clarify the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.

The paper details the first successful attempt at using model checking techniques to verify the correctness of distributed algorithms for robots evolving in a continuous environment. The study focuses on the problem of rendezvous of two robots with lights.There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g., FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between robots activation schedules.The paper presents a generic verification model written for the SPIN model checker. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model checker are consistent with the results known in the literature. The model checker outputs a counter-example execution in every case that is known to fail.In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem for luminous rendezvous algorithms.

International audience

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

The paper details the first successful attempt at using model-checking techniques to verify the correctness of distributed algorithms for robots evolving in a \emph{continuous} environment. The study focuses on the problem of rendezvous of two robots with lights. There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g., FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between robots activation schedules. The paper presents a generic verification model written for the SPIN model-checker. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model-checker are consistent with the results known in the literature. The model-checker outputs a counter-example execution in every case that is known to fail. In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem for luminous rendezvous algorithms.

We study verification problems for autonomous swarms of mobile robots that self-organize and cooperate to solve global objectives. In particular, we focus in this paper on the model proposed by Suzuki and Yamashita of anonymous robots evolving in a discrete space with a finite number of locations (here, a ring). A large number of algorithms have been proposed working for rings whose size is not a priori fixed and can be hence considered as a parameter. Handmade correctness proofs of these algorithms have been shown to be error-prone, and recent attention had been given to the application of formal methods to automatically prove those. Our work is the first to study the verification problem of such algorithms in the parameterized case. We show that safety and reachability problems are undecidable for robots evolving asynchronously. On the positive side, we show that safety properties are decidable in the synchronous case, as well as in the asynchronous case for a particular class of algorithms. Several properties on the protocol can be decided as well. Decision procedures rely on an encoding in Presburger arithmetics formulae that can be verified by an SMT-solver. Feasibility of our approach is demonstrated by the encoding of several case studies.

We present a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks. Our algorithm is efficient (its stabilization time is O(e) moves, where e denotes the number of edges in the network). Besides, our algorithm is optimal with respect to identifiers locality (we assume node identifiers are distinct up to distance three, a necessary condition to withstand arbitrary networks).

We present two geometric routing algorithms that reliably deliver messages to all devices in a geocast region. One algorithm is based on flooding, the other on concurrent geometric routing. They are the fist known stateless geocasting algorithms. We formally prove the algorithms correct, evaluate their performance through abstract and concrete simulation and estimate their message complexity.

In this paper we prove lower and matching upper bounds for the number of servers required to implement a regular shared register that tolerates unsynchronized Mobile Byzantine failures. We consider the strongest model of Mobile Byzantine failures to date: agents are moved arbitrarily by an omniscient adversary from a server to another in order to deviate their computation in an unforeseen manner. When a server is infected by an Byzantine agent, it behaves arbitrarily until the adversary decides to move the agent to another server. Previous approaches considered asynchronous servers with synchronous mobile Byzantine agents (yielding impossibility results), and synchronous servers with synchronous mobile Byzantine agents (yielding optimal solutions for regular register implementation, even in the case where servers and agents periods are decoupled). We consider the remaining open case of synchronous servers with unsynchronized agents, that can move at their own pace, and change their pace during the execution of the protocol. Most of our findings relate to lower bounds, and characterizing the model parameters that make the problem solvable. It turns out that unsynchronized mobile Byzantine agent movements requires completely new proof arguments, that can be of independent interest when studying other problems in this model. Additionally, we propose a generic server-based algorithm that emulates a regular register in this model, that is tight with respect to the number of mobile Byzantine agents that can be tolerated. Our emulation spans two awareness models: servers with and without self-diagnose mechanisms. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state.

We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).

The contribution of this paper is threefold. First, we give tight bounds for the complexity of the problem of data aggregation in static networks. In more details, we show that the problem remains NP-complete when the graph is of degree at most three. Second, we investigate the complexity of the same problem in a dynamic network, that is, a network whose topology can evolve through time. In the case of dynamic networks, we show that the problem is NP-complete even in the case where the graph is of degree at most two. Third, we give the first lower and upper bounds for the minimum data aggregation time in a dynamic graph. We also observe that even in a well-connected evolving graphs, the optimal solution cannot be found by a distributed algorithm or by a centralized algorithm that does not know the future.

This paper considers the Approximate Agreement problem in presence of mobile Byzantine agents. We prove lower bounds on the number of correct processes to solve such problem. To do that we prove that the existing solutions tolerant to Byzantine agents still holds in such case and under which conditions.

We consider the problem of aggregating data in a dynamic graph, that is, aggregating the data that originates from all nodes in the graph to a specific node, the sink. In our model, nodes are endowed with unlimited memory and unlimited computational power. Yet, we assume that communications between nodes are carried out with pairwise interactions, where nodes can exchange control information before deciding whether they transmit their data or not, given that each node is allowed to transmit its data at most once. When a node receives a data from a neighbor, the node may aggregate it with its own data. We are interested in giving lower bounds for this problem, under two possible adversaries: the oblivious adversary, and the randomized adversary that chooses the pairwise interactions uniformly at random. For the online adaptive and the oblivious adversary, we give impossibility results when nodes have no knowledge about the graph and are not aware of the future. For the randomized adversary, we propose two optimal algorithms, (i) when nodes have no knowledge at all and (ii) when each node knows its future pairwise interactions with the sink.

We present an optimal emulation of a server based regular read/write storage in a synchronous round-free message-passing system that is subject to mobile Byzantine failures and prove that the problem is impossible to solve in asynchronous settings. In a system with n servers implementing a regular register, our construction tolerates faults (or attacks) that can be abstracted by agents that are moved (in an arbitrary and unforeseen manner) by a computationally unbounded adversary from a server to another in order to deviate the server's computation. When a server is infected by an adversarial agent, it behaves arbitrarily until the adversary decides to "move" the agent to another server. We investigate the case where the movements of the mobile Byzantine agents are decided by the adversary and are completely decoupled from the message communication delay. Our emulation spans two awareness models: servers with and without self-diagnosis mechanism. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state. Our results, proven optimal with respect to the threshold of the tolerated mobile Byzantine faults in the first model, are significantly different from the round-based synchronous models. Another interesting side result of our study is that, contrary to the round-based synchronous consensus implementation for systems prone to mobile Byzantine faults, our storage emulation does not rely on the necessity of a core of correct processes all along the computation. That is, every server in the system can be compromised by the mobile Byzantine agents at some point in the computation. This leads to another interesting conclusion: storage is easier than consensus in synchronous settings, when the system is hit by mobile Byzantine failures.

We propose a new probabilistic pattern formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common "North" nor a common "Right"), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general pattern (and not just patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low -- a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic pattern formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form patterns with multiplicity points (except the gathering case due to impossibility results), a new feature in the context of pattern formation that we believe is an important asset of our approach.

International audience

The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date.

Recent applications of Wireless Sensor Network require small yet sustainable battery-powered devices. As a consequence, it becomes crucial to accurately and efficiently compute a node's power consumption in order to estimate its lifetime. Existing wireless network simulators either implement simplistic energy consumption and battery models, or very complex and general ones that hinders scalability. In this paper, we (i) present WiSeBat, a module to estimate devices lifetime using realistic energy consumption and battery models, that has specially been optimized for wireless sensor network simulations. We then (ii) validate it through real measurements. Finally, we used it (iii) to compare wireless sensor lifetime in several realistic scenarios. Firstly, we review existing techniques to simulate a battery and discuss what behaviors are important to get realistic and fast simulations. We then propose simulator-independent models for the battery and for the energy consumption of sensors, and implement this model in the WSNet simulator. Secondly, we compare measured and simulated lifetimes of sensors. On the one hand, our experiments show that our models provide an 86 - 96% accurate lifetime estimation. On the other hand, the previous default WSNet models overestimate lifetime by more than 2600%. Once validated, we used our approach to benchmark the energy consumption of different protocol stacks of wireless sensor networks, under different scenarios. These simulations match well-known results in simple scenarios, as we demonstrate better performance of ContikiMAC over X-MAC. They also provide an accurate comparison of sensor lifetime in more complex scenarios.

Distributed storage service is one of the main abstractions provided to developers of distributed applications due to its ability to hide the complexity generated by the various messages exchanged between processes. Many protocols have been proposed to build Byzantine-fault-tolerant (BFT) storage services on top of a message-passing system but none of them considers the possibility that well-behaving processes (i.e. correct processes) may experience transient failures due to, say, isolated errors during computation or bit alteration during message transfer. This paper proposes a stabilizing Byzantine-tolerant algorithm for emulating a multi-writer multi-reader regular register abstraction on top of a message passing system with n > 5f servers, which we prove to be the minimal possible number of servers for stabilizing and tolerating f Byzantine servers. That is, each read operation returns the value written by the most recent write and write operations are totally ordered with respect to the happened before relation. Our algorithm is particularly appealing for cloud computing architectures where both processors and memory contents (including stale messages in transit) are prone to errors, faults and malicious behaviors. The proposed implementation extends previous BFT implementations in two ways. First, the algorithm works even when the local memory of processors and the content of the communication channels are initially corrupted in an arbitrary manner. Second, unlike previous solutions, our algorithm uses bounded logical timestamps, a feature difficult to achieve in the presence of transient errors.

We present a flexible scheme and an optimization algorithm for request routing in Content Delivery Networks (CDN). Our online approach, which is based on Lyapunov theory, provides a stable quality of service to clients, while improving content delivery delays. It also reduces data transport costs for operators.

We consider the following problem: two nodes want to reliably communicate in a dynamic multihop network where some nodes have been compromised, and may have a totally arbitrary and unpredictable behavior. These nodes are called Byzantine. We consider the two cases where cryptography is available and not available. We prove the necessary and sufficient condition (that is, the weakest possible condition) to ensure reliable communication in this context. Our proof is constructive, as we provide Byzantine-resilient algorithms for reliable communication that are optimal with respect to our impossibility results. In a second part, we investigate the impact of our conditions in three case studies: participants interacting in a conference, robots moving on a grid and agents in the subway. Our simulations indicate a clear benefit of using our algorithms for reliable communication in those contexts.

We consider the problem of reliably broadcasting messages in a network where some nodes are likely to fail. We consider the most general failure model: the Byzantine model, where the failing nodes have an arbitrary behavior, and may actively try to destabilize the network. We focus on totally decentralized solutions. Most existing solutions require high network connectivity, and are not adapted to sparsely connected networks. A typical example is the grid, where each node has at most four neighbors. In this paper, we propose a new broadcast protocol adapted to such networks. This protocol is based on interconnected subsets called control zones, that filter the diffusion of false messages. We give a methodology to determine a set of nodes that always communicate reliably, depending on the placement of Byzantine nodes. We then use this methodology to perform an experimental evaluation on square and hexagonal grids, in the presence of randomly distributed Byzantine failures. We show that our protocol significantly improves the communication probability, compared to existing solutions.

We consider the problem of reliably broadcasting messages in a multi-hop network where nodes can fail in some unforeseen manner. We consider the most general failure model: the Byzantine model, where failing nodes may exhibit arbitrary behavior, and actively try to harm the network. Previous approaches dealing with permanent Byzantine failures limit either the number of Byzantine nodes or their density. In dense network, the density criterium is the allowed fraction of Byzantine neighbors per correct node. In sparse networks, density has been defined as the distance between Byzantine nodes. In this context, we first propose a new algorithm for networks whose communication graph can be decomposed into cycles: e.g., a torus can be decomposed into square cycles, a planar graph into polygonal cycles, etc. Our algorithm ensures reliable broadcast when the distance between permanent Byzantine failures is greater than twice the diameter of the largest cycle of the decomposition. Then, we refine the first protocol to make it Byzantine fault tolerant for transient faults (in addition to permanent Byzantine faults). This additional property is guaranteed by means of self-stabilization, which permits to recover from any arbitrary initial state. This arbitrary initial state can be seen as the result of every node being Byzantine faulty for a short period of time (hence the transient qualification). This second protocol thus tolerates permanent (constrained by density) and transient (unconstrained) Byzantine failures. When the maximum degree and cycle diameter are both bounded, both solutions perform in a time that remains proportional to the network diameter.

We study distributed coordination among autonomous mobile robots, focussing on the problem of gathering the robots at a single location. The gathering problem has been solved previously using deterministic algorithms even for robots that are anonymous, oblivious, disoriented, and operate in the semi-synchronous ATOM model. However these solutions require all robots to be fault-free. The recent results of Agmon and Peleg [1] show how to gather all correct robots when one of the robots may crash permanently. We study gathering in n-robot systems with f crashes for any f <; n. In such a scenario, no robot can wait for another robot, i.e., the algorithm must be wait-free. We provide such a wait-free algorithm to gather all correct robots assuming the capabilities of strong multiplicity detection and chirality. Unlike previous solutions, our algorithm does not impose the requirement of initially distinct locations, and works for any arbitrary initial configuration of robots (except the bivalent configuration where deterministic gathering is not possible).

This paper focuses on compact deterministic self-stabilizing solutions for the leader election problem. Self-stabilization is a versatile approach to withstand any kind of transient failures. Leader election is a fundamental building block in distributed computing, enabling to distinguish a unique node, in order to, e.g., execute particular actions. When the protocol is required to be silent (i.e., when communication content remains fixed from some point in time during any execution), there exists a lower bound of Ω(log n) bits of memory per node participating to the leader election (where n denotes the number of nodes in the system). This lower bound holds even in rings.

We propose a new metric for effectively and accurately evaluating the performance of self-stabilizing algorithms. Self-stabilization is a versatile category of fault-tolerance that guarantees system recovery to normal behavior within a finite number of steps, when the state of the system is perturbed by transient faults (or equally, the initial state of the system can be some arbitrary state). The performance of self-stabilizing algorithms is conventionally characterized in the literature by asymptotic computation complexity. We argue that such characterization of performance is too abstract and does not reflect accurately the realities of deploying a distributed algorithm in practice. Our new metric for characterizing the performance of self-stabilizing algorithms is the expected mean value of recovery time. Our metric has several crucial features. Firstly, it encodes accurate average case speed of recovery. Secondly, we show that our evaluation method can effectively incorporate several other parameters that are of importance in practice and have no place in asymptotic computation complexity. Examples include the type of distributed scheduler, likelihood of occurrence of faults, the impact of faults on speed of recovery, and network topology. We utilize a deep analysis technique, namely, probabilistic model checking to rigorously compute our proposed metric. All our claims are backed by detailed case studies and experiments.

The shared memory model matches important classes of systems deployed over dynamic networks, as for example, fault-tolerant and high available data centric services. Consensus is a fundamental building block able to realize such reliable distributed systems. Unlike the classical setting where the full set of participants and their identities are known to every process, dynamic networks preclude such global knowledge to be available. In this paper, we investigate and present protocols to solve fault-tolerant consensus in an environment with unknown participants that communicate via shared memory.

We consider the problem of reliably broadcasting information in a multi hop asynchronous network that is subject to Byzantine failures. That is, some nodes of the network can exhibit arbitrary (and potentially malicious) behavior. Existing solutions provide deterministic guarantees for broadcasting between all correct nodes, but require that the communication network is highly-connected (typically, 2k+1 connectivity is required, where k is the total number of Byzantine nodes in the network). In this paper, we investigate the possibility of Byzantine tolerant reliable broadcast between most correct nodes in low-connectivity networks (typically, networks with constant connectivity). In more details, we propose a new broadcast protocol that is specifically designed for low-connectivity networks. We provide sufficient conditions for correct nodes using our protocol to reliably communicate despite Byzantine participants. We present experimental results that show that our approach is especially effective in low-connectivity networks when Byzantine nodes are randomly distributed.

The growth of User-Generated Content (UGC) traffic makes the understanding of its nature a priority for network operators, content providers and equipment suppliers. In this paper, we study a four-month dataset that logs all video requests to DailyMotion made by a fixed subset of users. We were able to infer user sessions from raw data, to propose a Markovian model of these sessions, and to study video popularity and its evolution over time. The presented results are a first step for synthesizing an artificial (but realistic) traffic that could be used in simulations or experimental testbeds.

Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permit to cope with arbitrary malicious behaviors. Combining these two properties proved difficult: it is impossible to contain the spatial impact of Byzantine nodes in a self-stabilizing context for global tasks such as tree orientation and tree construction. We present and illustrate a new concept of Byzantine containment in stabilization. Our property, called Strong Stabilization enables to contain the impact of Byzantine nodes if they actually perform too many Byzantine actions. We derive impossibility results for strong stabilization and present strongly stabilizing protocols for tree orientation and tree construction that are optimal with respect to the number of Byzantine nodes that can be tolerated in a self-stabilizing context.

We propose a new approach to specifying and reasoning about forward recovery fault tolerant programs. We call it \emph{ideal stabilization}. The program is ideally stabilizing if its every state is legitimate. Ideal stabilization allows the specification designer to prescribe, with arbitrary degree of precision, not only the fault-free program behavior but also its recovery operation. Unlike the classic variant, ideal stabilization is particularly suitable for program composition. Specifications may or may not mention all possible states. We identify approaches to designing ideal stabilization to both classes of specifications. For the first class, we state the necessary condition for an ideally stabilizing solution. On the basis of this condition we prove that there is no ideally stabilizing solution to the leader election problem. We illustrate the utility of the concept of ideal stabilization by providing examples of well-known programs and proving them ideally stabilizing. Specifically, we prove ideal stabilization of the conflict manager, the alternator, the propagation of information with feedback and the alternating bit protocol.

Containment of application execution is a key security feature of operating systems. Without strong containment, an attacker who compromises one process may take control of the whole machine. Virtualization technology has been widely used in server systems to strongly isolate various applications or services in different virtual machines; its usage in desktop systems which are much more interactive (interactions with the user and between applications) is a challenging task. In this paper we describe SAFE-OS, a desktop operating system using virtualization technology. SAFE-OS provides a high level of isolation between processes while maintaining a standard user interface that abstracts the underlying complexity.

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. In this paper, we consider the problem of constructing self-stabilizingly a locally maximizable task (such as constructing a maximal independent set, a maximal matching, or a grundy coloring) in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, deterministic self-stabilization of this problem is impossible. Also, the silence property (i.e. having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols. On the positive side, we present a series of generic protocols that can be instantiated for all considered locally maximizable tasks. First, we design a deterministic protocol for arbitrary unidirectional networks with unique identifiers that exhibits polynomial space and time complexity in asynchronous scheduling. We complement the study with probabilistic protocols for the uniform case: the first probabilistic protocol requires infinite memory but copes with asynchronous scheduling, while the second probabilistic protocol has polynomial space complexity but can only handle synchronous scheduling. Both probabilistic solutions have expected polynomial time complexity.

International audience

In this brief announcement, we discuss the trade-off between the locality of information and the optimality of convergence for self-stabilization. We define the optimality of convergence, called monotonic stabilization, and propose a new metrics for the locality of information to achieve monotonic stabilization. Then, we examine the locality of many well-known distributed problems.

Recent advances in wireless sensor networks show an expansion both in the size of the network and in the variety of the applications that are to be executed. In this context, wireless network simulators play a key role in the design, development and testing of new wireless sensor networks applications and protocols. Most of the currently available wireless sensor network simulators work well for small to medium sized networks yet fail to scale to really large networks, mainly due to their single desktop machine architecture and its limited resources. In this paper, we present XS-WSNet, a wireless sensor network simulator that is designed with extreme scalability as a prime objective. First, we distribute the simulated wireless sensor network nodes on a variety of actual machines that communicate through a wired network. A large-scale simulation is then emulated by several smaller scale simulations that run concurrently and collaboratively. As smaller instances of simulations running on different machines usually induce asynchrony and non-determinism in the whole system, we also propose a distributed synchronization protocol, responsible for simulation accuracy in some simulation models. Our implementation (both asynchronized and synchronized versions) of XS-WSNet is fully evaluated in various contexts using a scalable benchmark application. Against its single machine version, the distributed simulator provides sensible matching results, exhibits both scale-up and speed-up of the simulation, and performs with linear slowdown with up to ten million simulated nodes.

In this paper, our focus is to lower the communication complexity of self-stabilizing protocols below the need of checking every neighbor forever. Our contribution is threefold: (i) We provide new complexity measures for communication efficiency of self-stabilizing protocols, especially in the stabilized phase or when there are no faults, (ii) On the negative side, we show that for non-trivial problems such as coloring, maximal matching, and maximal independent set, it is impossible to get (deterministic or probabilistic) self-stabilizing solutions where every participant communicates with less than every neighbor in the stabilized phase, and (iii) On the positive side, we present protocols for maximal matching and maximal independent set such that a fraction of the participants communicates with exactly one neighbor in the stabilized phase.

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the systems recovers from this catastrophic situation without external intervention in finite time. Uni-directional networks preclude many common techniques in self-stabilization from being used, such as preserving local predicates. In this paper, we investigate the intrinsic complexity of achieving self-stabilization in unidirectional anonymous general networks, and focus on the classical vertex coloring problem. Specifically, we prove a lower bound of n states per process (where n is the network size) and a recovery time of at least n(n-1)/2 actions in total. We also provide a deterministic algorithm with matching upper bounds that performs in arbitrary unidirectional anonymous graphs.

We generalize the classic dining philosophers problem to separate the conflict and communication neighbors of each process. Communication neighbors may directly exchange information while conflict neighbors compete for the access to the exclusive critical section of code. This generalization is motivated by a number of practical problems in distributed systems including problems in wireless sensor networks. We present a self-stabilizing deterministic algorithm— GDP that solves this generalized problem. Our algorithm is terminating. We formally prove GDP correct and evaluate its performance. We extend the algorithm to handle a similarly generalized drinking philosophers and the committee coordination problem. We describe how GDP can be implemented in wireless sensor networks and demonstrate that this implementation does not jeopardize its correctness or termination properties.

In this article, we quantify the amount of “practical” information (i.e., views obtained from the neighbors, colors attributed to the nodes and links) to obtain “theoretical” information (i.e., the local topology of the network up to distance k ) in anonymous networks. In more detail, we show that a coloring at distance 2 k + 1 is necessary and sufficient to obtain the local topology at distance k that includes outgoing links. This bound drops to 2 k when outgoing links are not needed. A second contribution of this article deals with color bootstrapping (from which local topology can be obtained using the aforementioned mechanisms). On the negative side, we show that ( i ) with a distributed daemon, it is impossible to achieve deterministic color bootstrap, even if the whole network topology can be instantaneously obtained, and ( ii ) with a central daemon, it is impossible to achieve distance m when instantaneous topology knowledge is limited to m − 1. On the positive side, we show that ( i ) under the k -central daemon, deterministic self-stabilizing bootstrap of colors up to distance k is possible provided that k -local topology can be instantaneously obtained, and ( ii ) under the distributed daemon, probabilistic self-stabilizing bootstrap is possible for any range.

We pose and study the problem of Byzantine-robust topology discovery in an arbitrary asynchronous network. The problem is an abstraction of fault-tolerant routing. We formally state the weak and strong versions of the problem. The weak version requires that either each node discovers the topology of the network or at least one node detects the presence of a faulty node. The strong version requires that each node discovers the topology regardless of faults. We focus on non-cryptographic solutions to these problems. We explore their bounds. We prove that the weak topology discovery problem is solvable only if the connectivity of the network exceeds the number of faults in the system. Similarly, we show that the strong version of the problem is solvable only if the network connectivity is more than twice the number of faults. We present solutions to both versions of the problem. The presented algorithms match the established graph connectivity bounds. The algorithms do not require the individual nodes to know either the diameter or the size of the network. The message complexity of both programs is low polynomial with respect to the network size. We describe how our solutions can be extended to add the property of termination, handle topology changes, and perform neighborhood discovery.

Self-stabilization is a strong property which guarantees that a network always resume a correct behavior starting from an arbitrary initial state. Weaker guarantees have later been introduced to cope with impossibility results: probabilistic stabilization only gives probabilistic convergence to a correct behavior. Also, weak-stabilization only gives the possibility of convergence. In this paper, we investigate the relative power of weak, self, and probabilistic stabilization, with respect to the set of problems that can be solved. We formally prove that in that sense, weak stabilization is strictly stronger that self-stabilization. Also, we refine previous results on weak stabilization to prove that, for practical schedule instances, a deterministic weak-stabilizing protocol can be turned into a probabilistic self-stabilizing one. This latter result hints at more practical use of weak-stabilization, as such algorithms are easier to design and prove than their (probabilistic) self-stabilizing counterparts.

In this announcement, we report recent results where we address the open problem of snap-stabilization in message-passing systems.

Stabilizing distributed systems expect all the component processes to run predefined programs that are externally mandated. In Internet scale systems, this is unrealistic, since each process may have selfish interests and motives related to maximizing its own payoff. This article formulates the problem of selfish stabilization to show how competition blends with cooperation in a stabilizing environment.

In self-organizing systems, such as mobile ad-hoc and peer-to-peer networks, consensus is a fundamental building block to solve agreement problems. It contributes to coordinate actions of nodes distributed in an ad-hoc manner in order to take consistent decisions. It is well known that in classical environments, in which entities behave asynchronously and where identities are known, consensus cannot be solved in the presence of even one process crash. It appears that self-organizing systems are even less favorable because the set and identity of participants are not known. We define necessary and sufficient conditions under which fault-tolerant consensus become solvable in these environments. Those conditions are related to the synchrony requirements of the environment, as well as the connectivity of the knowledge graph constructed by the nodes in order to communicate with their peers.

In this paper, we specify the conflict manager abstraction. Informally, a conflict manager guarantees that any two nodes that are in conflict cannot enter their critical section simultaneously (safety), and that at least one node is able to execute its critical section (progress). The conflict manager problem is strictly weaker than the classical local mutual exclusion problem, where any node that requests to enter its critical section eventually does so (fairness). We argue that conflict managers are a useful mechanism to transform a large class of self-stabilizing algorithms that operate in an essentially sequential model, into self-stabilizing algorithm that operate in a completely asynchronous distributed model. We provide two implementations (one deterministic and one probabilistic) of our abstraction, and provide a composition mechanism to obtain a generic transformer. Our transformers have low overhead: the deterministic transformer requires one memory bit, and guarantees time overhead in order of the network degree, the probabilistic transformer does not require extra memory. While the probabilistic algorithm performs in anonymous networks, it only provides probabilistic stabilization guarantees. In contrast, the deterministic transformer requires initial symmetry breaking but preserves the original algorithm guarantees.

One of the topics of paramount importance in the development of cluster and grid middleware is the impact of faults since their occurrence in grid infrastructures and in large-scale distributed systems is common. MPI (message passing interface) is a popular abstraction for programming distributed and parallel applications. FAIL (FAult Injection Language) is an abstract language for fault occurrence description capable of expressing complex and realistic fault scenarios. In this paper, we investigate the possibility of using FAIL to inject faults in a fault-tolerant MPI implementation. Our middleware, FAIL-MPI, is used to carry quantitative and qualitative faults and stress testing

In a network consisting of several thousands computers, the occurrence of faults is unavoidable. Being able to test the behaviour of a distributed program in an environment where we can control the faults (such as the crash of a process) is an important feature that matters in the deployment of reliable programs. In this paper, we investigate the possibility of injecting software faults in distributed Java applications. Our scheme is by extending the FAIL-FCI software. It does not require any modification of the source code of the application under test, while retaining the possibility to write high level fault scenarios. As a proof of concept, we use our tool to test FreePastry, an existing Java implementation of a distributed hash table (DHT), against node failures.

A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate. The mutual exclusion problem is fundamental in distributed computing, since it allows processors competing to access a shared resource to be able to synchronize and get exclusive access to the resource (i.e. execute their critical section). It is well known that providing self-stabilization in general uniform networks (e.g. anonymous rings of arbitrary size) can only be probabilistic. However, all existing uniform probabilistic self-stabilizing mutual exclusion algorithms designed to work under an unfair distributed scheduler (that may choose processors to execute their code in an arbitrary manner) suffer from the following common drawback: once stabilized, there exists no upper bound on time between two successive executions of the critical section at a given processor. In this paper, we present the first self-stabilizing algorithm that guarantees such a bound (O(n3), where n is the network size) while working using an unfair distributed scheduler. Our algorithm works in an anonymous unidirectional ring of any size and has a polynomial expected stabilization time.

Wormhole routing is the most common in parallel architecture in which messages are sent in small fragments called flits. It is a lightweight and efficient method of routing messages between parallel processors. Self-stabilization is a technique that guarantees tolerance to transient faults (e.g. memory corruption or communication hazard) for a given protocol. Self-stabilization guarantees that the network recovers to a correct behavior infinite time, without the need for human intervention. Self-stabilization also guarantees the safety property, meaning that once the network is in a legitimate state, it will remain there until another fault occurs. This paper presents the first self-stabilizing network algorithm in the wormhole routing model, using the unidirectional ring topology. Our solution benefits from wormhole routing by providing high throughput and low latency, and front self-stabilization by ensuring automatic resilience to all possible transient failures.

It is desirable that the smaller the number of faults hitting a network, the faster a network protocol recovers. We study the scenario where up to k (for a given k) faults hit processors of a synchronous distributed system by corrupting their state undetectably. In this context, we show that the well known step complexity model is not appropriate to study time complexity of time-adaptive protocols (i.e. protocols that recover from memory corruption in a time that depends only on the number of faults and not on the network size). In more detail, we prove that for nontrivial dynamic problems (such as token passing), there exists a lower bound of /spl Omega/(D) (where D is the network diameter) steps on the stabilization time even when as few as 1 corruption can hit the system. This implies that there exists no time adaptive protocol for those problems in the asynchronous step model, even if we assume that the number of faults is bounded by 1 and that the scheduling of the processors is almost synchronous (between two actions of an enabled processor any other processor may execute at most one action).

A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. The l-mutual exclusion is a generalization of the fundamental problem of mutual exclusion: the system has to guarantee the fair sharing of a resource that can be used by l processors simultaneously. We present a space efficient solution to the l-mutual exclusion problem that performs on uniform unidirectional ring networks and that is self-stabilizing. Our solution improves the space complexity of previously known approaches by a factor of min(n/sup 2//spl times/log(n), 1/l/spl times/log/sup l-1/ (n)), while retaining none of their drawbacks in terms of system hypothesis (we support unfair scheduler and ensure strong correctness) or specification verification (we guarantee high level 2-mutual exclusion). When l is fixed, the space complexity at each node is constant in average, making our approach suitable for scalable systems.

A self-stabilizing algorithm, regardless of the initial system state, converges infinite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. Mutual exclusion is fundamental in the area of distributed computing, by serializing the accesses to a common shared resource. All existing probabilistic self-stabilizing mutual exclusion algorithms designed to work under an unfair distributed scheduler suffer from the following common drawback: Once stabilized, there exists no upper bound of time between two executions of the critical section at a given node. We present the first probabilistic self-stabilizing algorithm that guarantees such a bound (O(n/sup 3/), where n is the network size) while working using an unfair distributed scheduler. As the scheduling adversary gets weaker the bound gets better. Our algorithm works in an anonymous unidirectional ring of any size and has a O(n/sup 3/) expected stabilization time.

Proposes a self-stabilizing synchronization technique, called the Neighborhood Synchronizer (/spl Nscr//spl Sscr/), that synchronizes nodes with their neighbors in a tree network. The /spl Nscr//spl Sscr/ scheme has an extremely small memory requirement-only one bit per processor. Algorithm /spl Nscr//spl Sscr/ is inherently self-stabilizing. We apply our synchronizer to design a broadcasting algorithm /spl Bscr//spl Ascr/ in a tree network. Algorithm /spl Bscr//spl Ascr/ is also inherently self-stabilizing and needs only 2h+2m-1 rounds to broadcast m messages, where h is the height of the tree.

We propose a self-stabilizing synchronization technique, called the global rooted synchronization, that synchronizes processors in a tree network. This synchronizer converts a synchronous protocol for tree networks into a self-stabilizing version. The synchronizer requires only O(1) memory (other than the memory needed to maintain the tree) at each node regardless of the size of the network, stabilizes in O(h) time, where h is the height of the tree, and does not invoice any global operations. Applications of this technique are presented.