Stabilization, Safety, and Security of Distributed Systems

Social networks and collaborative tagging systems have taken off at an unexpected scale and speed (Facebook, YouTube, Flickr, Last.fm, Delicious, etc). Web content is now generated by you, me, our friends and millions of others. This represents a revolution in usage and a great opportunity to leverage collaborative knowledge to enhance the user’s Internet experience. The

Gossple

project aims at precisely achieving this: automatically capturing affinities between users that are potentially unknown yet share similar interests, or exhibiting similar behaviors on the Web. This fully personalizes the search process, increasing the ability of a user to find relevant content. This personalization calls for decentralization. (1) Centralized servers might dissuade users from generating new content for they expose their privacy and represent a single point of attack. (2) The amount of information to store grows exponentially with the size of the system and centralized systems cannot sustain storing a growing amount of data at a user granularity. We believe that the salvation can only come from a fully decentralized user centric approach where every participant is entrusted to harvest the Web with information relevant to her own activity. This poses a number of scientific challenges: How to discover similar users, how to define the relevant metrics for such personalization, how to preserve privacy when needed, how to deal with free-riders and misheavior and how to manage efficiently a growing amount of data.

Fault tolerance is one of the main concepts in distributed computing. It has been tackled from different angles, e.g. by building replicated systems that can survive crash failures of individual components, or even systems that can tolerate a minority of arbitrarily malicious (“Byzantine”) participants.

Self-stabilization, a fault tolerance concept coined by the late Edsger W. Dijkstra in 1973 [1,2], is of a different stamp. A self-stabilizing system must survive arbitrary failures, beyond Byzantine failures, including for instance a total wipe out of volatile memory at all nodes. In other words, the system must self-heal and converge to a correct state even if starting in an arbitrary state, provided that no further faults happen.

Consider a logical structure

${\cal S}$

, constructed over a given network

G

, which is intended to efficiently support various services on

G

. This logical structure is supposed to possess certain desirable properties, measured with respect to

G

and represented by some requirement predicate

${\cal P}({\cal S},G)$

. Now consider a failure event

F

affecting some of the network’s vertices and edges. Making

${\cal S}$

fault-tolerant means reinforcing it so that subsequent to the failure event, its surviving part

${\cal S}'$

continues to satisfy

${\cal P}$

. One may insist on imposing the requirements with respect to the

original network

G

, i.e., demanding that the surviving structure

${\cal S}'$

satisfies the predicate

${\cal P}({\cal S}',G)$

. The idea behind

competitive fault tolerance

is that it may sometimes be more realistic and more productive to evaluate the performance of the surviving

${\cal S}'$

after the failure event not with respect to

G

(which at the moment is no longer in existence anyway), but rather with respect to the

surviving network

G

′ = 

G

 ∖ 

F

, which in a sense is the best one can hope for. Hence, we say that the structure

${\cal S}$

enjoys

competitive fault-tolerance

if subsequent to a failure event

F

, its surviving part

${\cal S}'$

satisfies the requirement predicate

${\cal P}({\cal S}',G')$

. The paper motivates the notion of competitive fault tolerance, compares it with the more demanding alternative approach, and illustrates it on a number of representative examples.

Given the non-determinism and race conditions in distributed programs, the ability to provide assurance about them is crucial. Our work focuses on incremental synthesis where we modify a distributed programs to add self-stabilization. We concentrate on reducing the time complexity of such synthesis using parallelism. We apply these techniques in the context of constraint satisfaction. In particular, incremental synthesis of self-stabilizing programs requires adding recovery actions to satisfy the constraint that are true in the legitimate states. We consider two approaches to speedup the synthesis algorithm: first, the use of the multiple constraints that have to be satisfied during synthesis; second, the use of the distributed nature of the programs being synthesized. We show that our approaches provide significant reductions in the synthesis time.

Traceroute is a widely used program for computing the topology of any network in the Internet. Using Traceroute, one starts from a node and chooses any other node in the network. Traceroute obtains the sequence of nodes that occur between these two nodes, as specified by the routing tables in these nodes. Each use of Traceroute in a network produces a trace of nodes that constitute a simple path in this network. In every trace that is produced by Traceroute, each node occurs either by its unique identifier, or by the anonymous identifier“*”. In this paper, we introduce the first theory aimed at answering the following important question. Is there an algorithm to compute the topology of a network

N

from a trace set

T

that is produced by using Traceroute in network

N

, assuming that each edge in

N

occurs in at least one trace in

T

, and that each node in

N

occurs by its unique identifier in at least one trace in

T

? We prove that the answer to this question is “No” if

N

is an even ring or a general network. However, it is ”Yes” if

N

is a tree or an odd ring. The answer is also “No” if

N

is mostly-regular, but “Yes” if

N

is a mostly-regular even ring.

This paper studies the development of autonomic and secure Virtual Organisations (VOs) when following the chemical-programming paradigm. We have selected the Higher-Order Chemical Language (HOCL) as the representative of the chemical paradigm, due mainly to its generality, its implicit autonomic property, and its potential application to emerging computing paragidms such as Grid computing and service computing. We have advocated the use of aspect-oriented techniques, where autonomicity and security can be seen as cross-cutting concerns impacting the whole system. We show how HOCL can be used to model VOs, exemplified by a VO system for the generation of digital products. We develop patterns for HOCL, including patterns for traditional security properties such as authorisation and secure logs, as well as autonomic properties such as self-protection and self-healing. The patterns are applied to HOCL programs following an aspect-oriented approach, where aspects are modelled as transformation functions that add to a program a cross-cutting concern.

Developing

self-stabilizing

solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. This remark holds for a large variety of models. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an

automatic transformer

for algorithms in

population protocols model

. This model introduced recently for networks with a large number of resource-limited mobile agents. For our purposes, we use a variant of this model. Mainly, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication “speed” and considered through the notion of

cover time

. The automatic transformer takes as an input an algorithm solving a static problem and outputs a self-stabilizing algorithm for the same problem. We prove that our transformer is correct and we analyze its stabilization complexity.

We describe an approach to the analysis of protocols for wireless sensor networks in scenarios with mobile nodes and dynamic link quality. The approach is based on the theorem proving system PVS and can be used for formal specification, automated simulation and verification of the behaviour of the protocol. In order to demonstrate the applicability of the approach, we analyse the reverse path forwarding algorithm, which is the basic technique used for diffusion protocols for wireless sensor networks.

Among all classes of faults, Byzantine faults form the most general modeling of value faults. Traditionally, in the Byzantine fault model, faults are statically attributed to a set of up to

t

processes. This, however, implies that in this model a process at which a value fault occurs is forever “stigmatized” as being Byzantine, an assumption that might not be acceptable for long-lived systems, where processes need to be reintegrated after a fault.

We thus consider a model where Byzantine processes can recover in a predefined recovery state, and show that consensus can be solved in such a model.

This paper proposes a fully dynamic self-stabilizing algorithm for the Steiner tree problem. The Steiner tree problem aims at constructing a Minimum Spanning Tree (MST) over a subset of nodes called Steiner members, or Steiner group usually denoted

S

. Steiner trees are good candidates to efficiently implement communication primitives such as publish/subscribe or multicast, essential building blocks in the design of middleware architectures for the new emergent networks (e.g. P2P, sensor or adhoc networks). Our algorithm returns a log|

S

|-approximation of the optimal Steiner tree. It improves over existing solutions in several ways. First, it is fully dynamic, in other words it withstands the dynamism when both the group members and ordinary nodes can join or leave the network. Next, our algorithm is self-stabilizing, that is, it copes with nodes memory corruption. Last but not least, our algorithm is

superstabilizing

. That is, while converging to a correct configuration (i.e., a Steiner tree) after a modification of the network, it keeps offering the Steiner tree service during the stabilization time to all members that have not been affected by this modification.

In the

k

-set agreement problem, each process (in a set of

n

processes) proposes a value and has to decide a proposed value in such a way that at most

k

different values are decided. While this problem can easily be solved in asynchronous systems prone to

t

process crashes when

k

 > 

t

, it cannot be solved when

k

 ≤ 

t

. Since several years, the failure detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the

k

-set agreement problem in read/write shared-memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases

k

 = 1 (consensus) and

k

 = 

n

 − 1 (set agreement). This paper introduces a candidate for the general case. It presents a new failure detector class, denoted

${\it \Pi}_k$

, and shows

${\it \Pi}_1={\it \Sigma}\times {\it \Omega}$

(the weakest class for

k

 = 1), and

${\it \Pi}_{n-1}={\cal L}$

(the weakest class for

k

 = 

n

 − 1). Then, the paper investigates the structure of

${\it \Pi}_k$

and shows it is the combination of two failures detector classes denoted

${\it \Sigma}_k$

and

${\it \Omega}_k$

(that generalize the previous “quorums” and “eventual leaders” failure detectors classes). Finally, the paper proves that

${\it \Sigma}_k$

is a necessary requirement (as far as information on failure is concerned) to solve the

k

-set agreement problem in message-passing systems. The paper presents also a

${\it \Pi}_{n-1}$

-based algorithm that solves the (

n

 − 1)-set agreement problem. This algorithm provides us with a new algorithmic insight on the way the (

n

 − 1)-set agreeement problem can be solved in asynchronous message-passing systems (insight from the point of view of the non-partitioning constraint defined by

${\it \Sigma}_{n-1}$

).

This paper addresses the byzantine resilience lower bound for the convergence in semi-synchronous robot networks. We prove that 3

f

 + 1 robots are needed for convergence to tolerate up to

f

Byzantine robots. Our work generalizes the previously established lower bound proved for the class of cautious algorithms only. Additionally we propose the first deterministic algorithm that matches this lower bound and performs in the asynchronous CORDA model. Our algorithm works under bounded scheduling assumptions for oblivious robots moving in a uni-dimensional space.

Gossip protocols are well known to provide reliable and robust dissemination protocols in highly dynamic systems. Yet, they suffer from high redundancy in the last phase of the dissemination. In this paper, we combine fountain codes (rateless erasure-correcting codes) together with gossip protocols for a robust and fast content dissemination in large-scale dynamic systems. The use of fountain enables to eliminate the unnecessary redundancy of gossip protocols. We propose the design of

FoG

, which fully exploits the first exponential growth phase (where the data is disseminated exponentially fast) of gossip protocols while avoiding the need for the shrinking phase by using fountain codes.

FoG

voluntarily increases the number of disseminations but limits those disseminations to the exponential growth phase. In addition,

FoG

creates a split-graph overlay that splits the peers between encoders and forwarders. Forwarder peers become encoders as soon as they have received the whole content. In order to benefit even further and quicker from encoders,

FoG

biases the dissemination towards the most advanced peers to make them complete earlier.

We assess

FoG

through simulation. We show that

FoG

outperforms by 50% a simple push protocol with respect to overhead and improves by 30% the termination time.

A

snap-stabilizing

protocol, starting from any configuration, always behaves according to its specification. In this paper, we are interested in message forwarding problem in a message-switched network. In this problem, we must manage resources of the system to deliver messages to any processor of the network. In this purpose, we use information given by a routing algorithm. By the context of stabilization (in particular, the system starts in any configuration), this information can be corrupted. In [1], authors show that there exists snap-stabilizing algorithms for this problem (in the

state model

). That implies that we can ask the system to begin forwarding messages without losses even if routing informations are initially corrupted.

In this paper, we propose another snap-stabilizing algorithm for this problem which improves the space complexity of the one of [1].

This paper presents an exercise in fault-containment on a weakly-stabilizing system. The exercise uses the weakly stabilizing leader election algorithm in [3], and shows how the effect of single faults can be contained both in space and in time. Our algorithm confines the effect of any single fault to the constant-distance neighborhood of the faulty process, and the contamination number is restricted to 4 with high probability for an array of processes. We also show that the expected recovery time from a single fault is independent of the array size, i.e., the solution is fault-containing in time too.

For large distributed systems built from inexpensive components, one expects to see incessant failures. This paper proposes two models for such faults and analyzes two well-known self-stabilizing algorithms under these fault models. For a small number of processes, the properties of interest are verified automatically using probabilistic model-checking tools. For a large number of processes, these properties are characterized using asymptotic bounds from a direct Markov chain analysis and approximated by numerical simulations.

Self-stabilization is an elegant way of realizing non-masking fault-tolerant systems. Sustained research over last decades has produced multiple self-stabilizing algorithms for many problems in distributed computing. In this paper, we present a framework to evaluate multiple self-stabilizing solutions under a fault model that allows intermittent transient faults. To that end, metrics to quantify the dependability of self-stabilizing systems are defined. It is also shown how to derive models that are suitable for probabilistic model checking in order to determine those dependability metrics. A heuristics-based method is presented to analyze counterexamples returned by a probabilistic model checker in case the system under investigation does not exhibit the desired degree of dependability. Based on the analysis, the self-stabilizing algorithm is subsequently refined.

This paper analyses the robustness of self-organizing (engineered) systems to perturbations (faults or environmental changes). It considers that a self-organizing system is embedded into an environment, the main active building blocks are agents, one or more self-organizing mechanisms regulate the interaction among agents, and agents manipulate artifacts, i.e. passive entities maintained by the environment. Perturbations then need to be identified at the level of these four design elements. This paper discusses the boundaries of normal and abnormal behaviour in self-organizing systems and provides guidelines for designers to determine which perturbation in which part of the system leads to a failure.

We present algorithms that reduce the time complexity and improve the scalability of robust storage for unauthenticated data. Robust storage ensures progress under every condition (wait-freedom) and never returns an outdated value (regularity) nor a forged value (Byzantine fault tolerance). The algorithms use

secret tokens

, which are values randomly selected by the clients and attached to the data written into the storage. Tokens are secret because they cannot be predicted by the attacker before they are used, and thus revealed, by the clients. Our algorithms do not rely on unproven cryptographic assumptions as algorithms based on self-verifying data. They are optimally-resilient, and ensure that reads complete in two communication rounds if readers do not write into the storage, or in one communication round otherwise.

Consider a fully connected network where up to

t

processes may crash, and all processes start in an arbitrary memory state. The self-stabilizing firing squad problem consists of eventually guaranteeing simultaneous response to an external input. This is modeled by requiring that the non-crashed processes “fire” simultaneously if some correct process received an external “

go

” input, and that they only fire as a response to some process receiving such an input. This paper presents

Fire-Squad

, the first self-stabilizing firing squad algorithm.

The

Fire-Squad

algorithm is optimal in two respects: (a) Once the algorithm is in a safe state, it fires in response to a

go

input as fast as any other algorithm does, and (b) Starting from an arbitrary state, it converges to a safe state as fast as any other algorithm does.

We present schemes for providing anonymous transactions while privacy and anonymity are preserved, providing user anonymous authentication in distributed networks such as the Internet. We first present a practical scheme for anonymous transactions while the transaction resolution is assisted by a Trusted Authority. This practical scheme is extended to a theoretical scheme where a Trusted Authority is not involved in the transaction resolution. Given an authority that generates for each player hard to produce evidence

EVID

(e. g., problem instance with or without a solution) to each player, the identity of a user

U

is defined by the ability to prove possession of said evidence. We use Zero-Knowledge proof techniques to repeatedly identify

U

by providing a proof that

U

has evidence

EVID

, without revealing

EVID

, therefore avoiding identity theft.

In both schemes the authority provides each user with a unique random string. A player

U

may produce unique user name and password for each other player

S

using a one way function over the random string and the

IP

address of

S

. The player does not have to maintain any information in order to reproduce the user name and password used for accessing a player

S

. Moreover, the player

U

may execute transactions with a group of players

S

U

in two phases; in the first phase the player interacts with each server without revealing information concerning its identity and without possibly identifying linkability among the servers in

S

U

. In the second phase the player allows linkability and therefore transaction commitment with all servers in

S

U

, while preserving anonymity (for future transactions).

The objective of this paper is three-fold. First, we specify what it means for a fixed point of a stabilizing distributed system to be a Nash equilibrium. Second, we present methods that can be used to verify whether or not a given fixed point of a given stabilizing distributed system is a Nash equilibrium. Third, we argue that in a stabilizing distributed system, whose fixed points are all Nash equilibria, no process has an incentive to perturb its local state, after the system reaches one fixed point, in order to force the system to reach another fixed point where the perturbing process achieves a better gain. If the fixed points of a stabilizing distributed system are all Nash equilibria, then we refer to the system as perturbation-proof. Otherwise, we refer to the system as perturbation-prone. We identify four natural classes of perturbation-(proof/prone) systems. We present system examples for three of these classes of systems, and show that the fourth class is empty.

Software systems are increasingly expected to dynamically self-adapt to the changing environments. One of the principle adaptation mechanisms is dynamic recomposition of application components. This paper addresses the key issues that arise when external context knowledge is used to steer the run-time (re)composition process. In order to integrate such knowledge into this process, A Continuous Context-Aware Deployment and Adaptation (ACCADA) framework is proposed. To support run-time component composition, the essential runtime abstractions of the underlying component model are studied. By using a layered modeling approach, our framework gradually incorporates design-time as well as run-time knowledge into the component composition process. Service orientation is employed to facilitate the changes of adaptation policy. Results show that our framework has significant advantages over traditional approaches in light of flexibility, resource usage and lines of code. Although our experience was done based on the OSGi middleware, we believe our findings to be general to other architecture-based management systems.

This paper presents a deterministic self-stabilizing algorithm that computes a 3-approximation vertex cover in anonymous networks. It reaches a legal state after

O

(

n

 + 

m

) moves or 2

n

 + 1 rounds respectively and recovers from a single fault within a constant containment time. The contamination number is

$2{\it \Delta} + 1$

. An enhanced version of this algorithm achieves a 2-approximation on trees.

Self-stabilizing distributed control is often modeled by token abstractions. For a cyber-physical system, tokens may represent physical objects whose movement is controlled. The problem studied in this paper is to ensure that a synchronous system with

m

circulating tokens has at least

d

distance between tokens. This problem is first considered in a ring where

d

is given whilst

m

and the ring size

n

are unknown. The protocol solving this problem can be uniform, with all processes running the same program, or it can be non-uniform, with some processes acting only as token relays. The protocol for this first problem is simple, and can be expressed with Petri net formalism. A second problem is to maximize

d

when

m

is given, and

n

is unknown. For the second problem, the paper presents a non-uniform protocol with a single corrective process.

The

Borowsky-Gafni

(

BG

)

simulation

algorithm is a powerful tool that allows a set of

t

 + 1 asynchronous sequential processes to wait-free simulate (i.e., despite the crash of up to

t

of them) a large number

n

of processes under the assumption that at most

t

of these processes fail (i.e., the simulated algorithm is assumed to be

t

-resilient). The BG simulation has been used to prove solvability and unsolvability results for crash-prone asynchronous shared memory systems.

In its initial form, the BG simulation applies only to colorless decision tasks, i.e., tasks in which nothing prevents processes to decide the same value (e.g., consensus or

k

-set agreement tasks). Said in another way, it does not apply to decision problems such as renaming where no two processes are allowed to decide the same new name. Very recently (STOC 2009), Eli Gafni has presented an

extended BG

simulation

algorithm (GeBG) that generalizes the basic BG algorithm by extending it to “colored” decision tasks such as renaming. His algorithm is based on a sequence of sub-protocols where a sub-protocol is either the base agreement protocol that is at the core of BG simulation, or a commit-adopt protocol.

This paper presents the core of an extended BG simulation algorithm that is particularly simple. This algorithm is based on two underlying objects: the base agreement object used in the BG simulation (as does GeBG), and (differently from GeBG) a new simple object that we call

arbiter

. More precisely, (1) while each of the

n

simulated processes is simulated by each simulator, (2) each of the first

t

 + 1 simulated processes is associated with a predetermined simulator that we called its “owner”. The arbiter object is used to ensure that the permanent blocking (crash) of any of these

t

 + 1 simulated processes can only be due to the crash of its owner simulator. After being presented in a modular way, the proposed extended BG simulation algorithm is proved correct.

Let us consider the gathering problem of

n

anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a non-predefined point. While the gathering problem cannot be solved deterministically without any additional capability to robots, randomized approach easily allows it to be solvable. However, only the randomized solution taking expected round complexity exponential of

n

is currently known. Motivated by this fact, we investigate the feasibility of polynomial-expected-round randomized gathering in this paper. Our first contribution is to give a negative result about the round complexity of randomized gathering. It is proved that any algorithm without no additional assumption has

${\it \Omega}(\mathrm{exp}(n))$

expected-round lower bound. This lower bound yields a question: What additional assumptions are necessary to achieve gathering in polynomial expected rounds? We address this question from the aspect of multiplicity detection. This paper newly introduces two weaker variants of multiplicity detection capability, called

local-strong

and

local-weak

multiplicity, and investigates whether those capabilities permit polynomial-expected-round gathering or not. Our second contribution is to reveal the power of local (strong/weak) multiplicity by showing that local-strong multiplicity detection allows

O

(

n

)-expected round gathering but local-weak multiplicity detection takes an exponential-time lower bound. These results imply that those two kinds of multiplicity-detection capabilities have inherently large difference about their computational powers.

In recent years peer-to-peer (P2P) technology has been adopted by Internet-based malware as a fault tolerant and scalable communication medium for self-organization and survival. It has been shown that malicious P2P networks would be nearly impossible to uncover if they operated in a

stealth mode

, that is, using only a small constant number of fixed overlay connections per node for communication. While overlay networks of a small constant maximal degree are generally considered to be unscalable, we argue in this paper that it is possible to design them to be scalable, efficient and robust. This is an important finding from a security point of view: we show that stealth mode P2P malware that is very difficult to discover with state-of-the-art methods is a plausible threat. In this paper we discuss algorithms and theoretical results that support the scalability of stealth mode overlays, and we present realistic simulations using an event based implementation of a proof-of-concept system. Besides P2P botnets, our results are also applicable in scenarios where relying on a large number of overlay connections per node is not feasible because of cost or the limited number of communication channels available.

Real-time performance is critical for many time-sensitive applications of wireless sensor networks. We present a constrained flooding protocol, called CFlood, which enhances the deadline satisfaction ratio per unit energy consumption of time-sensitive packets in sensor networks. CFlood improves real-time performance by flooding, but effectively constrains energy consumption by controlling the scale of flooding, i.e., flooding only when necessary. If unicasting meets the distributed sub-deadline of a hop, CFlood aborts further flooding even after flooding has occurred in the current hop. Our simulation-based experimental studies show that CFlood achieves higher deadline satisfaction ratio per unit energy consumption than previous multipath forwarding protocols, especially in sparsely deployed or unreliable sensor network environments.

A wireless sensor network is a set of nodes, each is equipped with sensors and a wireless communication device. Cached Sensornet Transform (CST for short) is a methodology for design and implementation of self-stabilizing algorithms for sensor networks. It transforms a self-stabilizing algorithm in the abstract computational model to a program for sensor networks. In the literature, only CST transformation of silent self-stabilizing algorithms have been investigated, while non-silent ones have not been investigated. Our contribution in this paper is threefold. We present a counterexample of a non-silent algorithm transformed by CST that does not behave correctly despite the original algorithm is correct. We show a sufficient condition for original algorithms and networks such that a transformed algorithm by CST behaves correctly. We present a token circulation algorithm that behaves correctly by CST, and derive upper bound of its expected convergence time.

We consider a malicious unfair adversary which generates an undetectable fault by local checks, called an intentional fault. Though the possibility of such a fault has ever been suggested, details of its influence and handling are unknown. We assume the intentional fault in a self-stabilizing mutual exclusion protocol, a hybrid of previously proposed ones that complement each other. In the hybrid protocol, we can cope with the fault by using optional strategies, whether or not sending a minor token, which plays a role of preventing the contamination from spreading. We construct a payoff matrix between a group of privileged processes and an adversary, and consider a multistage two-person zero sum game. We interpret the game in two ways: whether it continues or replays the game after an ME(mutual exclusion)-violating repair, in which more than one unexpected privileges are given. For each case, we evaluate the ability of malicious unfair adversary by using a mixed strategy. Our idea is also considered as a general framework for strengthening an algorithm against an intentional fault.

We study robustness issues of basic exploration tasks of simple robots inside a polygon

P

when sensors provide possibly faulty information about the unlabelled environment

P

. Ideally, the simple robot we consider is able to sense the number and the order of visible vertices, and can move to any such visible vertex. Additionally, the robot senses whether two visible vertices form an edge of

P

. We call this sensing a

combinatorial vision

. The robot can use pebbles to mark vertices. If there is a visible vertex with a pebble, the robot knows (senses) the index of this vertex in the list of visible vertices in counterclockwise order. It has been shown [1] that such a simple robot, using one pebble, can virtually label the visible vertices with their global indices, and navigate consistently in

P

. This allows, for example, to compute the map or a triangulation of

P

. In this paper we revisit some of these computational tasks in a

faulty

environment, in that we model situations where the sensors “see” two visible vertices as one vertex. In such a situation, we show that a simple robot with one pebble cannot even compute the number of vertices of

P

. We conjecture (and discuss) that this is neither possible with two pebbles. We then present an algorithm that uses three pebbles of two types, and allows the simple robot to count the vertices of

P

. Using this algorithm as a subroutine, we present algorithms that reconstruct the map of

P

, as well as the correct visibility at every vertex of

P

.

We study the problem of finding peers matching a given availability pattern in a peer-to-peer (P2P) system. Motivated by practical examples, we specify two formal problems of availability matching that arise in real applications:

disconnection matching

, where peers look for partners expected to disconnect at the same time, and

presence matching

, where peers look for partners expected to be online simultaneously in the future. As a scalable and inexpensive solution, we propose to use epidemic protocols for topology management; we provide corresponding metrics for both matching problems. We evaluated this solution by simulating two P2P applications,

task scheduling

and

file storage

, over a new trace of the eDonkey network, the largest available with availability information. We first proved the existence of regularity patterns in the sessions of 14M peers over 27 days. We also showed that, using only 7 days of history, a simple predictor could select predictable peers and successfully predicted their online periods for the next week. Finally, simulations showed that our simple solution provided good partners fast enough to match the needs of both applications, and that consequently, these applications performed as efficiently at a much lower cost. We believe that this work will be useful for many P2P applications for which it has been shown that choosing good partners, based on their availability, drastically improves their performance and stability.

DHT-based P2P systems provide a fault-tolerant and scalable mean to store data blocks in a fully distributed way. Unfortunately, recent studies have shown that if connection/disconnection frequency is too high, data blocks may be lost. This is true for most current DHT-based system’s implementations. To avoid this problem, it is necessary to build really efficient replication and maintenance mechanisms. In this paper, we study the effect of churn on an existing DHT-based P2P system such as DHash or PAST. We then propose solutions to enhance churn tolerance and evaluate them through discrete event simulations.

Power management in wireless networks has been thoroughly studied and applied in many different contexts. However, the problem has not been tackled from a multiple-agent perspective (MA). This paper intends to do so in the context of a wireless network comprised of distributed base stations using macrodiversity. The proposed design is shown to provide efficient use of macrodiversity resources and high energy efficiency when compared with more traditional algorithms. Moreover, the power control mechanism is completely decentralized, while avoiding direct information exchange or excessive signaling, which makes it highly scalable. Its auto-configuration property, stemming from its MA basis, offers high adaptivity when experiencing high or low interference levels. This leads to a naturally balanced resource usage, while also maintaining nearly full efficiency with only a reduced set of discrete power levels, thus making low-cost electronic implementation practical.

Maintaining redundancy in P2P storage systems is essential for reliability guarantees. Numerous P2P storage system maintenance algorithms have been proposed in the last years, each supposedly improving upon the previous approaches. We perform a systematic comparative study of the various strategies taking also into account the influence of different garbage collection mechanisms, an issue not studied so far. Our experiments show that while some strategies generally perform better than some others, there is no universally best strategy, and their relative superiority depends on various other design choices as well as the specific evaluation criterion. Our results can be used by P2P storage systems designers to make prudent design decisions, and our exploration of the various evaluation metrics also provides a more comprehensive framework to compare algorithms for P2P storage systems. While there are numerous network simulators specifically developed even to simulate peer-to-peer networks, there existed no P2P storage simulators - a byproduct of this work is a generic modular P2P storage system simulator which we provide as open-source. Different redundancy, maintenance, placement, garbage-collection policies, churn scenarios can be easily integrated to the simulator to try out new schemes in future, and provides a common framework to compare (future) p2p storage systems designs - something which has not been possible so far.

We present two OBDD based model checking algorithms for the verification of Nash equilibria in finite state mechanisms modeling

Multiple Administrative Domains

(MAD) distributed systems with possibly colluding agents (

coalitions

) and with possibly faulty or malicious nodes (Byzantine agents). Given a finite state mechanism, a

proposed protocol

for each agent and the

maximum sizes

f

for Byzantine agents and

q

for agents collusions, our model checkers return

Pass

if the proposed protocol is an

ε

-

f

-

q

-Nash equilibrium, i.e. no coalition of size up to

q

may have an interest greater than

ε

in deviating from the proposed protocol when up to

f

Byzantine agents are present,

Fail

otherwise. We implemented our model checking algorithms within the NuSMV model checker: the first one

explicitly

checks equilibria for each coalition, while the second represents

symbolically

all coalitions. We present experimental results showing their effectiveness for moderate size mechanisms. For example, we can verify coalition Nash equilibria for mechanisms which corresponding normal form games would have more than 5 ×10

21

entries. Moreover, we compare the two approaches, and the explicit algorithm turns out to outperform the symbolic one. To the best of our knowledge, no model checking algorithm for verification of Nash equilibria of mechanisms with coalitions has been previously published.

Aging effect in next-generation technologies will play a major role in determining system reliability. In particular, wear-out impact due to Negative Bias Temperature Instability (NBTI) will cause an increase in circuit delays of up to 10% in three years [8]. In these systems, NBTI-induced aging can be slowed-down by inserting periods of recovery where the core is functionally idle and gate input is forced to a specific state. This effect can be exploited to impose a given common target lifetime for all the cores. In this paper we present a technique that allows core-wear-out dependent insertion of recovery periods during loop execution in MPSoCs. Performance loss is compensated based on the knowledge of recovery periods. Loop iterations are re-distributed so that cores with longer recovery are allocated less iterations.

Graph searching games have been extensively studied in the past years. The graph searching problem involves a team of searchers who are attempting to capture a fugitive moving along the edges of the graph. In this paper we consider the graph searching problem in a network environment, namely a tree network. Searchers are software programs and the fugitive is a virus that spreads rapidly. Every node of the network which the virus may have reached, becomes contaminated. The purpose of the game is to clean the network. In real world distributed systems faults can occur and thus it is desirable for an algorithm to be able to facilitate the cleaning of a network in an optimal way, and also to reconfigure on the fly.

In this paper we give the first self-stabilizing algorithm for solving the graph searching problem in trees. Our algorithm stabilizes after

O

(

n

3

) time steps under the distributed adversarial daemon. Our algorithm solves the node searching variant of the graph searching problem, but can with small modifications also solve edge and mixed searching.

We propose a communication scheme for GALS systems with independent but approximately synchronized clock sources, which guarantees high-speed metastability-free communication between any two peers via bounded-size FIFO buffers. The proposed approach can be used atop of any multi-synchronous clocking system that guarantees a synchronization precision in the order of several clock cycles, like our fault-tolerant DARTS clocks. We determine detailed formulas for the required communication buffer size, and prove that this choice indeed guarantees metastability-free communication between correct peers, at maximum clock speed. We also describe a fast and efficient implementation of our scheme, and calculate the required buffer size for a sample test scenario. Experimental results confirm that the size lower bounds provided by our formulas are tight in this setting.

The problem of self-optimization and adaptation in the context of customizable systems is becoming increasingly important with the emergence of complex software systems and unpredictable execution environments. Here, a general framework for automatically deciding on when and how to adapt a system whenever it deviates from the desired behavior is presented. In this framework, the adaptation targets of the system are described in terms of a high-level policy that establishes goals for a set of performance indicators. The decision process is based on information provided independently for each service that describes the available adaptations, their impact on performance indicators, and any limitations or requirements. The technique consists of both offline and online phases. Offline, rules are generated specifying service adaptations that may help to achieve the specified goals when a given change in the execution context occurs. Online, the corresponding rule is evaluated when a change occurs to choose which adaptations to perform. Experimental results using a prototype framework in the context of a web-based application demonstrate the effectiveness of this approach.

This paper develops a framework for wireless security that provides confidentiality, identity authentication, message authentication, integrity, sender non-repudiation, receiver non-repudiation and anonymity. Our framework is based on two physical primitives: collaborative jamming and spatial signature enforcement. Notably, it eschews the use of shared secrets, while providing a cryptosystem that is no less secure than conventional cryptosystems.

We introduce the Read-Write-Coding-System (RWC) – a very flexible class of linear block codes that generate efficient and flexible erasure codes for storage networks. In particular, given a message

x

of

k

symbols and a codeword

y

of

n

symbols, an RW code defines additional parameters

k

 ≤ 

r

,

w

 ≤ 

n

that offer enhanced possibilities to adjust the fault-tolerance capability of the code. More precisely, an RWC provides linear

$\left(n,k,d\right)$

-codes that have (a) minimum distance

d

 = 

n

 − 

r

 + 1 for any two codewords, and (b) for each codeword there exists a codeword for each other message with distance of at most

w

. Furthermore, depending on the values

r

,

w

and the code alphabet, different block codes such as parity codes (e.g. RAID 4/5) or Reed-Solomon (RS) codes (if

r

 = 

k

and thus,

w

 = 

n

) can be generated. In storage networks in which I/O accesses are very costly and redundancy is crucial, this flexibility has considerable advantages as

r

and

w

can optimally be adapted to read or write intensive applications; only

w

symbols must be updated if the message

x

changes completely, what is different from other codes which always need to rewrite

y

completely as

x

changes. In this paper, we first state a tight lower bound and basic conditions for all RW codes. Furthermore, we introduce special RW codes in which all mentioned parameters are adjustable even online, that is, those RW codes are adaptive to changing demands. At last, we point out some useful properties regarding safety and security of the stored data.

We consider setting up

sleep scheduling

in sensor networks. We formulate the problem as an instance of the

fractional domatic partition problem

and obtain a distributed approximation algorithm by applying linear programming approximation techniques. Our algorithm is an application of the Garg-Könemann (GK) scheme that requires solving an instance of the minimum weight dominating set (MWDS) problem as a subroutine. Our two main contributions are a distributed implementation of the GK scheme for the sleep-scheduling problem and a novel asynchronous distributed algorithm for approximating MWDS based on a primal-dual analysis of Chvátal’s set-cover algorithm. We evaluate our algorithm with

ns2

simulations.

The emergence of large-scale distributed applications based on many-to-many communication models, e.g., broadcast and decentralized group communication, has an important impact on the underlying layers, notably the Internet routing infrastructure. To make an effective use of network resources, protocols should both limit the stress (amount of messages) on each infrastructure entity like routers and links, and balance as much as possible the load in the network. Most protocols use application-level metrics such as delays to improve efficiency of content dissemination or routing, but the extend to which such application-centric optimizations help reduce and balance the load imposed to the infrastructure is unclear. In this paper, we elaborate on the design of such

network-friendly

protocols and associated metrics. More specifically, we investigate random-based gossip dissemination. We propose and evaluate different ways of making this representative protocol network-friendly while keeping its desirable properties (robustness and low delays). Simulations of the proposed methods using synthetic and real network topologies convey and compare their abilities to reduce and balance the load while keeping good performance.

We study the Black Hole search problem using mobile agents in three interconnected network topologies: hypercube, torus and complete network. We do so without relying on local storage. Instead we use a less-demanding and less-expensive

token

mechanism. We demonstrate that the Black Hole can be located with a minimum of two (2)

co-located

agents performing Θ(

n

) moves with

O

(1) tokens, in each of these three topologies. Then we study the Black Hole search problem with

scattered

agents. We show that the optimal number of moves can be achieved with the optimal number of mobile agents using

O

(1) tokens.

This paper considers a system of autonomous mobile robots that can move freely in a two-dimensional plane, and where a number of them can fail by crashing. The crash of a robot can be either permanent or temporary, that is, after its crash the robot either executes no action or it recovers from its failure. These robots repeatedly go through a succession of activation cycles during which they observe the environment, compute a destination and move. In particular, we assume weak robots, in the sense that robots cannot communicate explicitly between each other. Also, they cannot remember their past computations (i.e., oblivious). Finally, robots do not agree on a common coordinate system.

In this paper, we address a fault-tolerant flocking problem under the crash-recovery model. That is, starting from any initial configuration, a group of non-faulty robots are required to form a desired pattern, and move together while following a robot leader on a given trajectory, and keeping such a pattern in movement. Specifically, we propose a fault-tolerant flocking algorithm in the semi-synchronous model that allows correct robots to dynamically form a regular polygon in finite time, and maintain it in movement infinitely often. Our algorithm relies on the existence of two devices, namely an eventually perfect failure detector oracle to ensure failure detection, and an eventual leader oracle to handle leader election. The algorithm tolerates permanent crash failures, and also crash recovery failures of robots due to its oblivious feature. The proposed algorithm ensures the necessary restrictions on the movement of robots in order to avoid collisions between them. In addition, it is self-stabilizing.

We present and evaluate a framework,

ParExC

, to reduce the runtime penalties of compiler generated runtime checks. An obvious approach is to use idle cores of modern multi-core CPUs to parallelize the runtime checks. This could be accomplished by (a) parallelizing the application and in this way, implicitly parallelizing the checks, or (b) by parallelizing the checks only. Parallelizing an application is rarely easy and frameworks that simplify the parallelization, e.g., like software transactional memory (STM), can introduce considerable overhead. ParExC is based on alternative (b). We compare it with an approach using a transactional memory-based alternative. Our experience shows that ParExC is not only more efficient than the STM-based solution but the manual effort for an application developer to integrate ParExC is lower. ParExC has – in contrast to similar frameworks – two noteworthy features that permit a more efficient parallelization of checks: (1) speculative variables, and (2) the ability to add checks by static instrumentation.

Efficiency of optimistic fair exchange using trusted devices is studied. Pfitzmann, Schunter and Waidner (

podc

1998) have shown that four messages in the main sub-protocol is optimal when exchanging idempotent items using non-trusted devices. It is straightforward that when using trusted devices for exchanging non-idempotent items this number can be reduced to three. This however comes at the cost of providing trusted devices with an unlimited amount of storage. We prove that exchanging non-idempotent items using trusted devices with a limited storage capacity requires exactly four messages in the main sub-protocol.

Host-based intrusion detection systems may be coarsely divided into two categories. Misuse-based intrusion detection systems, which rely on a database of malicious behavior; and anomaly-based intrusion detection systems which rely on the comparison of the observed behavior of the monitored application with a previously built model of its normal behavior called the reference profile. In this last approach, the reference profile is often built on the basis of the sequence of system calls the application emits during its normal executions. Unfortunately, this approach allows attackers to remain undetected by mimicing the attempted behavior of the application. Furthermore, such intrusion detection systems cannot by nature detect anything but violations of the integrity of the control flow of an application. Although, there exist quite critical attacks which do not disturb the control flow of an application and thus remain undetected. We thus propose a different approach relying on the idea that attacks often break simple constraints on the data manipulated by the program. In this perspective, we first propose to define which data are sensitive to intrusions. Then we intend to extract the constraints applying on these data items, afterwards controlling them to detect intrusions. We finally introduce an implementation of such an approach, and some encouraging results.

High-interaction honeypots are relevant to provide rich and useful information obtained from attackers. Honeypots come in different flavors with respect to their interaction potential. A honeypot can be very restrictive, but then only a few interactions can be observed. If a honeypot is very tolerant though, attackers can quickly achieve their goal. Having the best trade-off between attacker freedom and honeypot restrictions is challenging. In this paper, we address the issue of self adaptive honeypots, that can change their behavior and lure attackers into revealing as much information as possible about themselves. The key idea is to leverage game-theoretic concepts for the configuration and reciprocal actions of high-interaction honeypots.

The centralized management of large distributed systems is often impractical, particularly when the both the topology and status of the system change dynamically. This paper proposes an approach to application-centric self-management in large distributed systems consisting of a collection of autonomic components that join and leave the system dynamically. Cooperative autonomic components self-organize into a dynamically created overlay network. Through local information sharing with neighbors, each component gains access to global information as needed for optimizing performance of applications. The approach has been validated and evaluated by developing a decentralized autonomic system consisting of multiple autonomic application managers previously developed for the In-VIGO grid-computing system. Using analytical results from complex random network and measurements done in a prototype system, we demonstrate the robustness, self-organization and adaptability of our approach, both theoretically and experimentally.

We discuss the stabilization properties of networks that are composed of “displacement elements”. Each displacement element is defined by an integer

K

, called the displacement of the element, an input variable

x

, and an output variable

y

, where the values of

x

and

y

are non-negative integers. An execution step of this element assigns to

y

the maximum of 0 and

K

 + 

x

. The objective of our discussion is to demonstrate that two principles play an important role in ensuring that a network

N

is stabilizing, i.e. starting from any global state, network

N

is guaranteed to reach a global fixed point. The first principle, named consistent fixed points, states that if a variable is written by two subnetworks of

N

, then the values of this variable, when these two subnetworks reach fixed points, are equal. The second principle, named negative gain, states that the sum of displacements along every directed loop in network

N

is negative.

Awerbuch and Scheideler [2] have shown that peer-to-peer overlays networks can only survive Byzantine attacks if malicious nodes are not able to predict what will be the topology of the network for a given sequence of join and leave operations. A prerequisite for this condition to hold is to guarantee that nodes identifiers randomness is continuously preserved. However targeted join/leave attacks may quickly endanger the relevance of such an assumption. Inducing churn has been shown to be the other fundamental ingredient to preserve randomness. Several strategies based on these principles have been proposed. Most of them are based on locally induced churn. However either they have been proven incorrect or they involve a too high level of complexity to be practically acceptable [2]. The other ones, based on globally induced churn, enforce limited lifetime for each node in the system. However, these solutions keep the system in an unnecessary hyper-activity, and thus need to impose strict restrictions on nodes joining rate which clearly limit their applicability to open systems.

A self-stabilizing algorithm [2] is a distributed algorithm with an additional property: it guarantees to eventually execute its task, by reaching a

legitimate configuration

, regardless of the state in which the processes and communication links are started.

Some algorithms are supposed to remain safe at all times while they carry out their task. Safety, however, is impossible when very high levels of failures overwhelm the system, e.g., when more than a third of the processes are Byzantine, or in the extreme case, when all the processes disappear.

We propose a new

open addressing

hash function, the

unique-permutation hash function

, and a performance analysis of its hash computation. A hash function

h

is

simple uniform

if items are equally likely to be hashed to any table location (in the first trial). A hash function

h

is

random or strong uniform

if the probability of any permutation to be a probe sequence, when using

h

, is

${{1}\over{N!}}$

, where

N

is the size of the table. We show that the unique-permutation hash function is

strong uniform

and therefore has the lowest expected cost; each probe sequence is equally likely to be chosen, when the keys are uniformly chosen. Thus, the unique-permutation hash ensures that each empty table location has the same probability to be assigned with a uniformly chosen key.

For constant load factors

α

< 1, where

α

is the ratio between the number of inserted items and the table size, the expected time for computing the unique-permutation hash function is

O

(1) and the expected number of table locations that are checked before an empty location is found, during insertion (or search), is also

O

(1).

Self-stabilizing algorithms are designed to start from an arbitrary state and eventually exhibit a desired behavior. Self-stabilizing algorithms that use randomization are able to achieve tasks that cannot be achieved by deterministic means. In addition, in some cases, randomization enables faster convergence of self-stabilizing algorithms. Often, randomized self-stabilizing algorithms are designed to use an infinite amount of random bits to operate correctly. However, the creation of (real) random bits is considered expensive; thus, a

randomization adaptive

self-stabilizing algorithm which uses random bits during convergence but does not use random bits following the convergence is desirable. Such a notion of adaptiveness has been studied in the past, where the resource demands of a self-stabilizing algorithm are reduced upon convergence, be it memory requirements, or communication requirements.

This brief announcement proposes a new model to measure the distributed time complexity of topological self-stabilization. In the field of topological self-stabilization, nodes-e.g., machines in a p2p network—seek to establish a certain network structure in a robust manner (see, e.g., [2] for a distributed algorithm for skip graphs). While several complexity models have been proposed and analyzed over the last years, these models are often inappropriate to adequately model parallel efficiency: either they are overly pessimistic in the sense that they can force the algorithm to work serially, or they are too optimistic in the sense that contention issues are neglected. We hope that our approach will inspire researchers in the community to analyze other problems from this perspective. For a complete technical report about our model, related literature and algorithms, the reader is referred to [1].

By introducing context-awareness in the system layer, pervasive computing is a turning point in OS design. Device mobility and dynamicity of situations raise strong challenges for run-time adaptability of embedded software, while at the same time inducing new, serious threats to device security. Paradoxically, due to the multiplicity of protection requirements specific to each environment illustrated by the heterogeneity of network security policies, the solution may come from applying context-awareness to security itself. The idea is to tune security mechanisms to match the protection needs of the current device environment, such as the estimated level of risk. A manual adaptation is ruled out by the administration overhead and error potential of human intervention. To automate reconfiguration, security needs to be autonomic [2]. But how?

Security of cloud computing in the strict cryptographic sense is impossible to achieve practically. We propose a pragmatic security approach providing application-specific security under practical constraints.

The clustering problem consists of partitioning network nodes into groups called clusters. Each cluster has a single clusterhead that acts as local coordinator of cluster.

A technique for designing solutions that tolerate transient faults is selfstabilization. Self-stabilizing protocols are attractive because they need not be initialized: they converge from any configuration to a legitimate one. Also, they are adaptive to topological changes. If the current configuration is inconsistent with the network topology, the self-stabilizing protocol eventually converges to a legitimate configuration. Nevertheless, self-stabilizing protocols do not guarantee any property during the convergence period. In addition, the convergence time may be proportional to the size of the network; particularly, in weight-based clustering protocols. In order to overcome these drawbacks, we are interested to the robust stabilization. Robust stabilization guarantees that from an illegitimate configuration, the system reaches quickly a safe configuration, in which the safety property is satisfied. The safety property has to be defined such that the system performs correctly its task in a safe configuration. During the convergence to a legitimate configuration, the safety property stays always verified.

The problem of finding disjoint paths in a network is a fundamental problem with numerous applications. Two paths in a network are said to be (node) disjoint if they do not share any nodes except for the endpoints. The two node disjoint paths problem is to find two node-disjoint paths in

G

 = (

V

,

E

) from source

s

 ∈ 

V

to the target

t

 ∈ 

V

. The two-node-disjoint paths problem is a fundamental problem with several applications in diverse areas including VLSI layout, reliable network routing, secure message transmission, and network survivability. The two node disjoint path problem is fundamental, extensively studied in graph theory.

The designers of media access control (MAC) protocols often do not consider the relocation of mobile nodes. Alternatively, when they do assume that the nodes are not stationary, designers tend to assume that some nodes temporarily do not change their location and coordinate the communications among mobile nodes. An understanding is needed of the relationship between the performances of MAC algorithms and the different settings by which the location of the mobile nodes is modeled. We study this relationship with an emphasis on stabilization concepts, which are imperative in mobile ad hoc networks (MANETs). We show that efficient MAC algorithms must balance a trade-off between two strategies; one that is oblivious to the history of local broadcasts and one that is not.

We present a simple algorithm that implements the Omega failure detector in the crash-recovery model. The algorithm is quiescent, i.e., eventually all the processes but the leader stop sending messages. It assumes that processes have access to a nondecreasing local clock.

A distributed system consists of processes linked to one another by communication links. A classical problem is how to realistically model these links so that it is possible to write correct algorithms. This paper presents a new solution that results in more natural executions and removes the need for artificial workarounds.

Network file systems provide access to data in a networked environment. If such systems operate in a client-server (C/S) mode,

e

.

g

., NFS (Network File System) or SMB (Server Message Block), issues concerning the scalability, the presence of a single point of failure, and fault tolerance emerge. Scalability issues, such as coping with an increasing number of clients, need to be addressed, since bandwidth on the server side may be limited and expensive. Peer-to-peer (P2P) systems are, in contrast to C/S systems, fault-tolerant, robust, and scalable. Distributed file systems based on P2P networks can help to avoid such problems. Besides, P2P systems are self-organizing, requiring less management, thus reducing maintenance costs.