The binary similarity problem consists in determining if two functions are similar considering only their compiled form. Advanced techniques for binary similarity recently gained momentum as they can be applied in several fields, such as copyright disputes, malware analysis, vulnerability detection, etc. In this article we describe SAFE, a novel architecture for function representation based on a self-attentive neural network. SAFE works directly on disassembled binary functions, does not require manual feature extraction, is computationally more efficient than existing solutions, and is more general as it works on stripped binaries and on multiple architectures. Results from our experimental evaluation show how SAFE provides a performance improvement with respect to previous solutions. Furthermore, we show how SAFE can be used in widely different use cases, thus providing a general solution for several application scenarios.

Knowledge base (KB) sharing among parties has been proven to be beneficial in several scenarios. However such sharing can arise considerable privacy concerns depending on the sensitivity of the information stored in each party's KB. In this paper, we focus on the problem of exporting a (part of a) KB of a party towards a receiving one. We introduce a novel solution that enables parties to export data in a privacy-preserving fashion, based on a probabilistic data structure, namely the \emph{count-min sketch}. With this data structure, KBs can be exported in the form of key-value stores and inserted into a set of count-min sketches, where keys can be sensitive and values are counters. Count-min sketches can be tuned to achieve a given key collision probability, which enables a party to deny having certain keys in its own KB, and thus to preserve its privacy. We also introduce a metric, the γ-deniability (novel for count-min sketches), to measure the privacy level obtainable with a count-min sketch. Furthermore, since the value associated to a key can expose to linkage attacks, noise can be added to a count-min sketch to ensure controlled error on retrieved values. Key collisions and noise alter the values contained in the exported KB, and can affect negatively the accuracy of a computation performed on the exported KB. We explore the tradeoff between privacy preservation and computation accuracy by experimental evaluations in two scenarios related to malware detection.

In this paper we consider a static set of anonymous processes, i.e., they do not have distinguished IDs, that communicate with neighbors using a local broadcast primitive. The communication graph changes at each computational round with the restriction of being always connected, i.e., the network topology guarantees 1-interval connectivity. In such setting non trivial computations, i.e., answering to a predicate like "there exists at least one process with initial input a?", are impossible. In a recent work, it has been conjectured that the impossibility holds even if a distinguished leader process is available within the computation. In this paper we prove that the conjecture is false. We show this result by implementing a deterministic leader-based terminating counting algorithm. In order to build our counting algorithm we first develop a counting technique that is time optimal on a family of dynamic graphs where each process has a fixed distance h from the leader and such distance does not change along rounds. Using this technique we build an algorithm that counts in anonymous 1-interval connected networks.

In this paper we study the problem of counting processes in a synchronous dynamic network where a distinguished leader is available and other nodes share the same identifier. The network topology may change at each synchronous round and each node communicates with its neighbors by broadcasting messages. In such networks it is well known that counting requires Ω(D) rounds where D is the network diameter. We identify a non-trivial subset of dynamic net- works where counting requires Ω(log |V|) rounds even when the dynamic diameter, D, is constant with respect to the network size and the bandwidth is unlimited.

Many organizations today still manage mid or large in-house data centers that require very expensive maintenance efforts, including fault detection. Common monitoring frameworks used to quickly detect faults are complex to deploy/maintain, expensive, and intrusive as they require the installation of probes on monitored hw/sw to collect raw data. Such intrusiveness can be problematic as it imposes installation/management overhead and may interfere with security/privacy policies. In this paper we introduce NIRVANA, a novel monitoring system for fault detection that works at rack-level and is (i) non-intrusive, i.e., it does not require the installation of software probes on the hosts to be monitored and (ii) black-box, i.e., agnostic with respect to monitored applications. At the core of our solution lies the observation that aggregated features that can be monitored at rack-level in a non-intrusive and black-box way, show predictable behaviors while the system works in both fault-free and faulty states, it is therefore possible to detect and identify faults by monitoring and analyzing any perturbations to these behaviors. An extensive experimental evaluation shows that non-intrusiveness does not significantly hamper the fault detection capabilities of the monitoring system, thus validating our approach.

A distributed event notification service (ENS) is at the core of modern messaging infrastructures providing applications with scalable and robust publish/subscribe communication primitives. Such ENSs can route events toward subscribers using multiple paths with different lengths and latencies. As a consequence, subscribers can receive events out of order. In this paper, we propose a novel solution for ordered notifications on top of an existing distributed topic-based ENS. Our solutions guarantees that each pair of events published in the system will be notified in the same order to all their target subscribers independently from the topics they are published in. It endows a distributed timestamping mechanism based on a multistage sequencer that produces timestamps whose size is dynamically adjusted to accommodate changing subscriptions in the system. An extensive experimental evaluation based on a prototype implementation shows that the timestamping mechanism is able to scale from several points of view (i.e., number of publisher and subscribers, event rate). Furthermore, it shows how the deployment flexibility of our solution makes it perform better in terms of timestamp size and timestamp generation latency when the system load exhibits geographic topic popularity, that is, matching subscriptions and publications are geographically clustered. This makes our solution particularly well suited to be deployed in geo-distributed infrastructures.

In this paper we investigate the problem of counting the size of a network where processes are anonymous (i.e., they share the same identifier) and the network topology constantly changes controlled by an adversary able to look internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. It is easy to show that, if the adversary can generate graphs without any constraint on the connectivity (i.e. it can generate topologies where there exist nodes not able to influence the others), counting is impossible. In this paper we consider a synchronous round based computation and the dynamicity is governed by a worst-case adversary that generates a sequence of graphs, one for each round, with the only constraint that each graph must be connected (1-interval connectivity property). It has been conjectured that counting in a finite time against such adversary is impossible and the existing solutions consider that each process has some knowledge about network topologies generated by the adversary, i.e. at each round, each node has a degree lesser than D. Along the path of proving the validity (or not) of the conjecture, this paper presents an algorithm that counts in a finite time against the worst-case adversary assuming each process is equipped with an oracle. The latter provides a process at each round r with an estimation of the process degree in the graph generated by the adversary at round r. To the best of our knowledge, this is the first counting algorithm (terminating in a finite time) where processes exploit the minimal knowledge about the behavior of the adversary. Interestingly, such oracle can be implemented in a wide range of real systems.

Energy management, and in particular its efficient optimization, is one of the hot trends in the current days, both at the enterprise level (optimization of whole corporate/government buildings) and single-citizens' homes. Energy efficiency is generally function of out-door techniques -- renewable energy, smart energy production and distribution, etc. -- and in-door techniques; in particular, very few energy managers -- each of us can be an energy manager of his own home - can state "who, when and why is consuming", conversely this knowledge is fundamental in order to diminish wasting of energy. Recent studies show that the energy wasted in the overall consumption is about the 30% of the total amount; examples of potential energy wasting are printers and PCs on during the night, status LED of different devices (TV, set-top-box, etc.) and/or lights, lights during normal day-light time, etc.

A distributed event notification service (ENS) is a middleware architecture commonly used to provide applications with scalable and robust publish/subscribe communication primitives. A distributed ENS can route events toward subscribers using multiple paths with different lengths and latencies, as a consequence, subscribers can receive events out of order. In this paper, we propose a novel solution for out-of-order notification detection on top of an existing topic based ENS. Our solution guarantees that events published on different topics will be either delivered in the same order to all the subscribers of those topics or tagged as out-of-order. The proposed algorithm is completely distributed and is able to scale with the system size while imposing a reasonable cost in terms of notification latency. Our solution improves the current state of the art solutions by dynamically handling subscriptions/unsubscriptions and by automatically adapting with respect to topic popularity changes.

We propose an efficient software architecture for private collaborative event processing, enabling information sharing and processing among administratively and geographically disjoint organizations over the Internet. The architecture is capable of aggregating and correlating events coming from the organizations in near real-time, while preserving the privacy of sensitive data items even in the case of coalition of attackers. Although there is a rich literature in the field of secure multiparty computation techniques that preserve the privacy in a distributed systems, the ability of such systems to scale up horizontally (number of participants) and vertically (dataset per participant) is still limited. The key novelty of the architecture is the usage of a pseudo-random oracle functionality distributed among the organizations participating to the system for obfuscating the data, that allows for achieving a good level of privacy while guaranteing scalability in both dimensions. Some preliminary performance results are provided.

Due to their capability to hide the complexity generated by the messages exchanged between processes, shared objects are one of the main abstractions provided to developers of distributed applications. Implementations of such objects, in modern distributed systems, have to take into account the fact that almost all services, implemented on top of distributed infrastructures, are no longer fully managed due to either their size or their maintenance cost. Therefore, these infrastructures exhibit several autonomic behaviors in order to, for example, tolerate failures and continuous arrival and departure of nodes (churn phenomenon). Among all the shared objects, the register object is a fundamental one. Several protocols have been proposed to build fault resilient registers on top of message-passing system, but, unfortunately, failures are not the only challenge in modern distributed systems and new issues arise in the presence of churn. This paper addresses the construction of a multiwriter/multireader regular register in an eventually synchronous distributed system affected by the continuous arrival/departure of participants. In particular, a general protocol implementing a regular register is proposed and feasibility conditions associated with the arrival and departure of the processes are given. The protocol is proved correct under the assumption that a constraint on the churn is satisfied.

This paper studies the problem of building a byzantine fault tolerant storage service in a distributed system affected by servers join and leave (i.e., servers churn). We show a bound for ensuring both validity of read operations and the persistence of a value written by a write operation. This bound correlates the churn rate, the number of faulty processes and the time taken by register operations (i.e., join, read and write operations). © 2011 Authors.

Let consider a set of anonymous moving objects to be tracked in a binary sensor network. This article studies the problem of associating deterministically a track revealed by the sensor network with the trajectory of an unique anonymous object, namely the multiple object tracking and identification (MOTI) problem. In our model, the network is represented by a sparse connected graph where each vertex represents a binary sensor and there is an edge between two sensors if an object can pass from one sensed region to another one without activating any other sensor. The difficulty of MOTI lies in the fact that the trajectories of two or more objects can be so close that the corresponding tracks on the sensor network can no longer be distinguished (track merging), thus confusing the deterministic association between an object trajectory and a track. The article presents several results. We first show that MOTI cannot be solved on a general graph of ideal binary sensors even by an omniscient external observer if all the objects can freely move on the graph. Then we describe restrictions that can be imposed a priori either on the graph, on the object movements, or on both, to make the MOTI problem always solvable. In the absence of an omniscient observer, we show how our results can lead to the definition of distributed algorithms that are able to detect when the system is in a state where MOTI becomes unsolvable.

Telco providers are in the phase of migrating their services from PSTN to so called Next Generation Networks (NGNs) based on standard IP connectivity. This switch is expected to produce a cost degression of 50% for CAPEX, while OPEX remains fairly stable due to network management and energy costs. At the same time we are expecting a big increase of the load of a telco provider at the core level due to the istantiation of new telco services (VoIP, video conferencing etc) and to the support of third parties services (such as support to smartphone applications, etc.). The goal of this work is to show how management and energy costs can be effectively reduced by leveraging autonomic approaches to move some NGN services toward the telco network edge while still providing QoS levels comparable with those provided by a traditional fully-managed infrastructure.

Providing independent uniform samples from a system population poses considerable problems in highly dynamic settings, like P2P systems, where the number of participants and their unpredictable behavior (e.g., churn, crashes etc.) may introduce relevant bias. Current implementations of the Peer Sampling Service are designed to provide uniform samples only in static settings and do not consider that biased samples can directly affect the correctness of algorithms relying on a uniformity property or be exploited by a malicious adversary to increase the effectiveness of its attacks to the system. In this paper we provide a practical solution to the biasing problem by deploying a fully distributed Peer Sampling Correction Module on top of a given, possibly biased, peer sampling service. Samples provided by the peer sampling service will be locally processed by this module, using computationally efficient hashing functions, before getting to the application. The effectiveness of our approach is evaluated through an extensive simulation-based study.

Random walk (RW) is simple to implement and has a better termination control. The Markov chain analysis informs that RW eventually visits all vertices of a connected graph. Due to such nice properties, RW is often proposed for information dissemination or collection from all or part of a large scale unstructured network. The random walker, which can be used to disseminate or collect information, visits the nodes while selecting randomly one of the neighbors. The selection of neighbors is effected by the neighbor density or the connectivity degree of the nodes. The connectivity degree in turn depends on the radius of transmission of wireless nodes. In this paper we studied the coverage process of the RW on random geometric graph. The random geometric graphs are often considered as a model for wireless ad hoc and sensor networks. We defined and studied a metric called “attenuation” that indicates how fast a RW can move in the network while disseminating or collecting information. We showed that attenuation depends on the topology, the number of nodes in a network and the transmission radius of the nodes. We then studied the effect of attenuation on the RW coverage process analytically and through simulations and showed that attenuation is the normalized estimated search time of the network. In the end we applied the results obtained to show that the estimated search time in random geometric graphs is proportional to the reciprocal of the number of replicated targets.

Low-latency data delivery is an important requirement for achieving effective monitoring through wireless sensor networks. When sensor nodes employ duty cycling, sending a message along the shortest path, however, does not necessarily result in minimum delay. In this paper, we first study the lowest latency path problem, i.e., the characteristics of a path with minimum delay that connects a source node to the sink under random duty cycling nodes. Then, we propose a forwarding protocol based on biased random walks, where nodes only use local information about neighbors and their next active period to make forwarding decisions. We refer to this as lukewarm potato forwarding. Our analytical model and simulation experiments show that it is possible to reduce path latency without significantly increasing the number of transmissions (energy efficiency) needed to deliver the message to the destination. In particular, although deviating from the shortest path requires additional transmissions, and hence, higher energy consumption, this increase is compensated by a lighter duty cycle. Our experiments show that, overall, we can save up to 15 percent of energy while obtaining the same data delivery delay as shortest path routing. Additionally, the proposed solution is tunable. By changing the value of just one threshold parameter, it can be tuned to operate anywhere in the continuum from hot potato/random walk forwarding protocol to a deterministic shortest path forwarding protocol.

This paper studies the problem of realizing a common software clock among a large set of nodes without an external time reference (i.e., internal clock synchronization), any centralized control, and where nodes can join and leave the distributed system at their will. The paper proposes an internal clock synchronization algorithm which combines the gossip-based paradigm with a nature-inspired approach, coming from the coupled oscillators phenomenon, to cope with scale and churn. The algorithm works on the top of an overlay network and uses a uniform peer sampling service to fulfill each node's local view. Therefore, differently from clock synchronization protocols for small scale and static distributed systems, here, each node synchronizes regularly with only the neighbors in its local view and not with the whole system. An evaluation of the convergence speed and the synchronization error of the coupled-based internal clock synchronization algorithm has been carried out, showing how convergence time and the synchronization error depends on the coupling factor and the local view size. Moreover, the variation of the synchronization error with respect to churn and the impact of a sudden variation of the number of nodes have been analyzed to show the stability of the algorithm. In all these contexts, the algorithm shows nice performance and very good self-organizing properties. Finally, we showed how the assumption on the existence of a uniform peer-sampling service is instrumental for the good behavior of the algorithm and how, in system models where network delays are unbounded, a mean-based convergence function reaches a lower synchronization error than median-based convergence functions exploiting the number of averaged clock values.

Providing distributed processes with concurrent objects is a fundamental service that has to be offered by any distributed system. The classical shared read/write register is one of the most basic ones. Several protocols have been proposed that build an atomic register on top of an asynchronous message-passing system prone to process crashes. In the same spirit, this paper addresses the implementation of a regular register (a weakened form of an atomic register) in an asynchronous dynamic message-passing system. The aim is here to cope with the net effect of the adversaries that are asynchrony and dynamicity (the fact that processes can enter and leave the system). The paper focuses on the class of dynamic systems the churn rate c of which is constant. It presents two protocols, one applicable to synchronous dynamic message passing systems, the other one to eventually synchronous dynamic systems. Both protocols rely on an appropriate broadcast communication service (similar to a reliable broadcast). Each requires a specific constraint on the churn rate c. Both protocols are first presented in an as intuitive as possible way, and are then proved correct.

Consider a group of peers, an ideal random peer sampling service should return a peer, which is an unbiased independent random sample of the group. This paper focuses on peer sampling service based on view shuffling (aka gossip-based peer sampling), where each peer is equipped with a local view of size c. This view should correspond to a uniform random sample of size c of the whole system in order to implement correctly a uniform peer sampling service. To this aim, pairs of peers regularly and continuously swap a part of their local views (shuffling operation). The paper provides a proof that (i) starting from any non-uniform distribution of peers in the peers' local views, after a sequence of pairwise shuffle operations, each local view eventually represents a uniform sample of size c and (ii) once previous property holds, any successive sequence of shuffle operations does not modify this uniformity property. This paper also presents some numerical results concerning the speed of convergence to uniform samples of the local views.

Low latency data delivery is an important requirement for achieving effective monitoring through wireless sensor networks. When sensor nodes employ duty cycling, sending a message along the shortest path, however, does not necessarily result in minimum delay. In this paper we firstly study the lowest latency path problem, i.e., the characteristics of path with mini delay that connect a source node to the sink under random duty cycling nodes. Then, we propose a forwarding protocol based on biased random walks, where nodes only use local information about neighbors and their next active period to make forwarding decisions. We refer to this as lukewarm potato forwarding. Our analytical model and simulation experiments show that it is possible to reduce path latency without significantly increasing the number of transmissions (energy efficiency) needed to deliver the message to the destination. Additionally, the proposed solution is tunable. By changing the value of just one threshold parameter it can be tuned to operate anywhere in the continuum from hot potato/random walk forwarding protocol to a deterministic shortest path forwarding protocol.

Abstract Random walks can be conveniently exploited for implementing probabilistic algorithms to solve many searching problems arised by distributed applications, for example, service discovery, p2p file sharing, etc. In this paper we consider random walks executed on uniform wireless networks and study how to reduce the expected number of walk steps required to reach a target, namely the hitting time. The latter is the main search performance metric of a random walk based algorithm, since it determines the average response to a search as well as its cost; thus, the actual convenience of using random walks compared to other solutions depends on achieving a low hitting time. We show how in uniform wireless networks, the natural implementation of a random walk which selects the next node to visit at random among all neighbors is not a good choice, since it has a strong negative effect on the hitting time. This paper studies such a negative effect analytically and proposes two neighbor selection rules aiming at reducing the hitting time. A simulation study confirms the benefits of the proposed solutions. Copyright © 2008 John Wiley & Sons, Ltd.

This paper is about energy efficient and robust implementation of random walks in mobile wireless networks. While random walk based algorithm are often proposed to solve many problems in wireless networks, their implementation is usually done at the application layer so that many characteristics of the wireless transmissions are not exploited. In this paper we show that we can greatly reduce the energy requirements to perform a walk by better exploiting the broadcast nature of the transmissions. We propose a robust, energy efficient distributed next hop selection algorithm. To evaluate the algorithm we present a simulation study performed with ns-2. We found that in the proposed algorithm energy is reduced to more than 4 times and the selection delay is reduced to more than 8 times as compared to a standard next hop selection implementation.

This paper proposes an internal clock synchronization algorithm for very large number of processes that is able to (i) self-synchronize their local clocks without any central control and (ii) resist to attacks of an adversary whose aim is to put out-of-synchronization as many correct processes as possible. To cope with scale the algorithm utilizes the gossip-based paradigm where each process has a limited view of the system, while to resist to attacks the algorithm employs a filtering mechanism based on the notion of ¿-trimmed mean to filter out out-of-range clock values. The algorithm shows nice convergence in presence of networks errors and in absence of the adversary. When the adversary takes control of some of the processes in the system, we define two goals for the adversary, actually two predicates, to measure the strength of the attack. The first one captures the percentage of time in which at least one correct is out of synchronization and the second one when all correct processes are out of synchronization. The paper presents an extensive simulation study showing under which conditions (in terms of number of corrupted processes and size of local views) these two goals can be achieved by the adversary. Interestingly, these results can be exploited by applications that can tolerate either a certain time in which some correct process is non-synchronized or a certain percentage of correct processes that is non-synchronized.

This paper studies the existence and the regularity of Logarithmic Harary Graphs (LHGs). This study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in presence of link and node failures when considering an initial arbitrary number of nodes n. Therefore, the capability to identify graph constraints that allow the construction of LHGs for the largest number of pairs (n, k) (where k is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. The paper presents several results in that direction. We introduce a graph constraint, namely K-TREE, that allows the construction of a LHG for every pair (n, k) such that n ges 2k. Secondly we presents another graph constraint for LHG, namely KDIAMOND, which is equivalent to K-TREE in terms of capability to construct LHGs for any pair (n, k). The interest of K-DIAMOND lies in the fact that, for a given k, KDIAMOND allows to construct more regular graphs than K-TREE does. A k-regular graph shows the minimal number of links required by a k-connected graph, leading tominimal flooding cost. The paper formally shows, in particular, that there are an infinite number of pairs (n, k), such that there exists a k-regular LHG for the pair (n, k) that satisfies K-DIAMOND and does not satisfy K-TREE.

Overlay management protocols have been introduced to guarantee overlay network connectivity in dynamic large- scale peer-to-peer systems. Some of these protocols have been specifically designed to avoid the partitioning of the overlay in large clusters (network breakage) despite massive node failures and the continuous arrivals/departures of nodes (churn). In this paper we identify a second effect connected to churn, namely network erosion. We show how erosion affects overlay network connectivity and point out that even a strongly connected overlay network, when exposed to continuous churn, can be disgregated. More specifically the consequences of erosion are shown, through an experimental study, in the context of overlay management protocols based on the view-exchange technique. We finally propose a connection recovery mechanism to be endowed at each node which is able to collaboratively detect node isolation and the presence of small clusters. This mechanism is shown to be effective in reducing the erosion of an overlay network exposed to continuous churn and to quickly recover its connectivity during stability periods.

Nowadays, there are many protocols able to cope with process crashes, but, unfortunately, a process crash represents only a particular faulty behavior. Handling tougher failures (e.g. sending omission failures, receive omission failures, arbitrary failures) is a real practical challenge due to malicious attacks or unexpected software errors. This paper proposes a component-based methodology allowing to take a protocol A resilient to crash failures and to add software components, namely liveness and safety failure detectors, in order to adapt the protocol A to be resilient to more general failures than crashes, without changing the code of A. Then, the feasibility of this approach is shown, by providing an implementation of liveness failure detectors and of safety failure detectors for a protocol solving the problem of global data computation

We present a model of a mobile ad-hoc network in which nodes can move arbitrarily on the plane with some bounded speed. We show that without any assumption on some topological stability, it is impossible to solve the geocast problem despite connectivity and no matter how slowly the nodes move. Even if each node maintains a stable connection with each of its neighbours for some period of time, it is impossible to solve geocast if nodes move too fast. Additionally, we give a tradeoff lower bound which shows that the faster the nodes can move, the more costly it would be to solve the geocast problem. Finally, for the one-dimensional case of the mobile ad-hoc network, we provide an algorithm for geocasting and we prove its correctness given exact bounds on the speed of movement.

Recently many scalable and efficient solutions for event dissemination in publish/subscribe (pub/sub) systems have appeared in the literature. This dissemination is usually done over an overlay network of brokers and its cost can be measured as the number of messages sent over the overlay to allow the event to reach all intended subscribers. Efficient solutions to this problem are often obtained through smart dissemination algorithms that avoid flooding events on the overlay. In this paper, we propose a complementary approach that obtains efficient event dissemination by reorganizing the overlay network topology. More specifically, this reorganization is done through a self-organizing algorithm executed by brokers whose aim is to directly connect, through overlay links, pairs of brokers matching same events. In this way, on average, the number of brokers involved in an event dissemination decreases, thus reducing its cost. Even though the paradigm of the self-organizing algorithm is general and then applicable to any overlay-based pub/sub system, its concrete implementation depends on the specific system. As a consequence, we studied the effect of the introduction of the self-organizing algorithm in the context of a specific system implementing a tree-based routing strategy, namely SIENA, showing the actual performance benefits through an extensive simulation study. In particular, performance results point out the capacity of the algorithm to converge to an overlay topology accommodating efficient event with respect to (w.r.t) dissemination a specific scenario. Moreover, the algorithm shows a significant capacity to adapt the overlay network topology to continuously changing scenarios while keeping an efficient behavior w.r.t. event dissemination.

Communication-induced checkpointing protocols are mechanisms used to produce checkpoints and communication patterns which enjoy desirable properties, such as No-Z-Cycle (NZC). NZC guarantees that each checkpoint can be part of a global consistent checkpoint. It would be nice to define communication-induced checkpointing protocols that enforce NZC, adding a minimum number of checkpoints to remove all the Z-cycles from the distributed computation. In this paper, we prove that this is impossible by formulating the Minimum Z-Cycle Removal (MinZCR) problem and showing that there are no online competitive protocols for it. Moreover, we prove that the problem of enforcing NZC with an optimal number of checkpoints is difficult even if the whole input instance is known because its decision version is NP-complete. Finally, we also prove that MinZCR is difficult to approximate: it is APX-hard and this implies that no Polynomial Time Approximation Scheme exists for the problem.

A fundamental problem for both structured and unstructured peer-to-peer networks is how to maintain connected the topology of a network in the presence of processes that, possibly concurrently, join and leave the network. In this paper we firstly define a model of the computation well-suited to analyze connectivity maintenance among processes carrying out a distributed computation considering unbounded concurrency and infinite participation. Secondly upon this model we provide a specification of the connectivity maintenance problem. We finally present a protocol that guarantees connectivity maintenance by arranging processes of the computation on a tree. The protocol handles both joins and leaves concurrently and actively (i.e., some piece of code is executed by a leaving/joining process interacting with its neighbors in the topology).

In the context of clients accessing a read/write shared object, persistency of a written value is a property stating that a value written into the object is always available unless overwritten by a successive write operation. This property can be easily guaranteed in a static distributed system provided that either a subset of processes implementing the object does not crash or processes can crash and then recover being able to retrieve their last state. Unfortunately the enforcing of this property in a potentially large scale and dynamic distributed system (e.g. a P2P system) is far from being trivial when considering the case in which processes implementing the object may fail or leave at any time without notifying any other process (i.e., the last state might not be retrievable). The paper introduces the notion of weak persistency that guarantees persistency of values when a system becomes quiescent (arrivals and departures subside). An implementation of a weakly-persistent object ensuring causal consistency is provided along with its correctness proof. The interest of causal consistency lies in the fact that, contrarily to atomic consistency, it can be maintained even during non-quiescent periods of the distributed system (i.e., when persistency is not guaranteed)

Keeping strongly consistent the state of the replicas of a software service deployed across a distributed system prone to crashes and with highly unstable message transfer delays (e.g., the Internet), is a real practical challenge. The solution to this problem is subject to the FLP impossibility result, and thus there is a need for "long enough" periods of synchrony with time bounds on process speeds and message transfer delays to ensure deterministic termination of any run of agreement protocols executed by replicas. This behavior can be abstracted by a partially synchronous computational model. In this setting, before reaching a period of synchrony, the underlying network can arbitrarily delay messages and these delays can be perceived as false failures by some timeout-based failure detection mechanism leading to unexpected service unavailability. This paper proposes a fully distributed solution for active software replication based on a three-tier software architecture well-suited to such a difficult setting. The formal correctness of the solution is proved by assuming the middle-tier runs in a partially synchronous distributed system. This architecture separates the ordering of the requests coming from clients, executed by the middle-tier, from their actual execution, done by replicas, i.e., the end-tier. In this way, clients can show up in any part of the distributed system and replica placement is simplified, since only the middle-tier has to be deployed on a well-behaving part of the distributed system that frequently respects synchrony bounds. This deployment permits a rapid timeout tuning reducing thus unexpected service unavailability.

This paper introduces a novel architecture for implementing content-based pub/sub communications on top of structured overlay networks. This architecture overcomes some well-known limitations of existing infrastructures, i.e. lack of self-configuration and of adaptiveness to dynamic changes. This is achieved by devising a mediator stratum between the rich event subscription semantics of content-based pub/sub systems and the standard logical addressing scheme of overlays. The paper describes details of the design and provides considerations in selecting the subscription-to-node and event-to-node mappings suitable for the solution. We identify the lack of native support for one-to-many communication by overlay networks as the main impediment for efficient system operation. The paper introduces a novel primitive for one-to-many message delivery, showing through simulation how this can improve performance of the architecture. The simulation study also shows performance comparison between the different mappings proposed as well as evaluation of other optimizations discussed in the paper

Peer-to-peer systems (P2P) have become a popular technique to architect decentralized systems. However, despite its popularity most P2P systems consist in simple applications such as file sharing or chat systems. The main reason is that more complex applications require levels of consistency that nowadays are not offered by P2P systems. In this paper, we explore how to provide consistency based on distributed mutual exclusion via quorum systems in DHT-based P2P networks. Our results show that quorum systems applied directly to such networks are not scalable due to the high traffic imposed onto the underlying network. The paper introduces some design principles for both quorum systems and protocols using them that help to boost their performance. These design principles consist in dynamic and decentralized selection of quorums and in the exposition and exploitation of internals of the DHT such as the finger table. We show that by combining both design principles it is possible to minimize the number of visited sites and the latency needed to obtain a quorum

Abstract This paper presents a formal framework of a distributed computation based on a publish/subscribe system. The framework abstracts the system through two delays, namely the subscription/unsubscription delay and the diffusion delay. This abstraction allows one to model concurrent execution of publication and subscription operations without waiting for the stability of the system state and to define a Liveness property which gives the conditions for the presence of a notification event in the global history of the system. This formal framework allows us to analytically define a measure of the effectiveness of a publish/subscribe system, which reflects the percentage of notifications guaranteed by the system to subscribers. A simulation study confirms the validity of the analytical measurements. Copyright © 2005 John Wiley & Sons, Ltd.

Summary form only given. Distributed shared memory (DSM) is one of the main abstraction to implement data-centric information exchanges among a set of processes. Ensuring causal consistency means all operations executed at each process will be compliant to a cause effect relation. We provide an optimality criterion for a protocol P that enforces causal consistency on a DSM. This criterion addresses the number of write operations delayed by P (write delay optimality). Then we present a protocol which is optimal with respect to write delay optimality and we show how previous protocols presented in the literature are not optimal with respect to such a criterion.

A publish/subscribe communication system (PSS) realizes a many-to-many anonymous interaction among its participants. Producers of information (publishers) issue notifications to the PSS. These are delivered by the PSS to all subscribers that declared interest in it. However, this decoupled form of interaction introduces delays between i) the production of a notification and its delivery to subscribers (diffusion delay) and ii) the declaration of interest by a subscriber and its registration in the PSS (subscription/unsubscription delay). Such delays could lead to notification loss scenarios where an event is not delivered to an intended subscriber even though it was issued when the subscription was active. We studied this notification loss phenomenon by presenting a simulation study of a PSS and an analytical model. The latter measures the percentage of notifications guaranteed by a PSS implementation to a subscriber. This addresses a QoS issue. The model is based on a formal framework of a distributed computation. The framework abstracts the PSS through the two delays, defining safety and liveness properties that precisely characterize the semantics of the PSS.

Abstract Interceptors are an emerging middleware technology enabling the addition of specific network‐oriented capabilities to distributed applications. By exploiting interceptors, developers can register code within interception points, extending the basic middleware mechanisms with specific functionality, e.g. authentication, flow control, caching, etc. Notably, these extensions can be achievedwithout modifyingeither the application or the middleware code. In this paper we report the results of our experiences with CORBA request portable interceptors. In particular, we point out (i) the basic mechanisms implementable by these interceptors, i.e. request redirection and piggybacking and (ii) we analyze their limitations. We then propose a proxy‐based technique to overcome the interceptors' limitations. Successively, we present a performance analysis carried out on three Java‐CORBA platforms currently implementing the portable interceptors specification. Finally, we conclude our work with a case study in which portable interceptors are used to implement the fault‐tolerant CORBA client invocation semantic without impacting on the client application code and on the CORBA ORB. We also release fragments of Java code for implementing the described techniques. Copyright © 2003 John Wiley & Sons, Ltd.

Abstract Enforcing strong replica consistency among a set of replicas of a service deployed across anasynchronousdistributed system in the presence of crash failures is a real practical challenge. If each replica runs the consistency protocol bundled with the actual service implementation, this target cannot be achieved, as replicas need to be located over apartially synchronous distributed systemto solve the distributed agreement problems underlying strong replica consistency. A three‐tier architecture for software replication enables the separation of the replication logic, i.e. protocols and mechanisms necessary for managing software replication, from both clients and server replicas. The replication logic is embedded in a middle‐tier that confines the need of partial synchrony and thus frees replica deployment. In this paper we first introduce the basic concepts underlying three‐tier replication. Then we present the interoperable replication logic (IRL) architecture, a fault‐tolerant CORBA compliant infrastructure. IRL exploits a three‐tier approach to replicate stateful deterministic CORBA objects and allows object replicas to run on object request brokers from different vendors. A description of an IRL prototype developed in our department is proposed along with an extensive performance analysis. Copyright © 2003 John Wiley & Sons, Ltd.

A large class of routing protocols for MANETs, namely, reactive protocols employ some form of caching to reduce the number of route discoveries. The simplest form of caching is based on associating a timeout with each cache entry. Such timer-based cache schemes can increase the protocol efficiency. However, if the timeout is not well-tuned, a severe performance degradation arises as entries are removed either too early or too late from the cache. We address the problem of designing a proactive cache scheme that does not rely on any timer-based mechanism. This scheme guarantees that valid cached routes are never removed while stale routes are removed aggressively. This proactive cache scheme has been embedded in the Zone Routing Protocol (ZRP) framework and evaluated by an extensive simulation study.

Vector clocks are the appropriate mechanism used to track causality among the events produced by a distributed computation. Traditional implementations of vector clocks require application messages to piggyback a vector of n integers (where n is the number of processes). This paper investigates the tracking of the causality relation on a subset of events (namely, the events that are defined as "relevant" from the application point of view) in a context where communication channels are not required to be FIFO, and where there is no a priori information on the connectivity of the communication graph or the communication pattern. More specifically, the paper proposes a suite of simple and efficient implementations of vector clocks that address the reduction of the size of message timestamps, i.e., they do their best to have message timestamps whose size is less than n. The relevance of such a suite of protocols is twofold. From a practical side, it constitutes the core of an adaptive timestamping software layer that can used by underlying applications. From a theoretical side, it provides a comprehensive view that helps better understand distributed causality-tracking mechanisms.

A distributed mutual exclusion algorithm based on token exchange and well suited for mobile ad-hoc networks is presented along with a simulation study. The algorithm is based on a dynamic logical ring and combines the best from two families of token based algorithms (i.e., token-asking and circulating token). In this way, the number of messages exchanged per critical section (CS) access (the main performance index for such algorithms) tends to optimal values under a heavy request load (i.e., two application messages for each CS access). We present a simulation study that (i) confirms this optimality and (ii) shows that, in a mobile ad-hoc network, an effective reduction in the number of hops per application message can be achieved by using a specific policy to build the logical ring on-the-fly.

The deployment of server replicas of a service across an asynchronous distributed system (e.g., Internet) is a real practical challenge. This target cannot be indeed achieved by classical software replication techniques (e.g., passive and active replication) as these techniques usually rely on group communication toolkits that require server replicas to run over a partially synchronous distributed system to solve the underlying agreement problem. This paper proposes a three-tier architecture for software replication that encapsulates the need of partial synchrony in a specific software component of a mid-tier to free replicas and clients from the need of underlying partial synchrony assumptions. Then we propose how to specialize the mid-tier in order to manage active replication of server replicas.

A replication logic is the set of protocols and mechanisms implementing a software replication technique. A three-tier approach to replication consists in separating the replication logic from both clients and replicated servers by embedding such logic in a middle-tier In this paper we first introduce the fundamental concepts underlying three-tier replication. This approach has two main practical advantages: (i) it allows to maintain consistency among the state of server replicas deployed within an asynchronous distributed system and (ii) it supports very thin clients. Then we present the Interoperable Replication Logic (IRL) architecture, which is a Fault Tolerant CORBA compliant infrastructure exploiting a three-tier approach to replicate stateful deterministic CORBA objects. In this context, we illustrate the three-tier replication protocol currently implemented in our IRL prototype and a performance analysis that shows the feasibility of the three-tier approach to software replication.

Integrating autonomous enterprise systems allows the cooperation among applications belonging to distinct systems. As an example, this problem shows up when integrating software services of large departments and organizations in e-government initiatives. This paper studies, in the context of the Unitary Network of the Italian Public Administration, the problem of increasing the availability of services exported by an autonomous enterprise system towards others. In particular we show how a fault tolerant CORBA system, namely the Interoperable Replication Logic (IRL), can be used to increase such an availability by building a replicated cooperative gateway that wraps enterprise applications.

Even though introduced for solving the consensus problem in asynchronous distributed systems, the notion of unreliable failure detector can be used as a powerful tool for any distributed protocol in order to get better performance by allowing the usage of aggressive time-outs to detect failures of entities executing the protocol. We present the design of a Failure Detection Service (FDS) based on the notion of unreliable failure detectors introduced by T. Chandra and S. Toueg (1996). FDS is able to detect crashed objects and entities that permanently omit to send messages without imposing changes to the source code of the underlying protocols that use this service. Also, FDS provides an object oriented interface to its subscribers and, more important, it does not add network overhead if no entity subscribes to the service. The paper can be also seen as a first step towards a distributed implementation of a heartbeat-based failure management system as defined in fault-tolerant CORBA specification.

Whether it is for audit or for recovery purposes, data checkpointing is an important problem of transaction systems. Actually, transactions establish dependence relations on data checkpoints taken by data object managers. So, given an arbitrary set of data checkpoints (including at least a single data checkpoint from a data manager, and at most a data checkpoint from each data manager), an important question is the following one: ‘Can these data checkpoints be members of a same consistent global checkpoint?’ This paper answers this question by providing a necessary and sufficient condition suited to transaction systems. Moreover, to show its usefulness, two non-intrusive data checkpointing protocols are designed from this condition.

Presents a generic methodology to transform a protocol which is resilient to process crashes into one that is resilient to arbitrary failures in the case where processes run the same text and regularly exchange messages (i.e. the case of round-based protocols). The methodology follows a modular approach, encapsulating the detection of arbitrary failures in specific modules. This can be the starting point for designing tools that allow automatic transformation. We show an application of this methodology to the case of consensus.

A causal ordering protocol ensures that if two messages are causally related and have the same destination, they are delivered to the application in their sending order. Causal order strongly simplifies the development of distributed object oriented systems. To prevent causal order violation, either messages may be forced to wait for messages in their past, or late messages may have to be discarded. For a real time setting, the first approach is not suitable since when a message misses a deadline, all the messages that causally depend on it may also be forced to miss their deadlines. We propose a novel causal ordering abstraction that takes message deadlines into consideration. Two implementations are proposed in the context of multicast and broadcast communication that deliver as many messages as possible to the application. Examples of distributed soft real time applications that benefit from the use of a deadline-constrained causal ordering primitive are given.

We investigate issues related to building highly available World Wide Web (WWW) servers on workstation clusters. We present a novel architecture that includes a dynamic Domain Name System (DNS) and a WWW server based on passive object replication. This architecture allows us to reduce the service down-time of a WWW server without impacting on the Hyper Text Transfer Protocol (HTTP) protocol (and thus on the WWW client software). We implement this architecture in our department and we show some experimental results that analyze, given a batch of HTTP requests, the average response time to a request and the average time of WWW service unavailability due to object crashes.

When we consider an asynchronous distributed computation on which local checkpoints have been defined (namely, a communication and checkpoint pattern -in brief, CCP), two types of dependencies between its local checkpoints can be observed.The first type is due to causal sequences of messages that establish on-line trackable dependencies.The second type is due to noncausal sequences of messages (called Z-paths) that establish "hidden" dependencies between local checkpoints (a dependency is "hidden" if it can not be tracked online).The Rollback Dependency Trackability (RDT) property, defined by Y.-M.Wang, has been introduced to study CCPs.A CCP satisfies the RDT property if every pair of local checkpoints that are connected by a "hidden" dependency are also connected by a causal sequence of messages.The RDT property has a great interest: CCPs that satisfy this property allow relatively simple solutions to a lot of practical problems.This paper first introduces the notion of RDT-compliant property.In a given CCP, an X-path is a Z-path that satisfies a property X.The property X is RDT-compliant if every CCP without X-paths satisfies the RDT property.Then, the paper presents a particular RDT-compliant property.This property enjoys several very interesting features.(1) It is "visible" (i.e., it can be tested on-line).(2) It is stronger than previously known RDT-compliant properties.Consequently, this property provides a characterization of RDT better than the previous ones.The question of the minimal characterization of the RDT property is finally investigated.1 Introduction Long running scientific applications and service providing facilities use rollback-recovery techniques to increase their fault tolerance and their availability.This is done by saving onto stable storage the state of processes (i.e., Permission to make digital or hard copies of all or part ofthis work for personal or c~assroon~ use is granted without fee provided that copies arc not made or distrihutcd for protit or commercial advantage and that copies bear this notice and the full citation 011 the first page.'I'0 copy other&c.to republish, to post on servers or to redistribute to lists.

This paper presents an index-based checkpointing algorithm for distributed systems with the aim of reducing the total number of checkpoints while ensuring that each checkpoint belongs to at least one consistent global checkpoint (or recovery line). The algorithm is based on an equivalence relation defined between pairs of successive checkpoints of a process which allows us, in some cases, to advance the recovery line of the computation without forcing checkpoints in other processes. The algorithm is well-suited for autonomous and heterogeneous environments, where each process does not know any private information about other processes and private information of the same type of distinct processes is not related (e.g., clock granularity, local checkpointing strategy, etc.). We also present a simulation study which compares the checkpointing-recovery overhead of this algorithm to the ones of previous solutions.

A useless checkpoint corresponds to the occurrence of a checkpoint and communication pattern called Z-cycle. A recent result shows that ensuring a computation without Z-cycles is a particular application of a property, namely Virtual Precedence (VP), defined on an interval-based abstraction of a computation. We first propose a taxonomy of communication-induced checkpointing protocols based on the way they ensure the VP property. Then we derive a sufficient condition ensuring no Z-cycles in a distributed computation. This condition defines a checkpoint and communication pattern, namely suspect Z-cycle, such that if no suspect Z-cycle exists in a distributed computation then no Z-cycle exists. We present finally a communication-induced checkpointing protocol that avoids useless checkpoints by preventing on-the-fly the formation of suspect Z-cycles and discuss its performance with respect to other protocols.

In mobile computing systems the network configuration changes due to node mobility. The paper identifies the issues a group communication service has to take into account in order to handle node mobility. These include the need to identify the location of a node, and the ability to cope with inaccuracies in the determination of a group membership. A multi level architecture for group communication in mobile systems is presented. This architecture contains a synchronous proximity layer protocol to determine the set of mobile nodes in the proximity of a given node in the network. This information is used by a three round group membership protocol for construction of groups used by mobile applications. As an example, the architecture is specialized to solve the channel allocation problem.

Communication protocols designed for database applications are not necessarily suitable for other applications, like multimedia communication, due to the former's requirement of reliable and ordered communication, and the latter's ability to withstand occasional losses and misordering of messages as long as real-time communication can be supported. This paper presents the slotted-FIFO communication mode that supports communication primitives for the entire spectrum of reliability and ordering requirements of distributed applications: for example, FIFO as well as non-FIFO, and reliable as well as unreliable communication. It provides communication with a run-time variable degree of reliability and/or ordering. Hence, the slotted-FIFO communication mode is suitable for applications that can work with relaxed reliability and/or ordering constraints such as multimedia applications. The protocol is simple and has low overheads. As FIFO ordering is not required for all messages, message buffering requirements are considerably reduced. Also, message latencies are lower. We demonstrate such advantages by means of a simulation study. A low overhead protocol implementing slotted-FIFO communication is also presented. The protocol incurs a small resequencing cost.

Causal broadcasting has been introduced to reduce the asynchrony of communication channels inside groups of processes. It states that if two broadcast messages are causally related by the happened-before relation, these messages are delivered in their sending order to each process of the group. Even though protocols implementing causal broadcasting do not add control messages, they suffer from the typical pitfall of the timestamping technique: To ensure causal ordering, application messages have to piggyback a vector time of counters whose range of variation is unbounded. In this paper, we investigate such a range and define the concept of causal window of a process in which all counters of a vector time of a just arrived message at that process fall. We prove that, by using a causal broadcasting (one-to-all) protocol that follows a positive acknowledgment method, the width of the causal window of each process is limited. This allows a modulo k implementation of vector times when considering k greater than the width of the causal window of each process. The protocol is applicable to data link or transport layers using acknowledge messages to ensure reliable transfer of data. The paper also proposes two variants of the protocol based on causal windows. Both of them increase the concurrency of the protocol at the expense of wider causal windows.

This paper presents the slotted-FIFO communication mode that supports communication primitives for the entire spectrum of reliability and ordering requirements of distributed applications: FIFO as well as non-FIFO, and reliable as well as unreliable communication. Hence, the slotted-FIFO communication mode is suitable for multimedia applications, as well as non real-time distributed applications. As FIFO ordering is not required for all messages, message buffering requirements are considerably reduced. Also, message latencies are lower. We quantify such advantages by means of a simulation study. A low overhead protocol implementing slotted-FIFO communication is also presented. The protocol incurs a small resequencing cost.

We propose the hierarchical daisy architecture, which provides causal delivery of messages sent to any subset of processes. The architecture provides fault tolerance and maintains the amount of control information within a reasonable size. It divides processes into logical groups. Messages inside a logical group are sent directly, while messages that need to cross logical group boundaries are forwarded by servers. We prove the correctness of the daisy architecture and discuss possible optimizations.

The paper presents an index based checkpointing algorithm for distributed systems with the aim of reducing the total number of checkpoints while ensuring that each checkpoint belongs to at least one consistent global checkpoint (or recovery line). The algorithm is based on an equivalence relation defined between pairs of successive checkpoints of a process which allows, in some cases, to advance the recovery line of the computation without forcing check points in other processes. This protocol shows good performance, especially in autonomous environments, where each process does not have any private information about other processes.

No abstract available.

No abstract available.

Multimedia real-time collaborative applications or groupware real-time applications require participants to exchange real-time audio and video information over a communication network. This flow of information must preserve the causal dependency even though part of the information can be lost or can be discarded if it violates the tinting constraints imposed by a real-time interaction. In this paper we propose a communication abstraction to cope with unreliable communication networks with real-time delivery constraints: messages have a lifetime, /spl Delta/, after which their contents can no longer be used, moreover some of them can be lost. This new abstraction, called /spl Delta/-causal order, requires to deliver as much messages as possible within their lifetime in such a way that these deliveries respect causal order. An efficient protocol is proposed in the case of one-to-one communications. A variation of this protocol weld suited to broadcast communications is also shown.

This paper presents a permission-based algorithm to solve the problem of M identical resources shared among N processes in a distributed system. We prove that the number of messages exchanged necessary for a process to acquire k resources is O(N/sup M/(M+1)/). This result has been obtained (i) investigating the concept of arbiter of conflicting processes and (ii) extending conditions that permit conflict detection and resolution in a system of N competing processes to M shared resources. We show that for M=1 we get Maekawa's algorithm. However, we will also show that Maekawa's results, being based on finite projective plane geometry, do not apply for M>1.>