Skip to main content

Über dieses Buch

This book constitutes the refereed proceedings of the 16 International Symposium on Stabilization, Safety and Security of Distributed Systems, SSS 2013, held in Osaka, Japan, in September/October 2014. The 21 regular papers and 8 short papers presented were carefully reviewed and selected from 44 submissions. The Symposium is organized in several tracks, reflecting topics to self-* properties. The tracks are self-stabilization; ad-hoc; sensor and mobile networks; cyberphysical systems; fault-tolerant and dependable systems; formal methods; safety and security; and cloud computing; P2P; self-organizing; and autonomous systems.



Separating Data and Control: Asynchronous BFT Storage with 2t + 1 Data Replicas

The overhead of Byzantine fault tolerant (BFT) storage is a primary concern that prevents its adoption in practice. The cost stems from the need to maintain at least 3t + 1 copies of the data at different storage replicas in the asynchronous model, so that t Byzantine replica faults can be tolerated. This paper presents MDStore, the first fully asynchronous BFT storage protocol that reduces the number of replicas that store the payload data to as few as 2t + 1 and maintains metadata at 3t + 1 replicas on (possibly) different servers. At the heart of MDStore lies a metadata service built upon a new abstraction called “timestamped storage.” Timestamped storage allows for conditional writes (facilitating the implementation of the metadata service) and has consensus number one (making it implementable with wait-free semantics in an asynchronous system despite faults). In addition to its low replication overhead, MDStore offers strong guarantees by emulating a multi-writer multi-reader atomic register, providing wait-free termination, and tolerating any number of Byzantine readers and crash-faulty writers.
Christian Cachin, Dan Dobre, Marko Vukolić

On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms

It follows from the definition of silent self-stabilization, and from the definition of proof-labeling scheme, that if there exists a silent self-stabilizing algorithm using ℓ-bit registers for solving a task \({\mathcal{T}} \), then there exists a proof-labeling scheme for \({\mathcal{T}} \) using registers of at most ℓ bits. The first result in this paper is the converse to this statement. We show that if there exists a proof-labeling scheme for a task \({\mathcal{T}} \), using ℓ-bit registers, then there exists a silent self-stabilizing algorithm using registers of at most O(ℓ + logn) bits for solving \({\mathcal{T}} \), where n is the number of processes in the system. Therefore, as far as memory space is concerned, the design of silent self-stabilizing algorithms essentially boils down to the design of compact proof-labeling schemes. The second result in this paper addresses time complexity. We show that, for every task \({\mathcal{T}} \) with k-bits output size in n-node networks, there exists a silent self-stabilizing algorithm solving \({\mathcal{T}} \) in O(n) rounds, using registers of O(n 2 + kn) bits. Therefore, as far as running time is concerned, every task has a silent self-stabilizing algorithm converging in a linear number of rounds.
Lélia Blin, Pierre Fraigniaud, Boaz Patt-Shamir

On the Resilience of Pull-Based P2P Streaming Systems against DoS Attacks

The robustness of pull-based streaming systems to node failure and churn has been extensively analyzed. Their resistance to sabotage, however, is not well understood, so far. Recent measurement studies on a large deployed pull-based system have discovered stable source-to-peer paths and the convergence of the content dissemination to rather static topologies over time. Thus, an attack on central nodes within these static topologies, which causes serious service disruptions, is feasible. This paper demonstrates attacks that significantly reduce the system’s performance. As a countermeasure, we introduce a novel striping scheme, which decreases the dependencies between peers and thus the impact of attacks. A thorough simulation study indicates that our scheme achieves a high resistance against sabotage attacks at negligible overhead and performance penalties.
Giang Nguyen, Mathias Fischer, Thorsten Strufe

On Stabilizing Departures in Overlay Networks

A fundamental problem for peer-to-peer systems is to maintain connectivity while nodes are leaving, i.e., the nodes requesting to leave the peer-to-peer system are excluded from the overlay network without affecting its connectivity. There are a number of studies for safe node exclusion if the overlay is in a well-defined state initially. Surprisingly, the problem is not formally studied yet for the case in which the overlay network is in an arbitrary initial state, i.e., when looking for a self-stabilizing solution for excluding leaving nodes. We study this problem in two variants: the Finite Departure Problem ( \(\mathcal{FDP}\) ) and the Finite Sleep Problem ( \(\mathcal{FSP}\) ). In the \(\mathcal{FDP}\) the leaving nodes have to irrevocably decide when it is safe to leave the network, whereas in the \(\mathcal{FSP}\), this leaving decision does not have to be final: the nodes may resume computation if necessary. We show that there is no self-stabilizing distributed algorithm for the \(\mathcal{FDP}\), even in a synchronous message passing model. To allow a solution, we introduce an oracle called \(\mathcal{NIDEC}\) and show that it is sufficient even for the asynchronous message passing model by proposing an algorithm that can solve the \(\mathcal{FDP}\) using \(\mathcal{NIDEC}\). We also show that a solution to the \(\mathcal{FSP}\) does not require an oracle.
Dianne Foreback, Andreas Koutsopoulos, Mikhail Nesterenko, Christian Scheideler, Thim Strothmann

CloudSylla: Detecting Suspicious System Calls in the Cloud

To protect computer systems against the tremendous number of daily malware threats, security software is typically installed on individual end hosts and the responsibility to keep this software updated is often assigned to (inexperienced) users. A critical drawback of this strategy, especially in enterprise networks, is that a single unprotected client system might lead to severe attacks such as industrial espionage. To overcome this problem, a potential approach is to move the responsibility to utilize the latest detection mechanisms to a centralized, continuously maintained network service to identify suspicious behavior on end hosts and perform adequate actions once a client invokes malicious activities. In this paper, we propose a security approach called CloudSylla (Cloud-based SYscaLL Analysis) in which we utilize a centralized network service to analyze the clients’ activities directly at the API and system call level. This enables, among other advantages, a centralized management of signatures and a unified security policy. To evaluate the applicability of our approach, we implemented prototypes for desktop computers and mobile devices and found this approach to be applicable in practice as no substantial limitations of usability are caused on the client side.
Marc Kührer, Johannes Hoffmann, Thorsten Holz

Postman: An Elastic Highly Resilient Publish/Subscribe Framework for Self Sustained Service Independent P2P Networks

Self sustained service independent P2P networks aim to serve as a cheap alternative to traditional cloud providers. In such networks, users who add resources to the network are given strong (typically monetary) incentives to keep their devices connected for long periods of time. Further, in such networks, there is a decoupling between the machines that form the P2P network and the devices used to consume services from the network. In particular, users may access services offered by the network through their mobile devices. In fact, a user may obtain services even if he did not donate any resources, but is willing to pay for the services he consumes either through a service fee or by viewing ads, similarly to cloud services.
This work introduces Postman, a publish/subscribe architecture tailored for self sustained service independent P2P networks. Postman is designed to provide its users with a self-organizing, scalable, efficient and churn resilient publish/subscribe service. Postman achieves this using a novel client/mailbox architecture where a publish/subscribe system delivers content to a highly diverse set of mailboxes. Mailboxes are hosted on elastically selected set of peers and each mailbox accumulates multiple topics from many clients. Clients then fulfill their subscriptions by polling the relevant mailboxes, while the mailboxes act as subscribers of the actual publish/subscribe mechanism. Our experimental results show that the client/mailbox architecture significantly reduces the number of subscriptions the publish/subscribe mechanism handles. In addition, the publish/subscribe mechanism handles a much more uniform subscription pattern than the real subscription pattern, obtains very high delivery rates and is highly robust to failures and churn.
Gil Einziger, Roy Friedman

A Self-stabilizing Algorithm for Edge Monitoring Problem

Self-monitoring is a simple and effective mechanism for the security of wireless sensor networks (WSNs), especially to cope against compromised nodes. A node v can monitor an edge e if both end-nodes of e are neighbors of v; i.e., e together with v forms a triangle in the graph. Moreover, some edges need more than one monitor. Finding a set of monitoring nodes satisfying all monitoring constraints is called the edge-monitoring problem. The minimum edge-monitoring problem is long known to be NP-complete. In this paper, we present a novel silent self-stabilizing algorithm for computing a minimal edge-monitoring set. Correctness and termination are proven for the unfair distributed daemon.
Brahim Neggazi, Mohammed Haddad, Volker Turau, Hamamache Kheddouci

Self-stabilizing Leader Election in Polynomial Steps

In this paper, we propose a silent self-stabilizing leader election algorithm for bidirectional connected identified networks of arbitrary topology. This algorithm is written in the locally shared memory model. It assumes the distributed unfair daemon, the most general scheduling hypothesis of the model. Our algorithm requires no global knowledge on the network (such as an upper bound on the diameter or the number of processes, for example). We show that its stabilization time is in Θ(n 3) steps in the worst case, where n is the number of processes. Its memory requirement is asymptotically optimal, i.e., Θ(logn) bits per processes. Its round complexity is of the same order of magnitude — i.e., Θ(n) rounds — as the best existing algorithm [10] designed with similar settings. To the best of our knowledge, this is the first self-stabilizing leader election algorithm for arbitrary identified networks that is proven to achieve a stabilization time polynomial in steps. By contrast, we show that the previous best existing algorithm designed with similar settings [10] stabilizes in a non polynomial number of steps in the worst case.
Karine Altisen, Alain Cournier, Stéphane Devismes, Anaïs Durand, Franck Petit

Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Networks

Many articles deal with the problem of maintaining a rooted shortest-path tree. However, after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r. In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r . Without any assumption on the asynchronous model (unfair daemon), with no knowledge of the network and within an anonymous network, we present a silent self-stabilizing algorithm solving this more demanding task and running in less than 2n + D rounds for a network of n nodes and hop-diameter D.
Glacet Christian, Hanusse Nicolas, Ilcinkas David, Johnen Colette

Self-synchronized Cooperative Beamforming in Ad-Hoc Networks

We investigate the unicast problem for ad-hoc networks in the plane using MIMO techniques. In particular, we use the multi-node beamforming gain and present a self-synchronizing algorithm for the necessary carrier phase synchronization. First, we consider n nodes in a grid where the transmission power per node is restricted to reach the neighboring node. We extend the idea of multi-hop routing and relay the message by multiple nodes attaining joint beamforming gain with higher reception range. In each round, the message is repeated by relay nodes at dedicated positions after a fixed waiting period. Such simple algorithms can send a message from any node to any other node in time \(\mathcal{O}(\log \log n - \log \lambda)\) and with asymptotical energy \(\mathcal{O}(\sqrt{n})\), the same energy an optimal multi-hop routing strategy needs using short hops between source and target. Here, λ denotes the wavelength of the carrier. For λ ∈ Θ(1) we prove a tight lower time bound of Ω(loglogn).
Then, we consider n randomly distributed nodes in a square of area n and we show for a transmission range of \(\Theta(\sqrt{\log n})\) and for a wavelength of λ = Ω(log− 1/2 n) that the unicast problem can be solved in \(\mathcal{O}(\log \log n)\) rounds as well. The corresponding transmission energy increases to \(\mathcal{O}(\sqrt{n} \log n)\). Finally, we present simulation results visualizing the nature of our algorithms.
Thomas Janson, Christian Schindelhauer

Robots with Lights: Overcoming Obstructed Visibility Without Colliding

Robots with lights is a model of autonomous mobile computational entties operating in the plane in Look-Compute-Move cycles: each agent has an externally visible light which can assume colors from a fixed set; the lights are persistent (i.e., the color is not erased at the end of a cycle), but otherwise the agents are oblivious. The investigation of computability in this model is under way, and several results have been recently established. In these investigations, however, an agent is assumed to be capable to see through another agent.
In this paper we start the study of computing when visibility is obstructable, and investigate the most basic problem for this setting, Complete Visibility: The agents must reach within finite time a configuration where they can all see each other and terminate. We do not make any assumption on a-priori knowledge of the number of agents, on rigidity of movements nor on chirality. The local coordinate system of an agent may change at each activation. Also, by definition of lights, an agent can communicate and remember only a constant number of bits in each cycle. In spite of these weak conditions, we prove that Complete Visibility is always solvable, even in the asynchronous setting, without collisions and using a small constant number of colors. The proof is constructive. We also show how to extend our protocol for Complete Visibility so that, with the same number of colors, the agents solve the (non-uniform) Circle Formation problem with obstructed visibility.
Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Nicola Santoro, Giovanni Viglietta

SMT-Based Synthesis of Distributed Self-stabilizing Systems

A self-stabilizing system is one that guarantees reaching a set of legitimate states from any arbitrary initial state. Designing distributed self-stabilizing protocols is often a complex task and developing their proof of correctness is known to be significantly more tedious. In this paper, we propose an SMT-based method that automatically synthesizes a self-stabilizing protocol, given the network topology of distributed processes and description of the set of legitimate states. We also report successful automated synthesis of Dijkstra’s token ring and distributed maximal matching.
Fathiyeh Faghih, Borzoo Bonakdarpour

Stateless Stabilization Bootstrap (Extended Abstract)

Stateless protocols, servers, services and programs are inherently self-stabilizing when repeatedly invoked, as any invocation starts from scratch. We suggest to augment a given stateful program with a stateless prefix that (upon invocation of the stateful program, and possibly periodically) verifies the consistency of the state of the stateful program prior to the execution of the stateful program.
We demonstrate the new stateless stabilization bootstrap paradigm by implementing stabilizing double linked list of the Linux kernel. In particular we focus on the KVM linked list data structure consistency.
Shlomi Dolev, Ramzi Martin Kahil, Reuven Yagel

Self-healing Computation

In the problem of reliable multiparty computation (RC), there are n parties, each with an individual input, and the parties want to jointly compute a function f over n inputs. The problem is complicated by the fact that an omniscient adversary controls a hidden fraction of the parties.
We describe a self-healing algorithm for this problem. In particular, for a fixed function f, with n parties and m gates, we describe how to perform RC repeatedly as the inputs to f change. Our algorithm maintains the following properties, even when an adversary controls up to \(t \leq (\frac{1}{4} - \epsilon) n\) parties, for any constant ε > 0. First, our algorithm performs each reliable computation with the following amortized resource costs: O(m + n logn) messages, O(m + n logn) computational operations, and O(ℓ) latency, where ℓ is the depth of the circuit that computes f. Second, the expected total number of corruptions is O(t (log* m)2 ), after which the adversarially controlled parties are effectively quarantined so that they cause no more corruptions.
George Saad, Jared Saia

Optimal Gathering on Infinite Grids

The gathering problem has been largely studied in the last years with respect to various basic graph topologies. The requirement is to move a team of robots initially placed at different vertices of the input graph towards a common vertex, and to let them remain at such a vertex. Robots move based on the so called Look-Compute-Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move towards one of its neighbors (Compute), and in the positive case it makes the computed move instantaneously (Move). All the phases are performed asynchronously for each robot. So far, the goal has been mainly to detect the minimal assumptions that allow to accomplish the gathering task, without taking care of any cost measure of the provided solutions. In this paper, we are interested in devising optimal algorithms in terms of total number of moves the robots have to perform in order to finalize the gathering. In particular, we consider infinite grids as input graphs, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm.
Gabriele Di Stefano, Alfredo Navarra

Incremental Verification of Computing Policies

A computing policy is a sequence of rules, where each rule consists of a predicate and an action, which can be either “accept” or “reject”. A policy P is said to accept (or reject, respectively) a request iff the action of the first rule in P, whose predicate matches the request, is “accept” (or “reject”, respectively). An accept (or reject, respectively) property of a policy P is a set of requests that should be accepted (or rejected, respectively) by P. Policy P is said to satisfy an accept (or reject, respectively) property pp iff every request that is specified by property pp is accepted (or rejected, respectively) by policy P. In this paper, we outline efficient methods for verifying whether any given policy P satisfies any given property pp, provided that policy P results from changing only one rule in another policy that is known to satisfy property pp.
Ehab S. Elmallah, H. B. Acharya, Mohamed G. Gouda

On the Synthesis of Mobile Robots Algorithms: The Case of Ring Gathering

Recent advances in Distributed Computing highlight models and algorithms for autonomous swarms of mobile robots that self-organize and cooperate to solve global objectives. The overwhelming majority of works so far considers handmade algorithms and correctness proofs.
This paper is the first to propose a formal framework to automatically design distributed algorithms that are dedicated to autonomous mobile robots evolving in a discrete space. As a case study, we consider the problem of gathering all robots at a particular location, not known beforehand. Our contribution is threefold. First, we propose an encoding of the gathering problem as a reachability game. Then, we automatically generate an optimal distributed algorithm for three robots evolving on a fixed size uniform ring. Finally, we prove by induction that the generated algorithm is also correct for any ring size except when an impossibility result holds (that is, when the number of robots divides the ring size).
Laure Millet, Maria Potop-Butucaru, Nathalie Sznajder, Sébastien Tixeuil

Synthesizing Self-stabilization through Superposition and Backtracking

While the design of self-stabilization is known to be a hard problem, several sound (but incomplete) heuristics exist for algorithmic design of self-stabilization. This paper presents a sound and complete method for algorithmic design of self-stabilizing network protocols. The essence of the proposed approach is based on variable superposition and backtracking search. We have validated the proposed method by creating both a sequential and a parallel implementation in the context of a software tool, called Protocon. Moreover, we have used Protocon to automatically design self-stabilizing protocols for the problems that all existing heuristics fail to solve.
Alex Klinkhamer, Ali Ebnenasir

Configuration Hopping: A Secure Communication Protocol without Explicit Key Exchange

By changing one or more physical layer parameters (such as spreading code, symbol duration, symbol constellation, center frequency, modulation method, transmission power, etc.) in an agreed upon manner between two communication parties, we are able to realize communication that is hard to detect, identify, and decode. We present a formal link layer protocol for secure communication based on this idea that, along with the use of channel reciprocity, notably eschews the use of cryptographic keys. We prove the security properties of the protocol in the Canetti-Krawczyk framework and study the feasibility of changing several physical layer parameters at the link packet level in Software Defined Radios.
Yue Qiao, Kannan Srinivasan, Anish Arora

Dependable Decentralized Cooperation with the Help of Reliability Estimation

Internet supercomputing aims to solve large partitionable computational problems by using vast numbers of computers. Here we consider the abstract version of the problem, where n processors perform t independent tasks, with n ≤ t, and each processor learns the results of all tasks. An adversary may cause a processor to return incorrect results, and to crash. Prior solutions limited the adversary by either (i) assuming the average probability of returning incorrect results to always be inferior to \(\frac{1}{2}\), or (ii) letting each processor know such probabilities for all other processors. This paper presents a new randomized synchronous algorithm that deals with stronger adversaries while achieving efficiency comparable to the weaker solutions. The adversary is constrained in two ways. (1) The set of non-crashed processors must contain a hardened subset H of the initial set of processors P, for which the average probability of returning a bogus result is inferior to \(\frac{1}{2}\). Notably, crashes may increase the average probability of processor misbehavior. (2) The adversary may crash a set of processors F, provided |P − F| is bounded from below. We analyse the algorithm for three bounds on |P − F|: (a) when the bound is linear in n the algorithm takes \(\Theta(\frac{t}{n}\log{n})\) communication rounds, has work complexity Θ(tlogn), and message complexity O(nlog2 n); (b) when the bound is polynomial (|P − F| = Ω(n a ), for a constant a ∈ (0,1)), the algorithm takes \(O(\frac{t}{n^{a}}\log{n}\log{\log{n}})\) rounds, with work O(tlogn loglogn), and message complexity O(nlog2 nloglogn); (c) when the bound is polylog in n, it takes O(t) rounds, has work O(t ·n a ), and message complexity O(n 1 + a ), for a ∈ (0,1).
Seda Davtyan, Kishori M. Konwar, Alexander A. Shvartsman

Snap-Stabilizing PIF on Non-oriented Trees and Message Passing Model

Starting from any configuration, a snap-stabilizing protocol guarantees that the system always behaves according to its specification while a self-stabilizing protocol only guarantees that the system will behave according to its specification in a finite time. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). That property is very suitable in the case of systems that are prone to transient faults. There exist a lot of approaches of the concept of self-stabilization, but to our knowledge, snap-stabilization is the only variant of self-stabilization which has been proved power equivalent to self-stabilization in the context of the state model (a locally shared memory model) and for non anonymous systems. 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. In this paper, we present the first snap-stabilizing propagation of information with feedback (PIF) protocol for non-oriented trees in the message passing model. Moreover using slow and fast timers, the round complexity of our algorithm is in θ(h ×k) and θ((h ×k) + k 2), respectively, where h is the height of the tree and k is the maximal capacity of the channels. We conjecture that our algorithm is optimal.
Florence Levé, Khaled Mohamed, Vincent Villain

Edge Coloring Despite Transient and Permanent Faults

We consider the problem of edge coloring in the presence of transient and permanent faults: we must achieve a stable edge coloring despite any initial state, and despite an unbounded number of Byzantine nodes. In this paper, we consider that no local variable is allowed: we only use the colors of the edges. We give a general algorithm to achieve edge coloring at distance 2 of Byzantine failures. Then, we give a Byzantine insensitive algorithm for edge coloring on a ring (we achieve a stable coloring on the correct subgraph).
Alexandre Maurer, Toshimitsu Masuzawa

Tight Bounds for Stabilizing Uniform Consensus in Mobile Networks

This paper addresses the problem of solving stabilizing uniform consensus in mobile networks. In this problem, the input of nodes may change multiple times before they eventually stabilize. However, when the system stabilizes all correct nodes output a value and there are no two non-crashed nodes (whether faulty or not) that output different values. In contrast to stabilizing consensus, stabilizing uniform consensus is not solvable with Byzantine faults. So we consider here weaker kinds of faults, namely crash faults and omission faults. We show that for crash and send-omission faults, n > 2t is a necessary and sufficient condition for solving stabilizing uniform consensus, where n is the total number of mobile nodes, out of which t may be faulty. Interestingly, when the input of nodes are fixed, stabilizing uniform consensus is solvable with crash faults for n > t and with send-omission faults for n > 2t (for t > 1). When considering general omission faults, we show that stabilizing uniform consensus is not solvable, even for fixed inputs and t = 1.
Hung Tran-The, Luís Rodrigues


Weitere Informationen

Premium Partner