main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2016, held in Lyon, France, in November 2016.
This year the Program Committee was organized into three groups reflecting the major trends related to self-* systems: (a) Self-* and Autonomic Computing, (b)Foundations, and (c) Networks, Multi-Agent Systems, and Mobility.

Inhaltsverzeichnis

Leader Election in Rings with Bounded Multiplicity (Short Paper)

We study leader election in unidirectional rings of homonym processes that have no a priori knowledge on the number of processes. We show that message-terminating leader election is impossible for any class of rings $$\mathcal K_k$$ with bounded multiplicity $$k \ge 2$$. However, we show that process-terminating leader election is possible in the sub-class $$\mathcal U^* \cap \mathcal K_k$$, where $$\mathcal U^*$$ is the class of rings which contain a process with a unique label.

Karine Altisen, Ajoy K. Datta, Stéphane Devismes, Anaïs Durand, Lawrence L. Larmore

Synchronous Gathering Without Multiplicity Detection: A Certified Algorithm

In mobile robotic swarms, the gathering problem consists in coordinating all the robots so that in finite time they occupy the same location, not known beforehand. Multiplicity detection refers to the ability to detect that more than one robot can occupy a given position. When the robotic swarm operates synchronously, a well-known result by Cohen and Peleg permits to achieve gathering, provided robots are capable of multiplicity detection.We present a new algorithm for synchronous gathering, that does not assume that robots are capable of multiplicity detection, nor make any other extra assumption. Unlike previous approaches, our proof correctness is certified in the model where the protocol is defined, using the Coq proof assistant.

Thibaut Balabonski, Amélie Delga, Lionel Rieg, Sébastien Tixeuil, Xavier Urbain

On the Power of Oracle for Self-Stabilizing Leader Election in Population Protocols

This paper considers the fundamental problem of self-stabilizing leader election (SSLE) in the model of population protocols. In this model an unknown number of asynchronous, anonymous and finite state mobile agents interact in pairs. SSLE has been shown to be impossible in this model without additional assumptions. This impossibility can be circumvented for instance by augmenting the system with an oracle (an external module providing supplementary information useful to solve a problem). Fischer and Jiang have proposed solutions to SSLE, for complete communication graphs and rings, using the oracle $$\varOmega ?$$, called the eventual leader detector. In this paper, we investigate the power of $$\varOmega ?$$ on larger families of graphs. We present two important results.Our first result states that $$\varOmega ?$$ is powerful enough to allow solving SSLE over arbitrary communication graphs of bounded degree. Our second result states that, $$\varOmega ?$$ is the weakest (in the sense of Chandra, Hadzilacos and Toueg) for solving SSLE over rings. We also prove that this result does not extend to all graphs; in particular not to the family of arbitrary graphs of bounded degree.

Joffroy Beauquier, Peva Blanchard, Janna Burman, Oksana Denysyuk

Self-stabilizing Byzantine-Tolerant Distributed Replicated State Machine

Replicated state machine is a fundamental concept used for obtaining fault tolerant distributed computation. Legacy distributed computational architectures (such as Hadoop or Zookeeper) are designed to tolerate crashes of individual machines. Later, Byzantine fault-tolerant Paxos as well as self-stabilizing Paxos were introduced. Here we present for the first time the self-stabilizing Byzantine fault-tolerant version of a distributed replicated machine. It can cope with any adversarial takeover on less than one third of the participating replicas. It also ensures automatic recovery following any transient violation of the system state, in particular after periods in which more than one third of the participants are Byzantine. A prototype of self-stabilizing Byzantine-tolerant replicated Hadoop master node has been implemented. Experiments show that fully distributed recovery of cloud infrastructures against Byzantine faults can be made practical when relying on self-stabilization in local nodes. Thus automated cloud protection against a wide variety of faults and attacks is possible.

Alexander Binun, Thierry Coupaye, Shlomi Dolev, Mohammed Kassi-Lahlou, Marc Lacoste, Alex Palesandro, Reuven Yagel, Leonid Yankulin

Self-stabilizing Robots in Highly Dynamic Environments

This paper deals with the classical problem of exploring a ring by a cohort of synchronous robots. We focus on the perpetual version of this problem in which it is required that each node of the ring is visited by a robot infinitely often.The challenge in this paper is twofold. First, we assume that the robots evolve in a highly dynamic ring, i.e., edges may appear and disappear unpredictably without any recurrence nor periodicity assumption. The only assumption we made is that each node is infinitely often reachable from any other node. Second, we aim at providing a self-stabilizing algorithm to the robots, i.e., the algorithm must guarantee an eventual correct behavior regardless of the initial state and positions of the robots. Our main contribution is to show that this problem is deterministically solvable in this harsh environment by providing a self-stabilizing algorithm for three robots.

Marjorie Bournat, Ajoy K. Datta, Swan Dubois

Packet Efficient Implementation of the Omega Failure Detector

We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an Omega Failure Detector implementation. We prove the existence and sustainability of a leader is exponentially more probable in a multi-hop than in a single-hop implementation.An implementation is: message efficient if all but finitely many messages are sent by a single process; packet efficient if the number of packets used to transmit a message in all but finitely many messages is linear w.r.t. the number of processes; super packet efficient if the number of channels used by packets to transmit all but finitely many messages is linear.Our results for deterministic algorithms implementing Omega follow. If reliability and timeliness of messages do not correlate, packet efficiency is impossible. We establish necessary and sufficient conditions for the existence of message and packet efficiency and prove correct our deterministic implementation. We prove the eventuality of channels’ timeliness makes super packet efficiency impossible.

Quentin Bramas, Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil

Probabilistic Asynchronous Arbitrary Pattern Formation (Short Paper)

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.

Quentin Bramas, Sébastien Tixeuil

Flocking with Oblivious Robots

We propose a new self-stabilizing flocking algorithm for oblivious robot networks, and prove its correctness. With this algorithm, a flock head emerges from a uniform flock of robots, and the algorithm allows those robots to follow the head, whatever its direction on the plane. Robots are oblivious in that they do not recall the result of their previous computations and do not share a common coordinate system.The novelty of our approach consists in identifying the sufficient conditions to set on the flock pattern placement and the velocity of the flock-head (rotation, translation or speed), such that the flock head and the flock pattern are both preserved while the flock moves (following the head). Additionally, our system is both self-healing and self-stabilizing. In case the head leaves (e.g., disappears or is damaged) the flock agrees on a new head and follows its trajectory. Also, robots keep no record of their previous computations and we make no assumption on their initial position. The step complexity of our solution is O(n).

Davide Canepa, Xavier Defago, Taisuke Izumi, Maria Potop-Butucaru

Making Local Algorithms Wait-Free: The Case of Ring Coloring

When considering distributed computing, reliable message-passing synchronous systems on the one side, and asynchronous failure-prone shared-memory systems on tyhe other side, remain two quite independently studied ends of the reliability/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of wait-freedom is central to the second one. The paper proposes a new $$\mathcal{DECOUPLED}$$ model in an attempt to reconcile these two worlds. It consists of a synchronous and reliable communication graph of nnodes, and on top a set of asynchronous crash-prone processes, each attached to a communication node.To illustrate the $$\mathcal{DECOUPLED}$$ model, the paper presents an asynchronous 3-coloring algorithm for the processes of a ring. From the processes point of view, the algorithm is wait-free. From a locality point of view, each process uses information only from processes at distance $$O(\log ^* n)$$ from it. This local wait-free algorithm is based on an extension of the classical Cole and Vishkin vertex coloring algorithm in which the processes are not required to start simultaneously.

Armando Castañeda, Carole Delporte, Hugues Fauconnier, Sergio Rajsbaum, Michel Raynal

Meta-algorithm to Choose a Good On-Line Prediction (Short Paper)

Numerous problems require an on-line treatment. The variation of the problem instance makes it harder to solve: an algorithm used may be very efficient for a long period but suddenly its performance deteriorates due to a change in the environment. It could be judicious to switch to another algorithm in order to adapt to the environment changes.In this paper, we focus on the prediction on-the-fly. We have several on-line prediction algorithms at our disposal, each of them may have a different behaviour than the others depending on the situation. First, we address a meta-algorithm named SEA developed for experts algorithms. Next, we propose a modified version of it to improve its performance in the context of the on-line prediction.We confirm the efficiency gain we obtained through this modification in experimental manner.

Alexandre Dambreville, Joanna Tomasik, Johanne Cohen

On-Line Path Computation and Function Placement in SDNs

We consider service requests that arrive in an online fashion in Software-Defined Networks (SDNs) with network function virtualization (NFV). Each request is a flow with a high-level specification of routing and processing (by network functions) requirements. Each network function can be performed by a specified subset of servers in the system. The algorithm needs to decide whether to reject the request, or accept it and with a specific routing and processing assignment, under given capacity constraints (solving the path computation and function placement problems). Each served request is assumed to “pay” a pre-specified benefit and the goal is to maximize the total benefit accrued.In this paper we first formalize the problem, and propose a new service model that allows us to cope with requests with unknown duration without preemption. The new service model augments the traditional accept/reject schemes with a new possible response of “stand by.” We also present a new expressive model to describe requests abstractly using a “plan” represented by a directed graph. Our algorithmic result is an online algorithm for path computation and function placement that guarantees, in each time step, throughput of at least a logarithmic fraction of a (very permissive) upper bound on the maximal possible benefit.

Guy Even, Moti Medina, Boaz Patt-Shamir

Infinite Unlimited Churn (Short Paper)

We study unlimited infinite churn in peer-to-peer overlay networks. Under this churn, arbitrary many peers may concurrently request to join or leave the overlay network; moreover these requests may never stop coming. We prove that unlimited adversarial churn, where processes may just exit the overlay network, is unsolvable. We focus on cooperative churn where exiting processes participate in the churn handling algorithm. We define the problem of unlimited infinite churn in this setting. We distinguish the fair version of the problem, where each request is eventually satisfied, from the unfair version that just guarantees progress. We focus on local solutions to the problem, and prove that a local solution to the Fair Infinite Unlimited Churn is impossible. We then present our algorithm $$\mathcal {UIUC}$$ that solves the Unfair Infinite Unlimited Churn Problem for a linearized peer-to-peer overlay network. We extend this solution to skip lists and skip graphs.

Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil

Perfect Failure Detection with Very Few Bits

A failure detector is a distributed oracle that provides each process with a module that continuously outputs an estimate of which processes in the system have failed. The perfect failure detector provides accurate and eventually complete information about process failures. We show that, in asynchronous failure-prone message-passing systems, perfect failure detection can be achieved by an oracle that outputs at most $$\lceil \log \alpha (n)\rceil +1$$ bits per process in n-process systems, where $$\alpha$$ denotes the inverse-Ackermann function. This result is essentially optimal, as we also show that, in the same environment, no failure detector outputting a constant number of bits per process can achieve perfect failure detection.

Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers, Petr Kuznetsov, Thibault Rieutord

We consider snap-stabilizing algorithms in anonymous networks. Self-stabilizing algorithms are well known fault tolerant algorithms: a self-stabilizing algorithm will eventually recover from arbitrary transient faults. On the other hand, an algorithm is snap-stabilizing if it can withstand arbitrary initial values and immediately satisfy its safety requirement. It is a subset of self-stabilizing algorithms. Distributed tasks that are solvable with self-stabilizing algorithms in anonymous networks have already been characterized by Boldi and Vigna in [BV02b].In this paper, we show how the more demanding snap-stabilizing algorithms can be handled with standard tools for (not stabilizing) algorithms in anonymous networks. We give a characterization of which tasks are sovable by snap-stabilizing algorithms in anonymous networks. We also present a snap-stabilizing version of Mazurkiewicz’ enumeration algorithm.This work exposes, from a task-equivalence point of view, the complete correspondence between self or snap-stabilizing tasks and distributed tasks with various termination detection requirements.

Emmanuel Godard

Polynomial Silent Self-Stabilizing p-Star Decomposition (Short Paper)

We present a silent self-stabilizing distributed algorithm computing a maximal p-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most $$12\varDelta m + \mathcal {O}(m+n)$$ moves, where m is the number of edges, n is the number of nodes, and $$\varDelta$$ is the maximum node degree. Regarding the move complexity, our algorithm outperforms the previously known best algorithm by a factor of $$\varDelta$$. While the round complexity for the previous algorithm was unknown, we show a $$5\left\lfloor \frac{n}{p+1} \right\rfloor +5$$ bound for our algorithm.

Analysis of Computing Policies Using SAT Solvers (Short Paper)

A computing policy is a sequence of rules, where each rule consists of a predicate and a decision, and where each decision is either “accept” or “reject”. A policy P is said to accept (or reject, respectively) a request iif the decision of the first rule in P, that matches the request is “accept” (or “reject”, respectively). Examples of computing policies are firewalls, routing policies and software-defined networks in the Internet, and access control policies. A policy P is called adequate iff P accepts at least one request. It has been shown earlier that the problem of determining whether a given policy is adequate (called the policy adequacy problem) is NP-hard. In this paper, we present an efficient algorithm that use SAT solvers to solve the policy adequacy problem. Experimental results show that our algorithm can determine whether a given policy with 90 K rules is adequate in about 3 min.

Marijn J. H. Heule, Rezwana Reaz, H. B. Acharya, Mohamed G. Gouda

An Efficient Silent Self-stabilizing 1-Maximal Matching Algorithm Under Distributed Daemon Without Global Identifiers

We propose a new self-stabilizing 1-maximal matching algorithm that works under the distributed unfair daemon for arbitrarily shaped networks without cycle whose length is a multiple of three. The 1-maximal matching is a $$\frac{2}{3}$$-approximation of a maximum matching, a significant improvement over the $$\frac{1}{2}$$-approximation that is guaranteed by a maximal matching.Our algorithm is as efficient (its stabilization time is O(e) moves, where e denotes the number of edges in the network) as the best known algorithm operating under the weaker central daemon. It significantly outperforms the only known algorithm for the distributed daemon (with O(e) moves vs. $$O(2^n \delta n)$$ moves, where $$\delta$$ denotes the maximum degree of the network, and n its number of nodes), while retaining its silence property (after stabilization, its output remains fixed).

Michiko Inoue, Fukuhito Ooshita, Sébastien Tixeuil

Self-stabilizing Byzantine Clock Synchronization with Optimal Precision

We revisit the approach to Byzantine fault-tolerant clock synchronization based on approximate agreement introduced by Lynch and Welch. Our contribution is threefold: (i) We provide a slightly refined variant of the algorithm yielding improved bounds on the skew that can be achieved and the sustainable frequency offsets. (ii) We show how to extend the technique to also synchronize clock rates. This permits less frequent communication without significant loss of precision, provided that clock rates change sufficiently slowly. (iii) We present a coupling scheme that allows to make these algorithms self-stabilizing while preserving their high precision. The scheme utilizes a low-precision, but self-stabilizing algorithm for the purpose of recovery.

Pankaj Khanchandani, Christoph Lenzen

DecTDMA: A Decentralized-TDMA

With Link Quality Estimation for WSNs

In wireless sensor networks (WSNs), different motes may transmit packets concurrently, i.e., having overlapping transmission periods. As a result of this contention, there are no packet reception guarantees and significant bandwidth can be lost. This contention can have a strong impact on the performance together with other kinds of interference sources, e.g., ambient noise. As a result, WSN’s connectivity tends to have a very dynamic nature.In this paper, we devise DecTDMA (Decentralized-TDMA), a fully decentralized medium access controller (MAC) that significantly reduces contention. It is based on a self-stabilizing algorithm for time division multiple access (TDMA). This self-stabilizing TDMA algorithm uses no external assistance or external references, such as wireless access points (WAPs) and globally-synchronized clocks. We present the design and implementation of DecTDMA and report encouraging results: our Cooja simulations and Indriya testbed experiments show stable connectivity and high medium utilization in both single and multi-hop networks. Since DecTDMA has favorable characteristics with respect to connection stability, we show that common link quality estimation (LQE) techniques further improve the operation of DecTDMA in the dynamic environment of low-power wireless networks.

Olaf Landsiedel, Thomas Petig, Elad M. Schiller

Self-stabilizing Metric Graphs

We present a self-stabilizing algorithm for overlay networks that, for an arbitrary metric given by a distance oracle, constructs the graph representing that metric. The graph representing a metric is the unique minimal undirected graph such that for any pair of nodes the length of a shortest path between the nodes corresponds to the distance between the nodes according to the metric. The algorithm works under both an asynchronous and a synchronous dæmon. In the synchronous case, the algorithm stablizes in time O(n) and it is almost silent in that after stabilization a node sends and receives a constant number of messages per round.

Robert Gmyr, Jonas Lefèvre, Christian Scheideler

Near-Optimal Self-stabilising Counting and Firing Squads

Consider a fully-connected synchronous distributed system of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous counting problem, all nodes need to eventually agree on a counter that is increased by one modulo some C in each round. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input.We present a framework reducing both tasks to binary consensus at very small cost while maintaining the resilience of the underlying consensus routine. Our results resolve various open questions on the two problems, most prominently whether (communication-efficient) self-stabilising Byzantine firing squads or sublinear-time solutions for either problem exist. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience $$f<n/3$$, asymptotically optimal stabilisation and response time O(f), and message size $$O(\log f)$$. As our framework does not restrict the type of consensus routines used, we can also obtain efficient randomised solutions, and it is straightforward to adapt our framework to allow $$f<n/2$$ omission or $$f<n$$ crash faults.

Christoph Lenzen, Joel Rybicki

Snap-Stabilizing PIF on Arbitrary Connected Networks in Message Passing Model

Starting from any configuration, a snap-stabilizing algorithm guarantees that the system always behaves according to its specification while a self-stabilizing algorithm only guarantees that the system will behave according to its specification in a finite time. So, a snap-stabilizing algorithm is a time optimal self-stabilizing algorithm (because it stabilizes in 0 rounds). That means that even the first attempt of using a snap-stabilizing algorithm by any user (human or algorithm) will produce a correct execution. This is a very desirable property, especially in the case of systems that are prone to transient faults. So the problem of the existence of snap-stabilizing solutions in the message passing model is a very crucial question from a practical point of view.Snap-stabilization has been proven power equivalent to self-stabilization in the state model (a locally shared memory model) and for non-anonymous systems. That result is based on the existence of transformers built from a snap-stabilizing propagation of information with feedback (PIF) algorithm combined with some of its derivatives. In this paper, we present the first snap-stabilizing PIF algorithm for arbitrary connected networks in the message passing model. With a good setting of the timers, the time complexity of our algorithm is in $$\theta (n \times k)$$ rounds, where n and k are the number of processors and the maximal channel capacity, respectively. We then conclude that snap-stabilization is power equivalent to self-stabilization in the message passing model with bounded channels for non-anonymous systems.

Florence Levé, Khaled Mohamed, Vincent Villain

Towards Efficient and Robust BFT Protocols with ER-BFT (Short Paper)

Significant efforts have been made in designing Byzantine Fault-Tolerant (BFT) state machine replication. In addition to facing arbitrary types of faults, efficient BFT protocols aim at improving the performance in the absence of faults. This is usually obtained at the expense of higher cost when faults occur. Symmetrically, BFT protocols known as robust protocols tend to improve the performance when some types of faults occur. However, this usually implies a higher overhead in fault-free executions. ER-BFT associates efficiency and robustness to BFT protocols. The paper presents the design principles of ER-BFT, and its implementation through the ER-PBFT protocol. When compared to classical robust BFT protocols, ER-PBFT achieves better performance in fault-free cases, and in presence of faults.

Lucas Perronne, Sara Bouchenak

Global Versus Local Computations: Fast Computing with Identifiers (Short Paper)

This paper studies what can be computed by using probabilistic local interactions between agents with a very restricted power in polylogarithmic parallel time.If agents have a finite internal state (corresponding to the Population Protocol model by Angluin et al.), only semilinear predicates over the global input can be computed. If identifiers are added (corresponding to the Community Protocol model by Guerraoui and Ruppert), more global predicates over the input multiset can be computed. Local predicates over the input sorted according to the identifiers can also be computed, as long as the identifiers are ordered. The time of some of those predicates might require exponential parallel time.In this paper, we consider what can be computed with Community Protocol in a polylogarithmic number of parallel interactions. We introduce the class CPPL corresponding to protocols that use $$O(n\log ^kn)$$, for some k, expected interactions to compute their predicates, or equivalently a polylogarithmic number of parallel expected interactions.We provide some computable protocols, including one computing the size of the population. We also explore the limits of this model of computation by providing some arguments showing that local computations are no longer easy: the population does not have the time to compare a linear number of consecutive identifiers. The Linearly Local languages, such that the rational language $$(ab)^*$$, are not computable.

Mikaël Rabie

The problem of model/program repair focuses on revising an existing model/program to satisfy new properties. These properties can be safety, liveness, availability, or fault-tolerance requirements. Existing solutions focus on adding compatible properties, i.e., properties that can be satisfied while preserving the existing properties. In other words, they try to generate programs that satisfy the existing properties as well as the new desired properties. It follows that if one were to add a conflicting property, i.e., a property that cannot be satisfied while preserving existing properties, then the previous solutions declare failure to obtain the desired program. However, adding conflicting properties arises when one replaces an existing requirement with another– e.g., replacing fairness requirement with priority to some process. In this paper, we focus on the problem of adding conflicting properties. We present an algorithm for explicit addition of properties that adds new desired properties while preserving only an explicitly specified subset of existing properties. In turn, we use it to develop an algorithm for adding conflicting properties. We illustrate our algorithms with an example of job scheduling.

Complete Visibility for Robots with Lights in O(1) Time

We consider the problem of repositioning N autonomous robots on a plane so that each robot is visible to all others (the Complete Visibility problem); a robot cannot see another robot if its visibility is obstructed by a third robot positioned between them on a straight line. This problem is important since it provides a basis to solve many other problems under obstructed visibility. Robots operate following Look-Compute-Move (LCM) cycles and communicate with other robots using colored lights as in the recently proposed robots with lights model. The challenge posed by this model is that each robot has only a constant number of colors for its lights (symbols for communication) and no memory (except for the persistence of lights) between LCM cycles. Our goal is to minimize the number of rounds needed to solve Complete Visibility, where a round is measured as the time duration for all robots to execute at least one complete LCM cycle since the end of the previous round. The best previously known algorithm for Complete Visibility on this robot model has runtime of $$O(\log N)$$ rounds. That algorithm has the assumptions of full synchronicity, chirality, and robot paths may collide. In this paper we present the first algorithm for Complete Visibility with O(1) runtime that runs on the semi-synchronous (and also the fully synchronous) model. The proposed algorithm is deterministic, does not have the chirality assumption, and is collision free.

Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan, Costas Busch, Suresh Rai

- Self-stabilizing Publish/Subscribe Communication for Ad-Hoc Networks (Short Paper)

$$\mathcal {PSVR}$$ is a novel routing algorithm for pub/sub systems in ad-hoc networks focusing on scenarios where communications links are unstable and nodes frequently change subscriptions. It is a compromise of size and maintenance effort for routing tables due to sub- and unsubscriptions and the length of routing paths. Designed in a self-stabilizing manner it scales well with network size. The evaluation with real world deployment reveals that $$\mathcal {PSVR}$$ only needs slightly more messages than a close to optimal routing structure for publication delivery, and creates shorter routing paths than an existing self-stabilizing algorithm.

G. Siegemund, V. Turau

Asynchronous Non-Bayesian Learning in the Presence of Crash Failures

This paper addresses the problem of non-Bayesian learning in multi-agent networks, where agents repeatedly collect local observations about an unknown state of the world, and try to collaboratively detect the true state through information exchange. We focus on the impact of failures and asynchrony – two fundamental factors in distributed systems – on the performance of consensus-based non-Bayesian learning. In particular, we assume the networked agents may suffer crash faults, and messages delay can be arbitrarily long but finite.1.We characterize the minimal global identifiability of the network for any consensus-based non-Bayesian learning to work.2.Finite time convergence rate is obtained.3.As part of our convergence analysis, we obtain a generalization of a celebrated result by Wolfowitz and Hajnal to submatrices, which might be of independent interest.

Lili Su, Nitin H. Vaidya

Robust Multi-agent Optimization: Coping with Byzantine Agents with Input Redundancy

This paper addresses the multi-agent optimization problem in which the agents try to collaboratively minimize $$\frac{1}{k}\sum _{i=1}^k h_i$$ for a given choice of k input functions $$h_1, \ldots , h_k$$. This problem finds its application in distributed machine learning, where the data set is too large to be processed and stored by a single machine. It has been shown that when the networked agents may suffer Byzantine faults, it is impossible to minimize $$\frac{1}{k}\sum _{i=1}^k h_i$$ with no redundancy in the local cost functions.We are interested in the impact of the local cost functions redundancy on the solvability of $$\frac{1}{k}\sum _{i=1}^k h_i$$. In particular, we assume that the local cost function of each agent is formed as a convex combination of the k input functions $$h_1, \ldots , h_k$$. Depending on the availability of side information at each agent, two slightly different variants are considered. We show that for a given graph, the problem can indeed be solved despite the presence of faulty agents. In particular, even in the absence of side information at each agent, when adequate redundancy is available in the optima of input functions, a distributed algorithm is proposed in which each agent carries minimal state across iterations.

Lili Su, Nitin H. Vaidya

Plane Formation by Semi-synchronous Robots in the Three Dimensional Euclidean Space

We consider the plane formation problem that requires a set of autonomous mobile robots initially placed in the three-dimensional space to land on a common plane that is not defined a priori. The problem was first introduced for fully-synchronous (FSYNC) robots with rigid movement (i.e., the robots always reach the next position) and solvable instances are characterized in terms of the symmetry among the robots, i.e., the rotation group of the initial configuration of robots (Yamauchi et al. DISC 2015). We consider the plane formation problem for semi-synchronous (SSYNC) robots with non-rigid movement. We present a plane formation algorithm for oblivious SSYNC robots, and show that the SSYNC robots with non-rigid movement have the same plane formation power as the FSYNC robots with rigid movement.

Taichi Uehara, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Searching for an Evader in an Unknown Graph by an Optimal Number of Searchers

The graph search problem is the problem of searching a graph G for a mobile evader by mobile searchers. The edge search is an offline and centralized version, and es(G) denotes the number of searchers necessary and sufficient to edge search G. An online and distributed setting assumes a port numbering of G, a distinct homebase and a whiteboard in each node. Search algorithms typically respect the monotone and connected search strategy to protect the information on whiteboards; however, $$\varOmega ( \frac{n}{\log n} es (G))$$ searchers are necessary even for trees, where n is the order of G. We investigate the problem under a new online and distributed setting: We assume that searchers can exchange information wherever they meet, instead of assuming a port numbering, a homebase and whiteboards. Under this setting, we propose a search algorithm for es(G) searchers, which is optimal.

Takahiro Yakami, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Wait-Free Solvability of Colorless Tasks in Anonymous Shared-Memory Model

We investigate the capability of distributed systems in the anonymous asynchronous shared-memory model, in which processes have no identifiers and communicate through multi-writer/multi-reader atomic registers. The present paper assumes that an arbitrary number of processes may fail by crashing.We propose a full-information protocol for colorless tasks and give a topological characterization of colorless tasks that are wait-free solvable in the anonymous model. The characterization implies, as long as colorless tasks are concerned, that the anonymity does not reduce the computational power of the asynchronous shared-memory model.

Nayuta Yanagisawa

Backmatter

Weitere Informationen