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.

On behalf of the entire research track program committee, it is our great pleasure to present you to the research track of the 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2023). The program includes very solid contributions addressing diverse aspects of system robustness (including reliability, dependability, safety and security) across multiple domains including hardware, software, networks, cyber-physical and autonomous systems, artificial intelligence and machine learning. The program of the research track consists of 47 contributions, which consist of 40 research papers, five practical experience reports, and two tool papers.

We propose a novel algorithm to solve multi-robot motion planning (MRMP) rapidly, called Simultaneous Sampling-and-Search Planning (SSSP). Conventional MRMP studies mostly take the form of two-phase planning that constructs roadmaps and then finds inter-robot collision-free paths on those roadmaps. In contrast, SSSP simultaneously performs roadmap construction and collision-free pathfinding. This is realized by uniting techniques of single-robot sampling-based motion planning and search techniques of multi-agent pathfinding on discretized spaces. Doing so builds the small search space, leading to quick MRMP. SSSP ensures finding a solution eventually if exists. Our empirical evaluations in various scenarios demonstrate that SSSP significantly outperforms standard approaches to MRMP, i.e., solving more problem instances much faster. We also applied SSSP to planning for 32 ground robots in a dense situation.

We study the problem Rendezvous for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors [10], [21]. With external-lights, robots can only observe the state of the lights of other robots. With internal-lights, robots can only observe their own light, and full-lights combine both. This paper focuses on robots with external-lights in asynchronous settings and considers a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and 3 colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors [10]. This paper, extending the impossibility result, shows that there exists no L-algorithm in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC in which no robot can execute more than 1 Look operation between the Look and its subsequent Compute operations of another robot. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.

This study examines a novel planning problem for multiple agents that cannot share holding resources, namedOffline Time-Independent Multiagent Path Planning (OTIMAPP). Given a graph and a set of start-goal pairs, the problem to be addressed is assigning a path to each agent, such that every agent eventually reaches its destination without blocking others, regardless of when each agent starts and finishes each own action. This motivation stems from timing uncertainties, including the reality gaps between planning and robot execution. In contrast to conventional solution, concepts of multirobot path planning that rely on timings, once OTIMAPP solutions are obtained, they can be executed without any synchronization between robot actions. Moreover, there is a theoretical guarantee that all robots eventually reach their destinations, provided they avoid interrobot collisions. This study attempts to establish OTIMAPP both theoretically and practically. Specifically, we present a formalization of the problem, solution conditions based on a categorization of deadlocks, computational complexities showing that OTIMAPP is computationally intractable, practical relaxation of the solution concept, two algorithms to solve OTIMAPP based on multiagent pathfinding algorithms, empirical results showing large OTIMAPP instances can be solved to some extent, as well as robot demonstrations of asynchronous OTIMAPP execution.

This paper studies a novel planning problem for multiple agents that cannot share holding resources, named OTIMAPP (Offline Time-Independent Multi-Agent Path Planning). Given a graph and a set of start-goal pairs, the problem consists in assigning a path to each agent such that every agent eventually reaches their goal without blocking each other, regardless of how the agents are being scheduled at runtime. The motivation stems from the nature of distributed environments that agents take actions fully asynchronous and have no knowledge about those exact timings of other actors. We present solution conditions, computational complexity, solvers, and robotic applications.

In the Multi-Agent Path Finding (MAPF) problem, a set of agents moving on a graph must reach their own respective destinations without inter-agent collisions. In practical MAPF applications such as navigation in automated warehouses, where occasionally there are hundreds or more agents, MAPF must be solved iteratively online on a lifelong basis. Such scenarios rule out simple adaptations of offline compute-intensive optimal approaches; and scalable sub-optimal algorithms are hence appealing for such settings. Ideal algorithms are scalable, applicable to iterative scenarios, and output plausible solutions in predictable computation time. For the aforementioned purpose, this study presents Priority Inheritance with Backtracking (PIBT), a novel sub-optimal algorithm to solve MAPF iteratively. PIBT relies on an adaptive prioritization scheme to focus on the adjacent movements of multiple agents; hence it can be applied to several domains. We prove that, regardless of their number, all agents are guaranteed to reach their destination within finite time when the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle (e.g., biconnected). Experimental results covering various scenarios, including a demonstration with real robots, reveal the benefits of the proposed method. Even with hundreds of agents, PIBT yields acceptable solutions almost immediately and can solve large instances that other established MAPF methods cannot. In addition, PIBT outperforms an existing approach on an iterative scenario of conveying packages in an automated warehouse in both runtime and solution quality.

This article addresses novel real-valued consensus problems in the presence of malicious adversaries that can move within the network and induce faulty behaviors in the attacked agents. By adopting several mobile adversary models from the computer science literature, we develop protocols which can mitigate the influence of such malicious agents. The algorithms follow the class of mean subsequence reduced (MSR) algorithms, under which agents ignore the suspicious values received from neighbors during their state updates. Different from the static adversary models, even after the adversaries move away, the infected agents may remain faulty in their values, whose effects must be taken into account. We develop conditions on the network structures for both the complete and non-complete directed graph cases, under which the proposed algorithms are guaranteed to attain resilient consensus. The tolerance bound for network conditions becomes more strict as the adversaries are allowed to have more power. Extensive simulations are carried out over random graphs to verify the effectiveness of our approach when the information of the adversarial agents in terms of their models and numbers is unknown to the agents.

Typical Multi-agent Path Finding (MAPF) solvers assume that agents move synchronously, thus neglecting the reality gap in timing assumptions, e.g., delays caused by an imperfect execution of asynchronous moves. So far, two policies enforce a robust execution of MAPF plans taken as input: either by forcing agents to synchronize or by executing plans while preserving temporal dependencies. This paper proposes an alternative approach, called time-independent planning, which is both online and distributed. We represent reality as a transition system that changes configurations according to atomic actions of agents, and use it to generate a time-independent schedule. Empirical results in a simulated environment with stochastic delays of agents' moves support the validity of our proposal.

This paper presents a novel robot-environment interaction in navigation tasks such that robots have neither a representation of their working space nor planning function, instead, an active environment takes charge of these aspects. This is realized by spatially deploying computing units, called cells, and making cells manage traffic in their respective physical region. Different from stigmegic approaches, cells interact with each other to manage environmental information and to construct instructions on how robots move.As a proof-of-concept, we present an architecture called AFADA and its prototype, consisting of modular cells and robots moving on the cells. The instructions from cells are based on a distributed routing algorithm and a reservation protocol. We demonstrate that AFADA enables a robot to move efficiently in a dynamic environment that stochastic changes its topology, comparing to self-navigation by a robot itself. This is followed by several demos, including multi-robot navigation, highlighting the power of offloading both representation and planning from robots to the environment. We expect that the concept of AFADA contributes to developing the infrastructure for multiple robots because it can engage online and lifelong planning and execution.

We study the iterative refinement of path planning for multiple robots, known as multi-agent pathfinding (MAPF). Given a graph, agents, their initial locations, and destinations, a solution of MAPF is a set of paths without collisions. Iterative refinement for MAPF is desirable for three reasons: 1) optimization is intractable, 2) sub-optimal solutions can be obtained instantly, and 3) it is anytime planning, desired in online scenarios where time for deliberation is limited. Despite the high demand, this is under-explored in MAPF because finding good neighborhoods has been unclear so far. Our proposal uses a sub-optimal MAPF solver to obtain an initial solution quickly, then iterates the two procedures: 1) select a subset of agents, 2) use an optimal MAPF solver to refine paths of selected agents while keeping other paths unchanged. Since the optimal solvers are used on small instances of the problem, this scheme yields efficient-enough solutions rapidly while providing high scalability. We also present reasonable candidates on how to select a subset of agents. Evaluations in various scenarios show that the proposal is promising; the convergence is fast, scalable, and with reasonable quality.

Cooperative intelligent transportation systems (ITS) are used by autonomous vehicles to communicate with surrounding autonomous vehicles and roadside units (RSU). Current C-ITS applications focus primarily on real-time information sharing, such as cooperative perception. In addition to realtime information sharing, self-driving cars need to coordinate their action plans to achieve higher safety and efficiency. For this reason, this study defines a vehicles future action plan/path and designs a cooperative path-planning model at intersections using future path sharing based on the future path information of multiple vehicles. The notion is that when the RSU detects a potential conflict of vehicle paths or an acceleration opportunity according to the shared future paths, it will generate a coordinated path update that adjusts the speeds of the vehicles. We implemented the proposed method using the open-source Autoware autonomous driving software and evaluated it with the LGSVL autonomous vehicle simulator. We conducted simulation experiments with two vehicles at a blind intersection scenario, finding that each car can travel safely and more efficiently by planning a path that reflects the action plans of all vehicles involved. The time consumed by introducing the RSU is 23.0 % and 28.1 % shorter than that of the stand-alone autonomous driving case at the intersection.

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.

This paper presents a randomized self-stabilizing algorithm that elects a leader $r$ in a general $n$-node undirected graph and constructs a spanning tree $T$ rooted at $r$. The algorithm works under the synchronous message passing network model, assuming that the nodes know a linear upper bound on $n$ and that each edge has a unique ID known to both its endpoints (or, alternatively, assuming the $KT_{1}$ model). The highlight of this algorithm is its superior communication efficiency: It is guaranteed to send a total of $\tilde{O} (n)$ messages, each of constant size, till stabilization, while stabilizing in $\tilde{O} (n)$ rounds, in expectation and with high probability. After stabilization, the algorithm sends at most one constant size message per round while communicating only over the ($n - 1$) edges of $T$. In all these aspects, the communication overhead of the new algorithm is far smaller than that of the existing (mostly deterministic) self-stabilizing leader election algorithms. The algorithm is relatively simple and relies mostly on known modules that are common in the fault free leader election literature; these modules are enhanced in various subtle ways in order to assemble them into a communication efficient self-stabilizing algorithm.

The Multi-agent Path Finding (MAPF) problem consists in all agents having to move to their own destinations while avoiding collisions. In practical applications to the problem, such as for navigation in an automated warehouse, MAPF must be solved iteratively. We present here a novel approach to iterative MAPF, that we call Priority Inheritance with Backtracking (PIBT). PIBT gives a unique priority to each agent every timestep, so that all movements are prioritized. Priority inheritance, which aims at dealing effectively with priority inversion in path adjustment within a small time window, can be applied iteratively and a backtracking protocol prevents agents from being stuck. We prove that, regardless of their number, all agents are guaranteed to reach their destination within finite time, when the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle of length 3 or more (e.g., biconnected). Our implementation of PIBT can be fully decentralized without global communication. Experimental results over various scenarios confirm that PIBT is adequate both for finding paths in large environments with many agents, as well as for conveying packages in an automated warehouse.

Ensuring proper quality of service (QoS) is essential for cloud service providers and customers alike. To this end, cloud systems must rely as much as possible on automated and efficient methods of monitoring, introspection, and recovery. In particular, automated recovery is essential to ensure long-term reliability and availability because human intervention is too slow and not every situation can be anticipated. In turn, automated recovery requires both efficient monitoring and accurate identification of root causes to ensure that the same causes will not lead to failures in the future. Current cloud systems use an in-memory time-series database for dynamic analysis or aggregation purposes. When done at all, root cause analysis serves the convenience of reporting and does not need to be very accurate. As a result, recent studies lack details on how to accurately find root causes from time-series monitoring data. This study proposes a novel event-driven monitoring rule inference method based on dynamic case-based reasoning and shape-based root cause analysis. It is designed for autonomous recovery so as to guarantee long-term QoS of cloud systems. The accuracy and performance of the approach are evaluated using realistic monitoring data combining more than a decade of experience as a major cloud service provider (Yahoo). The results show that our approach makes effective use of monitoring data in improving overall QoS and hence opens interesting directions.

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 the Rendezvous problem for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors. If robots can observe not only their own lights but also other robots' lights, their lights are called full-light. If robots can only observe the state of other robots' lights, the lights are called external-light. This paper focuses on robots with external-lights in asynchronous settings and a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and three colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors. In this paper, extending the impossibility result, we show that there exist no L-algorithms in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC and other robots can execute at most one Look operation between the Look operation of a robot and its subsequent Compute operation. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.

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.

This paper extends the core model of a recent component-based reliability prediction approach to offer an explicit and flexible definition of reliability-relevant behavioral aspects (i.e. error detection and error handling) of software fault tolerance mechanisms, and an efficient evaluation of their reliability impact in the dependence of the whole system architecture and usage profile. Our approach is validated with the reporting service of a document exchange server, by modeling the reliability, conducting a reliability prediction and sensitivity analyses, and demonstrating its ability to support design decisions.

Anonymous mobile robots are often classified into synchronous, semi-synchronous, and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. (All patterns formable with memory are formable without memory for synchronous robots, and little is known for asynchronous robots.) However, the gathering problem for two semi-synchronous robots without memory (called oblivious robots in this paper) is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely, static compasses with (possibly incorrect) constant bearings and dynamic compasses the bearings of which can change arbitrarily (immediately before a new look-compute-move cycle starts and after the last cycle ends). For each of the combinations of robot and compass models, we establish the condition on deviation $\phi$ that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: $\phi < \pi/2$ for semi-synchronous and asynchronous robots with static compasses, $\phi < \pi/4$ for semi-synchronous robots with dynamic compasses, and $\phi < \pi/6$ for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

Consider a system composed of mobile robots (mobile sensors) that move on the plane, each of which independently executing its own instance of an algorithm. Given a desired geometric pattern, the flocking problem consists in ensuring that the robots form this pattern and maintain it while moving together on the plane. In this paper, we look at the flocking problem in the presence of faulty robots, where the desired pattern is a regular polygon. We propose a distributed algorithm assuming a semi-synchronous model with a k-bounded scheduler, in the sense that no robot is activated more than k times between any two consecutive activations of any other robot. The algorithm is composed of three parts: failure detector, ranking assignment and flocking algorithm. The rank assignment part is to provide a persistent ranking for the robots in the system. Then, the failure detector can select the set of correct robots from all the robots. Finally, the flocking algorithm handles the movement and reconfiguration of the flock, while maintaining the desired shape. The difficulty of the problem comes from the combination of the three parts together with the necessity to prevent collision and allow the rotation of the flock. Different from the existed work, our algorithm can make the formation rotate freely and has good maneuverability.

Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some location not determined in advance, and without the help of some global coordinate system. While very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it has been proved that the gathering problem is solvable in asynchronous model with oblivious (i.e., memory-less) robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass, or when they cannot detect multiplicity. In this article, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in the semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, we show that our algorithm solves the gathering problem for at most three robots in the asynchronous model. Our algorithm is intrinsically self-stabilizing.

In this paper, we present an anonymous, stable, communication efficient, stabilizing leader election algorithm that works using anonymous communication primitives. The algorithm offers properties similar to that of the Omega failure detector, with the added property of totally ordering the sequence of proposed leaders. The algorithm does not need to know beforehand the identity or the number of processes in the system, and operates using a constant amount of memory. We present the algorithm, discuss performance issues and optimizations and present experimental results of a prototype implementation.

The paper presents a fail-safe mobility management and a collision prevention platform for a group of asynchronous cooperative mobile robots. The fail-safe platform consists of a time-free collision prevention protocol, which guarantees that no collision can occur between robots, independently of timeliness properties of the system, and even in the presence of timing errors in the environment. The collision prevention protocol is based on a distributed path reservation system. Each robot in the system knows the composition of the group, and can communicate with all robots of the group. A performance analysis of the protocol provides insights for a proper dimensioning of system parameters in order to maximize the average effective speed of the robots.

The scheduling of real-time tasks with fault-tolerant requirements has been an important problem in multiprocessor systems. Primary-backup (PB) approach is often used as a fault-tolerant technique to guarantee the deadlines of tasks despite the presence of faults. In this paper we propose a PB-based task scheduling approach, wherein an allocation parameter is used to search the available time slots for a newly arriving task, and the previously scheduled tasks can be rescheduled when there is no available time slot for the newly arriving task. In order to improve the schedulability we extend the existing PB-overloading and the Backup-backup (BB) overloading. Our proposed task scheduling algorithm is compared with some existing scheduling algorithms in the literature through simulation studies. The results have shown that the task rejection ratio of our real-time task scheduling algorithm is lower than the compared algorithms.

This paper presents a fully decentralized distributed path reservation system for a group of asynchronous cooperative mobile robots. The protocol assumes a mobile ad hoc network formed by the robots themselves, and takes advantage of the inherent locality of the problem in order to reduce communication. In contrast with other work, our protocol requires neither initial nor complete knowledge of the composition of the group. A performance analysis of the protocol provides insights for a proper dimensioning of system parameters in order to maximize the average effective speed of the robots

This paper compares several parametric and adaptive failure detection schemes in terms of their respective QoS. We introduce an improvement over existing methods, and evaluate their benefits. First, we propose an optimization to enhance the adaptation of Chen's FD, which significantly improves QoS, especially in the aggressive range and when the network is unstable. Second, we address the problem of most adaptive schemes, namely their need for a large window of samples. We study a scheme that is designed to use a fixed and very limited amount of memory for each monitored-monitoring link. Our experimental results over several kinds of networks (Cluster, WiFi, wired LAN, WAN) show that the properties of the existing adaptive FDs, and that the optimization is reasonable and acceptable. Furthermore, the extensive experimental results show what is the effect of memory size on the overall QoS of each adaptive FD.

In this study, we focus on a self-deployment problem for a swarm of autonomous mobile robots that can be used to build a sensor networking infrastructure with equilateral triangle lattice configurations. In order to deploy the swarm, this paper proposes a self-stabilizing distributed self- deployment algorithm under a robot model with the following features: no identification numbers, no common coordinates, no predetermined leader, no memory for past actions and implicit communication. Regardless of the restricted model, our proposed algorithm based on local interactions provides a solution for the self-deployment problem. Moreover, the algorithm provides robust capability of swarm connectivity in spite of loss of several robots. We discuss in details the features of the algorithm, including self-organization, self-stabilization, and robustness. A simulation study demonstrates the validity of the algorithm.

In multiprocessor systems, redundant scheduling is a technique that trades processing power for increased reliability. One approach, called primary-backup task scheduling, is often used in real-time multiprocessor systems to ensure that deadlines are met in spite of faults. Briefly, it consists in scheduling a secondary task conditionally, in such a way that the secondary task actually gets executed only if the primary task (or the processor executing it) fails to terminate properly. Doing so avoids wasting CPU resources in the failure-free case, but primary and secondary tasks must then compete for resources in case of failure. To overcome this, overloading strategies, such as primary and backup overloading (PB) and backup-backup overloading (BB), aim at improving schedulability while retaining a certain level of reliability. In this paper, we propose a hybrid overloading technique based on extended PB overloading, which combines advantages of both PB and BB overloading. The three overloading strategies are then compared through a stochastic analysis, and by simulating them under diverse system conditions. The analysis shows that hybrid overloading provides an excellent tradeoff between schedulability and reliability.

End-to-end consensus ensures delivery of the same value to the application layer running in distributed processes. Deliveries that have not been acknowledged by the application before a failure are delivered again. End-to-end primitives are important for applications that need to enforce persistency. We present an algorithm that solves the end-to-end consensus problem. Our approach is to build end-to-end consensus using a new type of communication channels, end-to-end channels

In this paper, we present the SNMP-FD service, a novel failure detection service entirely based on the Simple Network Management Protocol (SNMP). This approach promises better interoperability with external tools and failure information sources, including network equipment and cluster management tools. We first show how the SNMP standard can be used to build a failure detection service. We describe the already standardized interfaces that can be reused and introduce the interfaces that need to be added. SNMP is used extensively in the service for messaging, process status description, configuration, services statistics and delivering failure detection information to applications. We then present our implementation and an evaluation of performance and quality of service

In this paper, we consider a distributed system that consists of a group of teams of worker robots that rely on physical robot messengers for the communication between the teams. Unlike traditional distributed systems, there is a finite amount of messengers in the system, and thus a team can send messages to other teams only when some messenger robot is available locally. It follows that a careful management of the messengers is necessary to avoid the starvation of some teams. Concretely, the paper proposes algorithms to provide group membership and view synchrony among robot teams. We look at the problem in the face of failures, in particular when a certain number of messenger robots can possibly crash.

For many years, people have been advocating the development of failure detection as a basic service, but, unfortunately, without meeting much success so far. We believe that this comes from the fact that important system engineering issues have not yet been addressed adequately, thus preventing the definition of a truly generic service. Ultimately, our goal is to define a service that is both simple and expressive, yet powerful enough to support the requirements of many distributed applications. To this end, we consider an alternative interaction model between the service and the applications, called accrual failure detectors. Roughly, an accrual failure detector associates to each process a real value representing a suspicion level, instead of the traditional binary information (i.e., trust vs. suspect). In this paper, we provide a rigorous definition for accrual failure detectors, demonstrate that changing the interaction model leads to no loss in computational power, discuss quality of service issues, and present several possible implementations.

This paper surveys the state of the art of agentbased fault tolerance techniques. Existing mobile agent-based fault-tolerant techniques are identified on prevent mobile agents from being blocked by a failure.

In this paper, we propose a novel active queue management (AQM) scheme based on the Random Early Detection (RED) of the loss ratio and the total sending rate control, called LRC-RED, to regulate the queue length with small variation and to achieve high utilization with small packet loss. This scheme measures the latest packet loss ratio, and uses it and the total sending rate as complements to queue length in order to dynamically adjust packet drop probability. Further, we also provide the design rules for this scheme based on the well-known TCP control model. On the basis of the design rules, we develop a simple, scalable and systematic rule for tuning the control parameters which can be adaptive to dynamic network conditions. Through ns 2 simulations, we show the faster response time and better robustness of the proposed LRC-RED as compared with the Loss Ratio based RED (LRED) [5] algorithm.

As two different research topics with much overlap, dependability and security of computer/communication systems have respective long and rich history. The development of the techniques for their modeling and analysis thus have followed distinct but convergent paths. In essence, diverse attributes and the fundamental difference between the nature of the failures bring in different concerns for dependability and security analysis during their modeling process. Taking the understanding of the basic concepts/attributes as a point of departure, this paper intend to carry out a comparative study on the analytical models of computer system dependability and security. Also, by examining the state-of-the-art quantitative techniques and sound modeling methodologies for dependability evaluation, e.g., combinatorial and stochastic methods, we attempt to explore why and how those methods can be extended to evaluate computer system security. Furthermore, we take our developed autonomic detection coordinator (for intrusion detection) as a case study to conduct the comparative analysis.

The detection of failures is a fundamental issue for fault-tolerance in distributed systems. Recently, many people have come to realize that failure detection ought to be provided as some form of generic service, similar to IP address lookup or time synchronization. However, this has not been successful so far; one of the reasons being the fact that classical failure detectors were not designed to satisfy several application requirements simultaneously. We present a novel abstraction, called accrual failure detectors, that emphasizes flexibility and expressiveness and can serve as a basic building block to implementing failure detectors in distributed systems. Instead of providing information of a binary nature (trust vs. suspect), accrual failure detectors output a suspicion level on a continuous scale. The principal merit of this approach is that it favors a nearly complete decoupling between application requirements and the monitoring of the environment. In this paper, we describe an implementation of such an accrual failure detector, that we call the /spl phi/ failure detector. The particularity of the /spl phi/ failure detector is that it dynamically adjusts to current network conditions the scale on which the suspicion level is expressed. We analyzed the behavior of our /spl phi/ failure detector over an intercontinental communication link over a week. Our experimental results show that if performs equally well as other known adaptive failure detection mechanisms, with an improved flexibility.

While group communication systems have been proposed for some time, they are still not used much in actual systems. We believe that one reason for this is the lack of standardisation of group communication system interfaces. The paper proposes an architecture, using the standard decomposition into services, where services are based on standard interfaces: both interactions between services and interactions with the application use existing, open standards. A decomposition of the group communication into services is presented, along with a description of applicable standards. As an example, a group membership service based on the LDAP standard is discussed.

This paper investigates the two main and seemingly antagonistic approaches to broadcasting messages reliably in fault-tolerant distributed systems: the approach based on reliable broadcast, and that based on view synchronous communication (or VSC for short). While VSC does more than reliable broadcast, this has a cost. We show that this cost can be reduced by exploiting the difference between input-triggered and output-triggered suspicions, and by replacing the standard VSC broadcast primitive by two broadcast primitives, one sensitive to input-triggered suspicions, and the other sensitive to output-triggered suspicions.

The paper considers a consensus algorithm for an asynchronous system augmented with failure detectors, and analyzes the impact on its termination time of various implementations of failure detectors. The study shows that the design of fault-tolerant distributed algorithms in the asynchronous system model augmented with failure detectors is orthogonal to implementing the actual failure detectors. This nicely decouples logical issues (proof of correctness) from engineering issues (e.g., performance and timing constraints).

Fault tolerance can be achieved in distributed systems by replication. However Fischer, Lynch and Paterson (1985) have proven an impossibility result about consensus in the asynchronous system model, and similar impossibility results exist for atomic broadcast and group membership. We investigate, with the aid of an experiment conducted in a LAN, whether these impossibility results set limits to the robustness of a replicated server exposed to extremely high loads. The experiment consists of client processes that send requests to a replicated server (three replicas) using an atomic broadcast primitive. It has parameters that allow us to control the load on the hosts and the network, as well as the timeout value used by our heartbeat failure detection mechanism. Our main observation is that the atomic broadcast algorithm never stops delivering messages, not even under arbitrarily high load and very small timeout values (1 ms). So, by trying to illustrate the practical impact of impossibility results, we discovered that we had implemented a very robust replicated service.

Resource contention is widely recognized as having a major impact on the performance of distributed algorithms. Nevertheless, the metrics that are commonly used to predict their performance take little or no account of contention. We define two performance metrics for distributed algorithms that account for network contention as well as CPU contention. We then illustrate the use of these metrics by comparing four atomic broadcast algorithms, and show that our metrics allow for a deeper understanding of performance issues than conventional metrics.

This paper presents the semi-passive replication technique, a variant of passive replication, that can be implemented in the asynchronous system model without requiring a membership service to agree on a primary. Passive replication is a popular replication technique since it can tolerate non-deterministic servers (e.g., multi-threaded servers) and uses little processing power when compared to other replication techniques. However, passive replication suffers from a high reconfiguration cost in case of the failure of the primary. The semi-passive replication technique presented in the paper benefits from the same advantages as passive replication. However, since it does not require a group membership service, semi-passive replication has a considerably lower cost in case of failure. As explained in the paper, this technique can benefit from an aggressive time-out value significantly lower than what a group membership allows. As a result, the reaction to crashes is greatly improved. The semi-passive replication algorithm uses failure detectors. The algorithm given in the paper is analysed in the failure free case and in the case of one server crash. The response time (for the client) of these two scenarios is analysed through simulation.