Skip to main content
main-content

Über dieses Buch

This book constitutes the proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2011, held in Grenoble, France, in October 2011. The 29 papers presented were carefully reviewed and selected from 79 submissions. They cover the following areas: ad-hoc, sensor, and peer-to-peer networks; safety and verification; security; self-organizing and autonomic systems; and self-stabilization.

Inhaltsverzeichnis

Frontmatter

Silence Is Golden: Self-stabilizing Protocols Communication-Efficient after Convergence

Self-stabilization is a general paradigm to provide forward recovery capabilities to distributed systems. A self-stabilizing protocol can eventually recover its intended behavior even when starting from an arbitrary initial configuration, and thus, it has high adaptability to transient faults (e.g., process state corruptions and message corruptions) and network topology changes. The high adaptability is usually acquired at the cost of efficiency. A crucial difference in cost between self-stabilizing and non-self-stabilizing protocols lies in the cost of communication after reaching a desired configuration. It is quite evident for static problems, e.g., spanning-tree construction. Self-stabilizing protocols cannot allow any process to terminate its communication even after converging to a desired configuration (where a solution of the problem is already obtained), while non-self-stabilizing ones can eventually allow every process to terminate all the activity.

Toshimitsu Masuzawa

Computing in Time-Varying Networks

There has been recently a large number of investigations devoted to the study of infrastructure-less highly dynamic networks. These include most types of

highly-mobile ad hoc networks

, such as pedestrian or vehicular networks, where the network’s topology may change dramatically over time due to the movement of the nodes;

sensor networks

with sleep scheduling, where links only exist when two neighbouring sensors are awake and have power; and low-density ad hoc networks made up of satellites, where nodes are most of the time isolated and must rely on a store-carry-forward mechanism for their communications. These highly dynamic networks, variously called

delay-tolerant

,

disruptive-tolerant

,

challenged

,

opportunistic

, have in common that the assumption of

connectivity

does not necessarily hold, at least with the usual meaning of

contemporaneous end-to-end multi-hop paths

between any pair of nodes. The network may actually be disconnected at every time instant. Still, communication routes may be available over time and space, and make broadcast, routing, and distributed computing feasible.

Nicola Santoro

The K-Observer Problem in Computer Networks

For any non-negative integer

K

, a

K

-

observer

P

of a network

N

is a set of nodes in

N

such that each message, that travels at least

K

hops in

N

, is handled (and so observed) by at least one node in

P

. A

K

-observer

P

of a network

N

is

minimum

iff the number of nodes in

P

is less than or equal the number of nodes in every

K

-observer of

N

. The nodes in a minimum

K

-observer of a network

N

can be used to monitor the message traffic in network

N

, detect denial-of-service attacks, and act as firewalls to identify and discard attack messages. This paper considers the problem of constructing a minimum

K

-observer for any given network. We show that the problem is NP-hard for general networks, and give linear-time algorithms for constructing minimum or near-minimum

K

-observers for special classes of networks: trees, rings,

L

-rings, and large grids.

H. B. Acharya, Taehwan Choi, Rida A. Bazzi, Mohamed G. Gouda

Pragmatic Self-stabilization of Atomic Memory in Message-Passing Systems

A fault-tolerant and stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a pragmatic manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself.

Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil

An Algorithm for Implementing BFT Registers in Distributed Systems with Bounded Churn

Distributed storage service is one of the main abstractions provided to the developers of distributed applications due to its capability to hide the complexity generated by the messages exchanged between processes. Many protocols have been proposed to build byzantine-fault-tolerant storage services on top of a message-passing system, but they do not consider the possibility to have servers joining and leaving the computation (

churn

phenomenon). This phenomenon, if not properly mastered, can either block protocols or violate the safety of the storage. In this paper, we address the problem of building of a safe register storage resilient to byzantine failures in a distributed system affected from churn. A protocol implementing a safe register in an eventually synchronous system is proposed and some feasibility constraints on the arrival and departure of the processes are given. The protocol is proved to be correct under the assumption that the constraint on the churn is satisfied.

Roberto Baldoni, Silvia Bonomi, Amir Soltani Nezhad

Computing Time Complexity of Population Protocols with Cover Times - The ZebraNet Example

Population protocols

are a communication model for large sensor networks with resource-limited mobile agents. The agents move asynchronously and communicate via pair-wise interactions. The original

fairness

assumption of this model involves a high level of asynchrony and prevents an evaluation of the convergence time of a protocol (via deterministic means). The introduction of some “partial synchrony” in the model, under the form of

cover times

, is an extension that allows evaluating the time complexities.

In this paper, we take advantage of this extension and study a

data collection

protocol used in the ZebraNet project for the wild-life tracking of zebras in a reserve in central Kenya. In ZebraNet, sensors are attached to zebras and the sensed data is collected regularly by a mobile

base station

crossing the area. The data collection protocol of ZebraNet has been analyzed through simulations, but to our knowledge, this is the first time, that a purely analytical study is presented. Our first result is that, in the original protocol, some data may never be delivered to the base station. We then propose two slightly modified and correct protocols and we compute their worst case time complexities. Still, in both cases, the result is far from the optimal.

Joffroy Beauquier, Peva Blanchard, Janna Burman, Sylvie Delaët

Building Self-stabilizing Overlay Networks with the Transitive Closure Framework

Overlay networks are expected to operate in hostile environments, where node and link failures are commonplace. One way to make overlay networks robust is to design self-stabilizing overlay networks, i.e., overlay networks that can handle node and link failures without any external supervision. In this paper, we first describe a simple framework, which we call the

Transitive Closure Framework

(TCF), for the self-stabilizing construction of an extensive class of overlay networks. Like previous self-stabilizing overlay networks, TCF permits node degrees to grow to Ω(

n

), independent of the maximum degree of the target overlay network. However, TCF has several advantages over previous work in this area: (i) it is a “framework” and can be used for the construction of a variety of overlay networks, not just a particular network, (ii) it runs in an optimal number of rounds for a variety of overlay networks, and (iii) it can easily be composed with other non-self-stabilizing protocols that can recover from specific bad initial states in a memory-efficient fashion. We demonstrate the power of our framework by deriving from TCF a simple self-stabilizing protocol for constructing

Skip+

graphs (Jacob et al., PODC 2009) which presents optimal convergence time from any configuration, and requires only a

O

(1) factor of extra memory for handling node

Join

s.

Andrew Berns, Sukumar Ghosh, Sriram V. Pemmaraju

Active Stabilization

We propose the notion of

active stabilization

for computing systems. Unlike typical stabilizing programs (called passive stabilizing in this paper) that require that the faults are absent for a long enough time for the system to recover to legitimate states, active stabilizing programs ensure recovery in spite of constant perturbation during the recovery process by an adversary. We identify the relation between active and passive stabilization in terms of their behavior and by comparing their cost of verification. We propose a method for designing active stabilizing programs by a collection of passive stabilizing programs. Finally, we compare active stabilization with fault-contained stabilization and stabilization in the presence of Byzantine faults.

Borzoo Bonakdarpour, Sandeep S. Kulkarni

Robot Networks with Homonyms: The Case of Patterns Formation

In this paper, we consider the problem of formation of a series of geometric patterns by a network of oblivious mobile robots that communicate only through vision. So far, the problem has been studied in models where robots are either assumed to have distinct identifiers or to be completely anonymous. To generalize these results and to better understand how anonymity affects the computational power of robots, we study the problem in a new model in which

n

robots may share up to 1 ≤ 

h

 ≤ 

n

different identifiers. We present necessary and sufficient conditions, relating symmetricity and homonymy, that makes the problem solvable. We also show that in the case where

h

 = 

n

, making the identifiers of robots invisible does not limit their computational power. This contradicts a recent result of Das et al. To present our algorithms, we use a function that computes the Weber point for many regular and symmetric configurations. This function is interesting in its own right, since the problem of finding Weber points has been solved up to now for only few other patterns.

Zohir Bouzid, Anissa Lamani

A Non-topological Proof for the Impossibility of k-Set Agreement

In the

k-set agreement

task each process proposes a value, and it is required that each correct process has to decide a value which was proposed and at most

k

distinct values must be decided. Using topological arguments it has been proved that

k

-set agreement is unsolvable in the asynchronous

wait-free

read/write shared memory model, when

k

 < 

n

, the number of processes.

This paper presents a simple, non-topological impossibility proof of

k

-set agreement. The proof depends on two simple properties of the

immediate snapshot executions

, a subset of all possible executions, and on the well known graph theory result stating that every graph has an even number of vertices with odd degree (the

handshaking lemma

).

Hagit Attiya, Armando Castañeda

Formal Verification of Consensus Algorithms Tolerating Malicious Faults

Consensus is the paradigmatic problem in fault-tolerant distributed computing: it requires network nodes that communicate by message passing to agree on common value even in the presence of (benign or malicious) faults. Several algorithms for solving Consensus exist, but few of them have been rigorously verified, much less so formally. The Heard-Of model proposes a simple, unifying framework for defining distributed algorithms in the presence of communication faults. Algorithms proceed in communication-closed rounds, and assumptions on the faults tolerated by the algorithm are stated abstractly in the form of communication predicates. Extending previous work on the case of benign faults, our approach relies on the fact that properties such as Consensus can be verified over a coarse-grained, round-based representation of executions. We have encoded the Heard-Of model in the interactive proof assistant Isabelle/HOL and have used this encoding to formally verify three Consensus algorithms based on synchronous and asynchronous assumptions. Our proofs give some new insights into the correctness of the algorithms, in particular with respect to transient faults.

Bernadette Charron-Bost, Henri Debrat, Stephan Merz

The Computational Power of Simple Protocols for Self-awareness on Graphs

We explore the capability of a network of extremely limited computational entities to decide properties about any of its subnetworks. We consider that the underlying network of the interacting entities (devices, agents, processes etc.) is modeled by a complete

interaction graph

and we devise simple graph protocols that can decide properties of some

input subgraph

provided by some preprocessing on the network. The agents are modeled as finite-state automata and run the same global graph protocol. Each protocol is a fixed size grammar, that is, its description is independent of the size (number of agents) of the network. This size is not known by the agents. We propose a simple model, the

Mediated Graph Protocol

(

MGP

) model, similar to the Population Protocol model of Angluin

et al.

, in which each network link is characterized by a

state

taken from a finite set. This state can be used and updated during each interaction between the corresponding agents. We provide some interesting properties of the MGP model among which is the ability to decide properties on stabilizing (initially changing for a finite number of steps) input graphs and we show that the MGP model has the ability to decide properties of disconnected input graphs. We show that the computational power within the connected components is fairly restricted. Finally, we give an exact characterization of the class

GMGP

, of graph languages decidable by the MGP model: it is equal to the class of graph languages decidable by a nondeterministic Turing Machine of linear space that receives its input graph by its adjacency matrix representation.

Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Paul G. Spirakis

Self-stabilizing Labeling and Ranking in Ordered Trees

We propose two self-stabilizing algorithms for tree networks. The first one computes a special label, called

guide pair

of each process

P

in

O

(

h

) rounds (

h

being the height of the tree) using

O

(

δ

P

log

n

) space per process

P

, where

δ

P

is the degree of

P

and

n

the number of processes in the network. Guide pairs have numerous applications, including ordered traversal or navigation of the processes in the tree. Our second self-stabilizing algorithm, which uses the guide pairs computed by the first algorithm, solves the

ranking problem

in

O

(

n

) rounds and has space complexity

O

(

b

 + 

δ

P

log

n

) in each process

P

, where

b

is the number of bits needed to store a value. The first algorithm orders the tree processes according to their topological positions. The second algorithm orders (ranks) the processes according to the values stored in them.

Ajoy K. Datta, Stéphane Devismes, Lawrence L. Larmore, Yvan Rivierre

Fault-Tolerant Algorithms for Tick-Generation in Asynchronous Logic: Robust Pulse Generation

[Extended Abstract]

The advances of deep submicron VLSI technology pose new challenges in designing robust systems, which can in principle be addressed by approaches established in fault-tolerant distributed systems research. This paper is the first step in an attempt to develop a very robust high-precision clocking system for hardware designs like systems-on-chip for critical applications. It is devoted to the design and the correctness proof of a novel Byzantine fault-tolerant self-stabilizing pulse synchronization protocol, which facilitates a direct implementation in standard asynchronous digital logic. Despite the severe implementation constraints, it offers optimal resilience and smaller complexity than all existing pulse synchronization protocols.

Danny Dolev, Matthias Függer, Christoph Lenzen, Ulrich Schmid

The South Zone: Distributed Algorithms for Alliances

We present novel results on and efficient deterministic as well as randomized synchronous message-passing distributed algorithms for generalized graph alliances, a new concept incorporating and expanding previous ones. An alliance is here a group of nodes of a connected network or a population fulfilling certain thresholds for their neighbourhood. More precisely, every node outside and inside the alliance must have a minimum number of neighbours inside the alliance. A threshold function defining this number may be specific to each node. We are interested in finding minimal alliances of generalized type: the threshold function might be any. We also investigate conditions in which it is possible to have anonymity, a praised property in population protocols.

M. C. Dourado, L. D. Penso, D. Rautenbach, J. L. Szwarcfiter

Social Market: Combining Explicit and Implicit Social Networks

The pervasiveness of the Internet has lead research and applications to focus more and more on their users. Online social networks such as Facebook provide users with the ability to maintain an unprecedented number of social connections. Recommendation systems exploit the opinions of other users to suggest movies or products based on our similarity with them. This shift from machines to users motivates the emergence of novel applications and research challenges.

In this paper, we embrace the social aspects of the Web 2.0 by considering a novel problem. We build a distributed social market that combines interest-based social networks with explicit networks like Facebook. Our Social Market (SM) allows users to identify and build connections to other users that can provide interesting goods, or information. At the same time, it backs up these connections with trust, by associating them with paths of trusted users that connect new acquaintances through the explicit network. This convergence of implicit and explicit networks yields

TAPS

, a novel gossip protocol that can be applied in applications devoted to commercial transactions, or to add robustness to standard gossip applications like dissemination or recommendation systems.

Davide Frey, Arnaud Jégou, Anne-Marie Kermarrec

TrumanBox: Improving Dynamic Malware Analysis by Emulating the Internet

Dynamic analysis of malicious software (

malware

) is a powerful tool in countering modern threats on the Internet. In dynamic analysis, a malware sample is executed in a controlled environment and its actions are logged. Through dynamic analysis, an analyst can quickly obtain an overview of malware behavior and can decide whether or not to indulge into tedious manual analysis of the sample. However, usual dynamic analysis exposes the Internet to the threats of an executed malware (like portscans) because advanced concealment techniques of malware often require full Internet access. For example, a missing link to the Internet or the unavailability of a specific server often causes the malware to not trigger its malicious behavior. In this paper, we present

TrumanBox

, a technique to emulate relevant parts of the Internet to enhance dynamic malware analysis. We show that

TrumanBox

not only prevents many threats but also enlarges the scope of the types of malware that can be analyzed dynamically.

Christian Gorecki, Felix C. Freiling, Marc Kührer, Thorsten Holz

Rendezvous Tunnel for Anonymous Publishing: Clean Slate and Tor Based Designs

Anonymous communication, and in particular anonymous Peer-to-Peer (P2P) file sharing systems, have received considerable attention in recent years. In a P2P file sharing system, there are three types of participants: publishers that insert content into the system, servers that store content, and readers that retrieve content from the servers. Existing anonymous P2P file sharing systems confer partial anonymity. They provide anonymity to participant pairs, such as servers and readers or publishers and readers, but they do not consider the anonymity of all three types of participants.

In this work we propose two solutions for anonymous P2P file sharing systems.

Both of our solutions provide anonymity to all three types of participants

. The proposed solutions are based on indexing by global hash functions (rather than an index server), dispersal of information, and three anonymity tunnels. Each anonymity tunnel is designed to protect the anonymity of a different user (publisher, server, or reader). In both solutions the reader and publisher tunnels are sender anonymity tunnels. In the first solution the third tunnel is a rendezvous tunnel, constructed by means of a random walk and terminating at the server. In the second solution, which is based on Tor, the third tunnel is built using Tor’s hidden services.

The first solution preserves anonymity in the presence of a semi-honest adversary that controls a limited number of nodes in the system. The second solution is based on Tor primitives, coping with the same adversary as that assumed in Tor. The second solution enhances Tor, ensuring publisher, server, and reader anonymity.

Ofer Hermoni, Niv Gilboa, Eyal Felstaine, Yuval Elovici, Shlomi Dolev

Snake: Control Flow Distributed Software Transactional Memory

Remote Method Invocation (RMI), Java’s remote procedure call implementation, provides a mechanism for designing distributed Java technology-based applications. It allows methods to be invoked from other Java virtual machines, possibly at different hosts. RMI uses lock-based concurrency control, which suffers from distributed deadlocks, livelocks, and scalability and composability challenges. We present

Snake-DSTM

, a distributed software transactional memory (D-STM) that is based on the RMI as a mechanism for handling remote calls and transactional memory for distributed concurrency control, as an alternative to RMI/locks. Critical sections are defined as atomic transactions, in which reads and writes to shared, local and remote objects appear to take effect instantaneously. The novelty of Snake-DSTM is in manipulating transactional memory by moving control to remote nodes, rather than remote nodes’ data being copied to the node at which the transaction runs. Transaction metadata is detached from the transactional context, and the dynamic two phase commitment protocol (D2PC) is employed to coordinate the voting process among participating nodes toward making distributed transactional commit decisions. We propose a simple programming model using (Java 5) annotations to define critical sections and remote methods. Instrumentation is used to generate code at class-load time, which significantly simplifies user-space end code. No changes are needed to the underlying virtual machine or compiler. We describe Snake-DSTM’s architecture and implementation, and report on experimental studies comparing it against competing models including RMI with mutual exclusion and read/write locks, distributed shared memory (DSM), and dataflow-based D-STM. Our studies show that Snake-DSTM outperforms competitors by up to 12× on different workloads using a 120-node system.

Mohamed M. Saad, Binoy Ravindran

POLISH: Proactive Co-operative LInk Self-Healing for Wireless Sensor Networks

In this paper we propose the first proactive co-operative link self-healing (POLISH) scheme, in which the secure link compromised in WSNs automatically self-heals with time, without the help of a server. Our scheme updates a secure link using the random data transmitted from the neighboring sensor nodes, based on the idea of the POSH scheme. It is necessary to newly take the security of a link between sensors into consideration in our scheme since such security is not considered in the POSH scheme. We conduct analytical evaluation and a simulation experiment for our scheme, and the results indicate that our scheme is very effective in self-healing.

Tatsuro Iida, Atsuko Miyaji, Kazumasa Omote

The Weakest Failure Detector to Implement a Register in Asynchronous Systems with Hybrid Communication

This paper introduces an asynchronous crash-prone hybrid system model. The system is hybrid in the way the processes can communicate. On the one side, a process can send messages to any other process. On another side, the processes are partitioned into clusters and each cluster has its own read/write shared memory. In addition to the model, a main contribution of the paper concerns the implementation of an atomic register in this system model. More precisely, a new failure detector (denoted

M

Σ) is introduced and it is shown that, when considering the information on failures needed to implement a register, this failure detector is the weakest. To that end, the paper presents an

M

Σ-based algorithm that builds a register in the considered hybrid system model and shows that it is possible to extract

M

Σ from any failure detector-based algorithm that implements a register in this model. The paper also (a) shows that

M

Σ is strictly weaker than Σ (which is the weakest failure detector to implement a register in a classical message-passing system) and (b) presents a necessary and sufficient condition to implement

M

Σ in a hybrid communication system.

Damien Imbs, Michel Raynal

Price Stabilization in Networks — What Is an Appropriate Model ?

We consider a simple network model for economic agents where each can buy commodities in the neighborhood. Their prices may be initially distinct in any node. However, by assuming some rules on new prices, we show that the distinct prices will converge to unique by iterating buy and sell operations. First, we present a protocol model in which each agent always bids an arbitrary price in the difference between his own price and the lowest price in the neighborhood, called max price difference. Next, we derive the condition that price stabilization occurs in our model. Furthermore, we consider game (auction) theoretic price determination by assuming that each agent’s value is uniformly distributed over the max price difference. Finally, we perform a simulation experiment. Our model is suitable for investigating the effects of network topologies on price stabilization.

Jun Kiniwa, Kensaku Kikuta

Dynamic Regular Registers in Systems with Churn

Distributed systems with churn, or dynamic distributed systems, allow the processes to join and leave the system at will. In this paper, we present a new consistency condition for shared read-write registers which is based on multi-writer regularity, but allows for the likelihood of the register to lose its state with some probability; we call this a

dynamic regular register

. We then describe an algorithm for implementing a dynamic regular register using copies of the register distributed among the processes. When a process joins the system, it attempts to obtain an up-to-date copy of the data from other processes. Copies of the register are updated by broadcasting information. To model the dynamicity of the system with churn, we use a continuous-time birth-death process which is a special case of continuous-time Markov processes. Then, we analyze the probability and the time duration that the dynamic regular register system keeps its state, given the joining rate and the leaving rate of the processes.

Andreas Klappenecker, Hyunyoung Lee, Jennifer L. Welch

Space-Efficient Fault-Containment in Dynamic Networks

Bounding the impact of transient small-scale faults by self”=stabilizing protocols has been pursued with independent objectives: Optimizing the system’s reaction upon topological changes (e.g. super”=stabilization), and reducing system recovery time from memory corruptions (e.g. fault”=containment). Even though transformations adding either super”=stabilization or fault”=containment to existing protocols exist, none of them preserves the other. This paper makes a first attempt to combine both objectives. We provide a transformation adding fault”=containment to silent self-stabilizing protocols while simultaneously preserving the property of self”=stabilization and the protocol’s behavior in face of topological changes. In particular, the protocol’s response to a topology change remains unchanged even if a memory corruption occurs in parallel to the topology change. The presented transformation increases the memory footprint only by a factor of 4 and adds

${\mathcal O}{1}$

bits per edge. All previously known transformations for fault”=containing self”=stabilization increase the memory footprint by a factor of 2

m

/

n

.

Sven Köhler, Volker Turau

The OCRC Fuel Cell Lab Safety System: A Self-Stabilizing Safety-Critical System

We describe the practical application of self-stabilization to a safety-critical system. The Ohio Coal Research Center (OCRC) at Ohio University has a fuel-cell laboratory that uses explosive and poisonous gases. The lab is located in and uses the ventilation system of a large campus building that houses offices, other labs, and classrooms. The OCRC fuel cell lab safety system seeks to protect lab and other building personnel in the event of a gas leak. We present the system and the use of self-stabilization to ensure that, in the presence of actual or potential hazards, the lab converges to as safe a state as possible. It is responds to environmental conditions such as gas leaks and is tolerant to faults that affect the system’s sensors and actuators.

William Leal, Micah McCreery, Daniel Faria

Relations Linking Failure Detectors Associated with k-Set Agreement in Message-Passing Systems

The

k

-set agreement problem is a coordination problem where each process is assumed to propose a value and each process that does not crash has to decide a value such that each decided value is a proposed value and at most

k

different values are decided. While it can always be solved in synchronous systems,

k

-set agreement has no solution in asynchronous send/receive message-passing systems where up to

t

 ≥ 

k

processes may crash.

A failure detector is a distributed oracle that provides processes with additional information related to failed processes and can consequently be used to enrich the computability power of asynchronous send/receive message-passing systems. Several failure detectors have been proposed to circumvent the impossibility of

k

-set agreement in pure asynchronous send/receive message-passing systems. Considering three of them (namely, the generalized quorum failure detector Σ

k

, the generalized loneliness failure detector

${\cal L}_k$

and the generalized eventual leader failure detector Ω

k

) the paper investigates their computability power and the relations that link them. It has three mains contributions: (a) it shows that the failure detector Ω

k

and the eventual version of

${\cal L}_k$

have the same computational power; (b) it shows that

${\cal L}_k$

is realistic if and only if

k

 ≥ 

n

/2; and (c) it gives an exact characterization of the difference between

${\cal L}_k$

(that is too strong for

k

-set agreement) and Σ

k

(that is too weak for

k

-set agreement).

Achour Mostéfaoui, Michel Raynal, Julien Stainer

Corona: A Stabilizing Deterministic Message-Passing Skip List

We present Corona, a deterministic self-stabilizing algorithm for skip list construction in structured overlay networks. Corona operates in the low-atomicity message-passing asynchronous system model. Corona requires constant process memory space for its operation and, therefore, scales well. We prove the general necessary conditions limiting the initial states from which a self-stabilizing structured overlay network in message-passing system can be constructed. The conditions require that initial state information has to form a weakly connected graph and it should only contain identifiers that are present in the system. We formally describe Corona and rigorously prove that it stabilizes from an arbitrary initial state subject to the necessary conditions. We extend Corona to construct a skip graph.

Rizal Mohd Nor, Mikhail Nesterenko, Christian Scheideler

Using Zero Knowledge to Share a Little Knowledge: Bootstrapping Trust in Device Networks

In device networks, trust must often be established in the field despite limited a priori knowledge of the network and the possibility of adversaries in the network environment. This paper presents a solution to the problem of bootstrapping trust that is minimal in the sense that it circumvents ongoing maintenance of security material. Specifically, security material is communicated to members of a device group just once by using zero knowledge identification in a new and efficient way, whereby devices in the group may henceforth securely verify each other as well as initialize mutual keys for confidentiality without needing to update that security material over time. In its basic form, the solution uses a base station to communicate the security material for group membership verification. The solution allows for scaling by letting the base station hierarchically delegate the task of bootstrapping to subordinate trusted nodes.

Ingy Ramzy, Anish Arora

Conflict-Free Replicated Data Types

Replicating data under Eventual Consistency (EC) allows any replica to accept updates without remote synchronisation. This ensures performance and scalability in large-scale distributed systems (e.g., clouds). However, published EC approaches are ad-hoc and error-prone. Under a formal Strong Eventual Consistency (SEC) model, we study sufficient conditions for convergence. A data type that satisfies these conditions is called a Conflict-free Replicated Data Type (CRDT). Replicas of any CRDT are guaranteed to converge in a self-stabilising manner, despite any number of failures. This paper formalises two popular approaches (state- and operation-based) and their relevant sufficient conditions. We study a number of useful CRDTs, such as sets with clean semantics, supporting both

add

and

remove

operations, and consider in depth the more complex Graph data type. CRDT types can be composed to develop large-scale distributed applications, and have interesting theoretical properties.

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski

Analysis of DSR Protocol in Event-B

This paper presents an incremental formal development of the Dynamic Source Routing (DSR) protocol in Event-B. DSR is a reactive routing protocol, which finds a route for a destination on demand, whenever communication is needed. Route discovery is an important task of any routing algorithm and formal specification of it, itself is a challenging problem. The specification is performed in a stepwise manner composing more advanced routing components between the abstract specification and topology. It is verified through a series of refinements. The specification includes safety properties as set of invariants, and liveness properties that characterize when the system reaches stable states. We establish these properties by proof of invariants, event refinement and deadlock freedom. The consequence of this incremental approach helps to achieve a high degree of automatic proof. Our approach can be useful for formalizing and developing other kinds of reactive routing protocols (i.e. AODV etc.).

Dominique Méry, Neeraj Kumar Singh

Self-Stabilizing De Bruijn Networks

This paper presents a dynamic overlay network based on the De Bruijn graph which we call

Linearized De Bruijn (LDB) network

. The LDB network has the advantage that it has a guaranteed constant node degree and that the routing between any two nodes takes at most

O

(log

n

) hops with high probability. Also, we show that there is a simple local-control algorithm that can recover the LDB network from any network topology that is weakly connected.

Andréa Richa, Christian Scheideler, Phillip Stevens

Brief Announcement: A Conjecture on Traceability, and a New Class of Traceable Networks

The problem of reconstructing the topology of a network, given a set of hop-by-hop traces of packet paths through it, is called ’network tracing’. Unfortunately, there are only a few known classes of networks (trees and odd rings) that are traceable, i.e. that have the property that a unique network topology can be reconstructed from a trace set. Here, we suggest a property that may be the reason such networks are traceable, and use it to identify a new class of traceable networks.

H. B. Acharya, Anil K. Katti, Mohamed G. Gouda

Brief Announcement: A Stabilizing Algorithm for Finding Two Edge-Disjoint Paths in Arbitrary Graphs

Given two distinct nodes

s

and

t

of a directed graph

G

 = (

V

,

E

), where

V

is the set of nodes and

E

is the set of arcs, the problem of identifying

two edge-disjoint paths

from

s

to

t

is to identify two distinct paths

Q

1

and

Q

2

from

s

to

t

such that

Q

1

and

Q

2

share no common arc.

Fawaz M. Al-Azemi, Mehmet Hakan Karaata

Brief Announcement: Towards Interoperability Standards and Services for Autonomic Systems

This paper advocates a generic, standardised approach to the problem of interoperability and proposes introduction of a centralised Interoperability Service (IS) with which Autonomic Managers (AM) register their management interests and capabilities, using a standardised management description language. A fuzzy mapping technique is used to identify potential conflicts of management interest in a conflict-risk model. The main contribution of this work is that the interoperability support is integrated into autonomic components making them

interoperability ready

in advance of their deployment.

Richard Anthony, Mariusz Pelc, Haffiz Suahib

Brief Announcement: Distributed Self-organizing Event Space Partitioning for Content-Based Publish/Subscribe Systems

Publish/subscribe systems have commonly been divided in two large families on the basis of their event-selection model [2]: topic-based and content-based systems. The former trade reduced subscription expressiveness with simpler implementations and higher performance. Conversely, the latter allow to accurately map published data in a complex event schema on top of which expressive subscriptions can be defined, but incur the cost of more complex implementations that delivers reduced performance on large distributed settings. System developers are thus faced with a choice about which kind of system is best suited to the target application. A common solution to this dilemma lies in the

event space partitioning

[4] technique: the event schema is partitioned in a number of subspaces that are then statically mapped to topics. The partitioning must be globally known and subscribers are expected to subscribe those topics where subspaces that have a non-empty intersection with their content-based subscriptions have been mapped. Undesired events (false positives) can be filtered out at the receiver side. The event space partitioning granularity strongly affects the performance of such systems: if it is excessively coarse-grained too much resources are wasted to deliver false positives, while if it is too fine-grained the number of topics that will be generated, and that must be managed by the topic based system, could easily become huge. Current solutions [3] provide sub-optimal approximations that are calculated offline and then statically applied to the system.

Roberto Beraldi, Adriano Cerocchi, Fabio Papale, Leonardo Querzoni

Brief Announcement: A Note on Replication of Documents

We prove one combinatorial result which we found useful in investigations of replication of documents in various storage systems like P2P systems or clouds.

Jacek Cichoń, Rafał Kapelko, Karol Marchwicki

Brief Announcement: A Stable and Robust Membership Protocol

In this paper, we summarize the core ideas of our stable and robust membership protocol, which is fully decentralized. After convergence, each node of the overlay graph has expected in- and out-degrees scaling logarithmically with the size of the network (around 2ln (

n

)), and that the diameter of the overlay graph remains at

$\frac{\ln(n)}{\ln(2\ln(n))}+O(1)$

. Our protocol restores the desirable properties of the overlay network from an arbitrary state, which might result from a massive but temporary disruption.

Ajoy K. Datta, A. -M. Kermarrec, Lawrence L. Larmore, E. Le Merrer

Brief Announcement: Sorting on Skip Chains

Sorting values on a chain of processes is a well-known problem, and a number of algorithms has been published [1,2]. We consider here a generalization of this problem, where the processes that have values, called

major processes

, are separated from each other by any number of intermediate processes, called

relay processes

, which do not have their own values, although they can read and write the major values while doing their job of relaying those values.

Ajoy K. Datta, Stéphane Devismes, Lawrence L. Larmore

Brief Announcement: A Concurrent Partial Snapshot Algorithm for Large-Scale and Dynamic Distributed Systems

We propose a concurrent partial snapshot algorithm (

CSS algorithm

) to extend a previously proposed sub-snapshot algorithm (SSS algorithm) [2] by introducing a method of merging multiple snapshots that are concurrently initiated by different nodes. In earlier work [5,6], efficient merging algorithms have already been introduced for CL algorithm. On the other hand, the main issue of our merging algorithm is to cope with dynamic situations based on SSS algorithm. Since the SSS algorithm is an extension of Chandy-Lamport snapshot algorithm (CL algorithm) [1], it allows large-scale and dynamic situations in snapshots. A dynamic situation means that nodes can join and leave freely during the execution of a snapshot algorithm. A snapshot algorithm for the dynamic situation has also been proposed [4]; however in this algorithm, nodes must stop sending application messages during its execution of the snapshot algorithm. Moreover, for concurrent snapshots, it has to cancel a portion of snapshot algorithms. Our algorithm has successfully removed these restrictions.

Yonghwan Kim, Tadashi Araragi, Junya Nakamura, Toshimitsu Masuzawa

Brief Announcement: Fault-Tolerant Object Location in Large Compute Clusters

A so-called

single system image

(SSI) allows threads in a distributed shared memory (DSM) system to access data and other resources in a location transparent manner. In this brief announcement, we present our ongoing research towards fault-tolerant algorithms that locate objects in such systems. In particular, we build our algorithms on a multi-version, object-based software transactional memory (STM) system, in which objects form a sequence of immutable object versions. Our algorithms are fully decentralized and allow resources to be added and removed at run-time without disturbing the application.

Björn Saballus, Stephan-Alexander Posselt, Thomas Fuhrmann

Brief Announcement: Faster Gossiping in Bidirectional Radio Networks with Large Labels

We study the problem of deterministic gossiping in unknown ad-hoc bidirectional radio networks, when nodes can have polynomially large labels. We present a deterministic protocol which takes

$O(n \lg^2 n \lg \lg n)$

rounds, improving upon the previous best result for the problem by Gasienec, Potapov, Pagourtizis [

Deterministic Gossiping in Radio Networks with Large labels

, Algorithmica 47(1) (2007), pp 97-117], by a

$O(\lg n)$

factor.

Shailesh Vaya

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise