This paper presents the first non-interactive, succinct, and secure representation of a PoW-based blockchain that operates under variable mining difficulty while satisfying both completeness and onlineness properties. Completeness ensures that provers can update an existing NIPoPoW by incorporating a newly mined block, whereas onlineness ensures that miners can extend the chain directly from a NIPoPoW. The time complexity for both the prover (to update a NIPoPoW with a new block) and the verifier is logarithmic in the number of blocks of the underlying PoW blockchain. The communication complexity required for synchronization is polylogarithmic in the length of the blockchain. We prove the correctness of our scheme in the presence of a 1/3-bounded PPT adversary.

The long-term feasibility of blockchain technology is hindered by the inability of existing blockchain protocols to prune the consensus data leading to constantly growing storage and communication requirements. Kiayias et al. have proposed Non-Interactive-Proofs-of-Proof-of-Works (NIPoPoWs) as a mecha-nism to reduce the storage and communication complexity of blockchains to O(poly log(n)). However, their protocol is only resilient to an adversary that may control strictly less than a third of the total computational power, which is a reduction from the security guaranteed by Bitcoin and other existing Proof-of-based blockchains. We present an improvement to the Kiayias et al. proposal, which is resilient against an adversary that may control less than half of the total computational power while operating in$o$(polylog$(n)$) storage and communication complexity. Additionally, we present a novel proof that establishes a lower bound of$O(\log(n))$on the storage and communication complexity of any PoW-based blockchain protocol.

In this paper, we analyze a new asynchronous rumor spreading protocol to deliver a rumor to all the nodes of a large-scale distributed network. This protocol relies on successive pull operations involving$k$different nodes, with$k=2$or$k=3$, and called$k$-pull operations. Specifically during a k-pull operation, an uninformed node$a$contacts$k-1$other nodes at random in the network, and if at least one of them knows the rumor, then node$a$learns it. We perform a detailed study in continuous-time of$\Theta_{k, n}$, the total time needed for all the$n$nodes to learn the rumor. We obtain, for$k\in\{2,3\}$, the mean value, the variance and the distribution of$\Theta_{k, n}$together with their asymptotic behavior when the number of nodes$n$tends to infinity.

This paper proposes and analyses the performance and the vulnerability to attacks of three algorithms for collecting longitudinal data in a large scale system. A monitoring device is in charge of continuously collecting measurements from end-devices. The communication graph is connected but not necessar-ily complete. For scalability reasons, at each collect, a single end-device is randomly selected among all the end -devices to send the content of its local buffer of data to the monitoring device. Once sent, the end-device resets its buffer, and resumes its measurement process. Two of the three algorithms are randomized algorithms while the third one is deterministic. We study the transient and stationary maximum load distribution at end-devices when collects are made using the first and third algorithm, and by providing bounds via a coupling argument when the second algorithm is used. While the third algorithm provides the best performance, it is highly vulnerable to attacks.

In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. [1], a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element e of a certain join-semi lattice L and it has to decide on a value that contains e. Moreover, any pair pi, pjof correct processes has to decide two values deciand decjthat are comparable (e.g., deci≤ decjor decji). In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of n processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if f = n/3 or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the authenticated message model), tolerates up to f byzantine failures (where f <; n/3) and that terminates in O(log f) rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency (f <; n/4). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.

The paper investigates the Lattice Agreement (LA) problem in asynchronous systems. In LA each process proposes an element e from a predetermined lattice, and has to decide on an element e' of the lattice such that e ≤ e'. Moreover, decisions of different processes have to be comparable (no two processes can decide two elements e' and e such that (e ≤ e') ∧ (e' ≤ e)).It has been shown that Generalized LA (i.e., a version of LA proposing and deciding on sequences of values) can be used to build a Replicated State Machine (RSM) with commutative update operations. The key advantage of LA and Generalized LA is that they can be solved in asynchronous systems prone to crash-failures (which is not the case with standard Consensus).In this paper we assume Byzantine failures. We propose the Wait Till Safe (WTS) algorithm for LA, and we show that its resilience to f ≤ (n - 1)/3 Byzantine processes is optimal. We then generalize WTS obtaining a Generalized LA algorithm, namely GWTS. We use GWTS to build a RSM with commutative updates. Our RSM works in asynchronous systems and tolerates f ≤ (n - 1)/3 malicious entities. All our algorithms use the minimal assumption of authenticated channels. When the more powerful public signatures are available, we discuss how to improve the message complexity of our results (from quadratic to linear, when f = O(1)). To the best of our knowledge this is the first paper proposing a solution for Byzantine LA that works on any possible lattice, and it is the first work proposing a Byzantine tolerant RSM built on it.

We propose a consensus algorithm whose objective is to decide on the same union of proposed values, such that with high probability all the values proposed by the honest nodes belong to the decision. Our algorithm has been designed to cope with an asynchronous and permissionless system. By relying on a proof-of-eligibility, our algorithm is tolerant to an adversary capable of instantaneously corrupting entities. A straightforward application of our algorithm is the design of permissionless distributed ledgers.

The context of this work is the well-studied dissemination of information in large-scale distributed networks through pairwise interactions. This problem, originally called rumor mongering, and then rumor spreading, has mainly been investigated in the synchronous model. This model relies on the assumption that all the nodes of the network act in synchrony; that is, at each round of the protocol, each node is allowed to contact a random neighbor. In this paper, we drop this assumption under the argument that it is not realistic in large-scale systems. We, thus, consider the asynchronous variant, with which, at random times, nodes successively interact by pairs, exchanging their information on the rumor. In a previous paper, we performed a study of the total number of interactions needed for all the nodes of the network to discover the rumor. Although most of the existing results involve huge constants that do not allow us to compare different protocols, we provided a thorough analysis of the distribution of this total number of interactions together with its asymptotic behavior. In this paper, we extend this discrete-time analysis by solving a conjecture proposed previously, and we consider the continuous-time case, in which a Poisson process is associated to each node to determine the instants at which interactions occur. The rumor-spreading time is, thus, more realistic because it is the real time needed for all the nodes of the network to discover the rumor. Once again, as most of the existing results involve huge constants, we provide tight bound and equivalent of the complementary distribution of the rumor-spreading time. We also give the exact asymptotic behavior of the complementary distribution of the rumor-spreading time around its expected value when the number of nodes tends to infinity.

This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.

The presented work continues the line of recent distributed computing community efforts dedicated to the theoretical aspects of blockchains. This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. Our work is based on an original oracle-based construction that, along with new consistency definitions, captures the eventual convergence process in blockchain systems. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.

This paper presents a new algorithm that detects on the fly the k most frequent items in the sliding window model. This algorithm is distributed among the nodes of the system. It is inspired by a recent and innovative approach, which consists in associating a stochastic value correlated with the item's frequency instead of trying to estimate its number of occurrences. This stochastic value corresponds to the number of consecutive heads in coin flipping until the first tail occurs. The original approach was to retain just the maximum of consecutive heads obtained by an item, since an item that often occurs will have a higher probability of having a high value. While effective for very skewed data distributions, the correlation is not tight enough to robustly distinguish items with comparable frequencies. To address this important issue, we propose to combine the stochastic approach together with a deterministic counting of items. Specifically, in place of keeping the maximum number of consecutive heads obtained by an item, we count the number of times the coin flipping process of an item has exceeded a given threshold. This threshold is defined by combining theoretical results in leader election and coupon collector problems. Results on simulated data show how impressive is the detection of the top-k items in a large range of distributions.

We propose a new way to organise both transactions and blocks in a distributed ledger to address the performance issues of permissionless ledgers. In contrast to most of the existing solutions in which the ledger is a chain of blocks extracted from a tree or a graph of chains, we present a distributed ledger whose structure is a balanced directed acyclic graph of blocks. We call this specific graph a SYC-DAG. We show that a SYC-DAG allows us to keep all the remarkable properties of the Bitcoin blockchain in terms of security, immutability, and transparency, while enjoying higher throughput and self-adaptivity to transactions demand. To the best of our knowledge, such a design has never been proposed so far.

This paper focuses on pairwise interaction-based protocols, and proposes an universal mechanism that allows each agent to locally detect that the system has converged to the sought configuration with high probability. To illustrate our mechanism, we use it to detect the instant at which the proportion problem is solved. Specifically, let nA(resp. nB) be the number of agents that initially started in state nA(resp. B) and γA= nA/n, where n is the total number of agents. Our protocol guarantees, with a given precision ε > 0 and any high probability 1 - 6, that after O (n ln(n/δ)) interactions, any queried agent that has set the detection flag will output the correct value of the proportion γAof agents which started in state A, by maintaining no more than O (ln(n)/ε) integers. We are not aware of any such results. Simulation results illustrate our theoretical analysis.

We consider a large system populated by n anonymous nodes that communicate through asynchronous and pair-wise interactions. The aim of these interactions is for each node to converge toward a global property of the system, that depends on the initial state of each node. In this paper we focus on both the counting and proportion problems. We show that for any δ ϵ (0, 1), the number of interactions needed per node to converge is O(ln(n/δ)) with probability at least 1-δ. We also prove that each node can determine, with any high probability, the proportion of nodes that initially started in a given state without knowing the number of nodes in the system. This work provides a precise analysis of the convergence bounds, and shows that using the 4-norm is very effective to derive useful bounds.

Decentralized cryptocurrency systems offer a medium of exchange secured by cryptography, without the need of a centralized banking authority. Among others, Bitcoin is considered as the most mature one. Its popularity lies on the introduction of the concept of the blockchain, a public distributed ledger shared by all participants of the system. Double spending attacks and blockchain forks are two main issues in blockchain-based protocols. The first one refers to the ability of an adversary to use the very same bitcoin more than once, while blockchain forks cause transient inconsistencies in the blockchain. We show through probabilistic analysis that the reliability of recent solutions that exclusively rely on a particular type of Bitcoin actors, called miners, to guarantee the consistency of Bitcoin operations, drastically decreases with the size of the blockchain.

The computational model of population protocols is a formalism that allows the analysis of properties emerging from simple and pairwise interactions among a very large number of anonymous finite-state agents. Significant work has been done so far to determine which problems are solvable in this model and at which cost in terms of states used by the agents and time needed to converge. The problem tackled in this paper is the population proportion problem: each agent starts independently from each other in one of two states, say A or B, and the objective is for each agent to determine the proportion of agents that initially started in state A, assuming that each agent only uses a finite set of states, and does not know the number n of agents. We propose a solution which guarantees that in presence of a uniform probabilistic scheduler every agent outputs the population proportion with any precision ε ∈ (0, 1) with any high probability after having interacted O(log n) times. The number of states maintained by every agent is optimal and is equal to 2⌈3/(4ε)⌉+1. Finally, we show that our solution is optimal in time and space to solve the counting problem, a generalization of the proportion problem. Finally, simulation results illustrate our theoretical analysis.

The context of this work is the well studied dissemination of information in large scale distributed networks through pairwise interactions. This problem, originally called rumor mongering, and then rumor spreading has mainly been investigated in the synchronous model. This model relies on the assumption that all the nodes of the network act in synchrony, that is, at each round of the protocol, each node is allowed to contact a random neighbor. In this paper, we drop this assumption under the argument that it is not realistic in large scale systems. We thus consider the asynchronous variant, where at time unit, a single node interacts with a randomly chosen neighbor. We perform a thorough study of Tn the total number of interactions needed for all the n nodes of the network to discover the rumor. While most of the existing results involve huge constants that do not allow for comparing different protocols, we prove that in a complete graph of size n ≥ 2, the probability that Tn> k for all k ≥ 1 is less than (1+(2k(n-2)2)/(n))(1-2/n)(k-1). We also study the behavior of the complementary distribution of Tnat point cE(Tn) when n tends to infinity for c ≠ 1. We end our analysis by conjecturing that when n tends to infinity, Tn> E(Tn) with probability close to 0.4484.

Video traffic, which represents an increasing fraction of the Internet traffic, requires end-to-end quality of service (QoS) guarantees for inter-domain routing. However, providing such guarantees remains a challenge essentially because it requires a strong and fair cooperation among the different network operators or Autonomous Systems (ASes), crossed by the traffic. Having a single AS on the path that does not meet its QoS engagement is sufficient to violate the end-to-end QoS guarantees. Unfortunately, the client is not capable of distinguishing unfair ASes from honest ones at the time it selects its path. Reputation mechanisms turn out to be very efficient tools to estimate how trustworthy and reliable entities can be without requiring the help of any central authority. They are effective to foster cooperation by remedying selfishness. In this position paper, we identify the main properties a reputation mechanism should meet to improve inter-domain QoS routing, and we provide a coarsed-grain vision of the design of such a mechanism.

This paper presents a solution to the well-known Test-and-Set operation in asynchronous systems prone to process crashes. Test-and-Set is a synchronization operation that, when invoked by a set of processes, returns "yes" to a unique process and returns "no" to all the others. Recently many advances in implementing Test and Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test-and-Set object for message passing distributed systems. This implementation can be invoked by any number p of processes. It has an expected step complexity in O(p) and an expected message complexity in O(np), where n is the total number of processes in the system. The proposed Test and Set object is built atop a new basic building block that allows to select a winning group among two groups of processes.

The population protocol model provides theoretical foundations for analyzing the properties emerging from simple and pair wise interactions among a very large number n of anonymous agents. The problem tackled in this paper is the following one: is there an efficient population protocol that exactly counts the difference k between the number of agents that initially and independently set their state to "A" and the one that initially set it to "B", assuming that each agent only uses a finite set of states? We propose a solution which guarantees with any high probability that after O(log n) interactions any agent outputs the exact value of k. Simulation results illustrate our theoretical analysis.

We consider the problem of identifying global iceberg attacks in massive and physically distributed streams. A global iceberg is a distributed denial of service attack, where some elements globally recur many times across the distributed streams, but locally, they do not appear as a deny of service. A natural solution to defend against global iceberg attacks is to rely on multiple routers that locally scan their network traffic, and regularly provide monitoring information to a server in charge of collecting and aggregating all the monitored information. Any relevant solution to this problem must minimise the communication between the routers and the coordinator, and the space required by each node to analyse its stream. We propose a distributed algorithm that tracks global icebergs on the fly with guaranteed error bounds, limited memory and processing requirements. We present a thorough analysis of our algorithm performance. In particular we derive a tight upper bound on the number of bits communicated between the multiple routers and the coordinator in presence of an oblivious adversary. Finally, we present the main results of the experiments we have run on a cluster of single-board computers. Those experiments confirm the efficiency and accuracy of our algorithm to track global icebergs hidden in very large input data streams exhibiting different shapes.

The context of this work is the online characterization of errors in large scale systems. In particular, we address the following question: Given two successive configurations of the system, can we distinguish massive errors from isolated ones, the former ones impacting a large number of nodes while the second ones affect solely a small number of them, or even a single one? The rationale of this question is twofold. First, from a theoretical point of view, we characterize errors with respect to their neighbourhood, and we show that there are error scenarios for which isolated and massive errors are indistinguishable from an omniscient observer point of view. We then relax the definition of this problem by introducing unresolved configurations, and exhibit necessary and sufficient conditions that allow any node to determine the type of errors it has been impacted by. These conditions only depend on the close neighbourhood of each node and thus are locally computable. We present algorithms that implement these conditions, and show through extensive simulations, their performances. Now from a practical point of view, distinguishing isolated errors from massive ones is of utmost importance for networks providers. For instance, for Internet service providers that operate millions of home gateways, it would be very interesting to have procedures that allow gateways to self distinguish whether their dysfunction is caused by network-level errors or by their own hardware or software, and to notify the service provider only in the latter case.

In this paper, we consider the setting of large scale distributed systems, in which each node needs to quickly process a huge amount of data received in the form of a stream that may have been tampered with by an adversary. In this situation, a fundamental problem is how to detect and quantify the amount of work performed by the adversary. To address this issue, we propose a novel algorithm AnKLe for estimating the Kullback-Leibler divergence of an observed stream compared with the expected one. AnKLe combines sampling techniques and information-theoretic methods. It is very efficient, both in terms of space and time complexities, and requires only a single pass over the data stream. We show that AnKLe is an (ε, δ)-approximation algorithm with a space complexity Õ(1/ε + 1/ε2) bits in "most" cases, and Õ(1/ε + (n-ε-1)/ε2) otherwise, where n is the number of distinct data items in a stream. Moreover, we propose a distributed version of AnKLe that requires at most O (rℓ (log n + 1)) bits of communication between the ℓ participating nodes, where r is number of rounds of the algorithm. Experimental results show that the estimation provided by AnKLe remains accurate even for different adversarial settings for which the quality of other methods dramatically decreases.

We consider the problem of achieving uniform node sampling in large scale systems in presence of a strong adversary. We first propose an omniscient strategy that processes on the fly an unbounded and arbitrarily biased input stream made of node identifiers exchanged within the system, and outputs a stream that preserves Uniformity and Freshness properties. We show through Markov chains analysis that both properties hold despite any arbitrary bias introduced by the adversary. We then propose a knowledge-free strategy and show through extensive simulations that this strategy accurately approximates the omniscient one. We also evaluate its resilience against a strong adversary by studying two representative attacks (flooding and targeted attacks). We quantify the minimum number of identifiers that the adversary must insert in the input stream to prevent uniformity. To our knowledge, such an analysis has never been proposed before.

Reputation systems allow to estimate the trustworthiness of entities based on their past behavior. Electronic commerce, peer-to-peer routing and collaborative environments, just to cite a few, highly benefit from using reputation systems. To guarantee an accurate estimation, reputation systems typically rely on a central authority, on the identification and authentication of all the participants, or both. In this paper, we go a step further by presenting a distributed reputation mechanism which is robust against malicious behaviors and that preserves the privacy of its clients. Guaranteed error bounds on the estimation are provided.

In this paper, we consider the problem of estimating the distance between any two large data streams in small-space constraint. This problem is of utmost importance in data intensive monitoring applications where input streams are generated rapidly. These streams need to be processed on the fly and accurately to quickly determine any deviance from nominal behavior. We present a new metric, the Sketch *-metric, which allows to define a distance between updatable summaries (or sketches) of large data streams. An important feature of the Sketch *-metric is that, given a measure on the entire initial data streams, the Sketch *-metric preserves the axioms of the latter measure on the sketch. Extensive experiments conducted on both synthetic traces and real data sets allow us to validate the robustness and accuracy of the Sketch *-metric.

In this paper, we consider the setting of large scale distributed systems, in which each node needs to quickly process a huge amount of data received in the form of a stream that may have been tampered with by an adversary. In this situation, a fundamental problem is how to detect and quantify the amount of work performed by the adversary. To address this issue, we have proposed in a prior work, AnKLe, a one pass algorithm for estimating the Kullback-Leibler divergence of an observed stream compared to the expected one. Experimental evaluations have shown that the estimation provided by AnKLe is accurate for different adversarial settings for which the quality of other methods dramatically decreases. In the present paper, considering n as the number of distinct data items in a stream, we show that AnKLe is an (ε, δ)-approximation algorithm with a space complexity Õ(1/ε + 1/ε2) bits in “most” cases, and Õ(1/ε + n-ε-1/ε2) otherwise. To the best of our knowledge, an approximation algorithm for estimating the Kullback-Leibler divergence has never been analyzed before.

In this paper we consider the problem of targeted attacks in large scale peer-to-peer overlays. These attacks aimed at exhausting key resources of targeted hosts to diminish their capacity to provide or receive services. To defend the system against such attacks, we rely on clustering and implement induced churn to preserve randomness of nodes identifiers so that adversarial predictions are impossible. We propose robust join, leave, merge and split operations to discourage brute force denial of services and pollution attacks. We show that combining a small amount of randomization in the operations, and adequately tuning the sojourn time of peers in the same region of the overlay allows first to decrease the effect of targeted attacks at cluster level, and second to prevent pollution propagation in the whole overlay.

In this paper we evaluate the performance of DataCube a P2P persistent data storage platform. This platform exploits the properties of cluster-based peer-to-peer structured overlays together with a hybrid redundancy schema (a compound of light replication and rateless erasure coding) to guarantee durable access and integrity of data despite adversarial attacks. The triptych "availability - storage overhead - bandwidth usage" is evaluated, and results show that despite massive attacks and high churn, DataCube performs remarkably well. We evaluate the performance of the rateless erasure codes implemented in DataCube. Our exploration shows how parameters selection impacts codes performance mainly in terms of decoding time, and collect strategies.

In this paper we present an analytic study of the impact of churn in cluster-based overlay networks. Cluster-based overlays keep the best of unstructured and structured overlays in terms of scalability, fault-tolerance and stability. Most of join and leave events have no impact on the overall overlay topology making these overlays highly robust to high churn. The only situations that effectively give rise to topology modifications are when clusters need to split because they exceed some maximal size or need to merge because they fall under some minimal size. Although these operations are scalable, they are intricate in the sense that they need synchronization among nodes involved in these operations. In this paper we accurately predict the frequency at which the topology of the overlay changes according to the number of join/leave operations. Our analysis improves upon existing studies by showing that these relevant topological changes are very infrequent, namely θ(N) join/leave events are required before any of these topological operations occur, where N is the number of peers currently in the system. Such a result clearly demonstrates the appropriateness of these overlays to high churn.

This paper presents the design of a P2P data persistent platform. Durable access and integrity of the data are ensured despite massive attacks. This platform, named DataCube, exploits the properties of cluster-based peer-to-peer substrates to implement a compound of full replication and rateless erasure codes. DataCube guarantees durable access and integrity of data despite adversarial attacks. In particular, the recovery of damaged data is achieved through the retrieval of coded blocks whose integrity is checked on the fly.

Awerbuch and Scheideler have shown that peer-to-peer overlays networks can survive Byzantine attacks only 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. In this paper we investigate adversarial strategies by following specific protocols. Our analysis demonstrates first that an adversary can very quickly subvert DHT-based overlays by simply never triggering leave operations. We then show that when all nodes (honest and malicious ones) are imposed on a limited lifetime, the system eventually reaches a stationary regime where the ratio of polluted clusters is bounded, independently from the initial amount of corruption in the system.

Publish/Subscribe systems provide a useful platform for delivering data (events) from publishers to subscribers in an anonymous fashion in distributed networks. In this paper, we promote a novel design principle for self-. dynamic and reliable content-based publish/subscribe systems and perform a comparative analysis of its probabilistic and deterministic implementations. More specifically, we present a generic content-based publish/subscribe system, called DPS (Dynamic Publish/Subscribe). DPS combines classical content-based filtering with self-. (self-organizing, selfconfiguring, and self-healing) subscription-driven clustering of subscribers. DPS gracefully adapts to failures and changes in the system while achieving scalable events delivery. DPS includes a variety of fault-tolerant deterministic and probabilistic content-based publication/subscription schemes. These schemes are targeted toward scalability, and aim at reducing and distributing the number of messages exchanged. Reliability and scalability of our system are shown through analytical and experimental evaluation.

We consider the problem of fair resource sharing to optimize the performance of resource sharing in peer to peer systems. Resource sharing systems currently face rational peers which may exhibit a variety of strategies including: no participation, also referred as free-riding, and greedy behavior. The first aspect has been extensively studied in the late years, while the second one has not received much attention. The broad class of proposed solutions focuses on designing incentives to reward cooperative peers. The side effect of these incentives is twofold: the system load is not balanced and the resource potential of the system is not fully exploited. The P2P fair resource sharing aims at both balancing the load and maximizing the use of system resources. The contribution of our work is twofold. First, we specify the P2P fair resource sharing problem and propose a mechanism to solve it in large scale dynamic networks with rational users. Our mechanism is composed of a novel incentive (i.e. fair cooperation) and an algorithmic part encapsulated in a middleware layer. Second, we propose an architecture for our mechanism middleware layer including four distributed services that bring together several research area: aggregation, semantic group membership and tracking. Finally, we implement our mechanism using a peer-to-peer unstructured model and evaluate it through simulations

A distributed computation is usually modeled as a partially ordered set of relevant events (the relevant events are a subset of the primitive events produced by the computation). An important causality-related distributed computing problem, that we call the Immediate Predecessors Tracking (IPT) problem, consists in associating with each relevant event, on the fly and without using additional control messages, the set of relevant events that are its immediate predecessors in the partial order. So, IPT is the on-the-fly computation of the transitive reduction (i.e., Hasse diagram) of the causality relation defined by a distributed computation. This paper addresses the IPT problem: it presents a family of protocols that provides each relevant event with a timestamp that exactly identifies its immediate predecessors. The family is defined by a general condition that allows application messages to piggyback control information whose size can be smaller than $n$ (the number of processes). In that sense, this family defines message size-efficient IPT protocols. According to the way the general condition is implemented, different IPT protocols can be obtained. Two of them are exhibited.

Considers the priority inversion problem in an actively replicated system. Priority inversion was originally defined in the context of nonreplicated systems. Therefore, we first introduce the concept of group priority inversion, which extends the concept of (local) priority inversion to the context of a group of processors that perform an actively replicated processing. We then present the properties of a request scheduling protocol to enforce a total ordering for the processing of requests while avoiding group priority inversions. These properties have been implemented in a protocol that relies on a timed asynchronous system model equipped with a failure detector of the class /spl diams/S. The proposed solution allows us to replicate a critical server while ensuring that the processing of all the incoming requests is consistent (mechanisms for solving the atomic broadcast problem) and predictable (mechanisms for solving the group priority inversion problem). Thus, the described request scheduling protocol is a key component which can be used to develop fault-tolerant real-time applications in a timed asynchronous system.

We consider the priority inversion problem in an actively replicated system. Priority inversion was originally defined in the context of non-replicated systems. Therefore we first introduce the concept of group priority inversion, which extends the concept of (local) priority inversion to the context of a group of processors that perform an actively replicated processing. We then present the properties of a request scheduling protocol to enforce a total ordering for the processing of requests while avoiding group priority inversions. These properties have been implemented in a protocol that relies on a timed asynchronous system model equipped with a failure detector of the class /spl square/S. The proposed solution allows one to replicate a critical server while ensuring that the processing of all the incoming requests is consistent (mechanisms for solving the atomic broadcast problem) and predictable (mechanisms for solving the group priority inversion problem). Thus, the described request scheduling protocol is a key component which can be used to develop fault tolerant real time applications in a timed asynchronous system.

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.

This paper provides a method to verify that the properties we consider critical to build a correct multimedia application are met. These properties are the compatibility of the protocols employed by the computing elements to interact with each other and the timeliness of the application. The method relies on (i) an original model that enables a software architect to specify the basic elements of its multimedia application according to the two aforementioned properties, and (ii) two algorithms that determine the best level of perceived quality of service that can be guaranteed by the application.

Typically, most distributed, dependable, real time systems designed in the past can only meet the particular requirements of the application domain to which they were targeted. This approach led to specific, non flexible, dedicated and non reusable solutions, often based on specialized hardware. The paper presents an alternative approach where a flexible run time support for distributed dependable hard real time applications is built on top of off-the-shelf hardware. This support has been designed by considering three fundamental and complementary aspects: real time, to support applications that exhibit strict timing constraints; fault tolerance, to provide a high degree of reliability through the transparent provision of fault tolerant mechanisms; and flexibility, to allow the modifications of components of the run time support without having to rewrite it entirely, and to support a large range of application domains, real time kernels and hardware.

Most distributed safety critical real time systems designed in the past have been specialized to meet the particular requirements of the application domain to which they were targeted. This approach led to specific, inflexible, dedicated and non reusable solutions, often based on specialized hardware. The paper presents an overview of HADES, which provides a set of flexible tools built on top of off the shelf hardware, and designed to help in the construction of a panel of distributed safety critical real time applications. In order for HADES to support the execution of the widest range of applications, we have followed a rigorous methodology based on: (i) the separation of services dedicated to a specific application domain (scheduling policy) from services providing a range of robustness properties common to a large spectrum of application domains (e.g. task dispatching, fault detection, clock synchronization, monitoring); (ii) the provision of a precise cost information induced by all these services in order to increase the accuracy of the application feasibility test.