In this paper, we propose a methodology to design and analyze the correctness and fairness of committee-based blockchains. We specify the problem that these blockchains implement, specifically, the Byzantine repeated consensus problem. Moreover, we define the problem of fair reward distribution among committee members and study the impact of synchronous assumptions on fairness . It is common knowledge that in permisionless blockchain systems, the main threat is the tragedy of commons that may yield the system to collapse if the rewarding mechanism is not adequate. At minimum, the reward mechanism must be fair , i.e., distribute the rewards in proportion to the merit of the participants. We prove, for the first time in blockchain systems, that in repeated-consensus based blockchains there exists an (eventual) fair rewarding mechanism if and only if the system is (eventual) synchronous. As a case study, we study Tendermint both from Byzantine Repeated Consensus perspective and its fairness with respect to the rewarding of committee members. We prove that in eventual synchronous systems, a modified version of Tendermint solves: (i) one-shot consensus for the validation of one single block with message complexity O ( n 3 ) where is the size of the validators set and (ii) a variant of the repeated consensus problem for multiple blocks. Our second contribution is related to the fairness of the Tendermint rewarding mechanism. We show that the rewarding in Tendermint is not fair, but a small modification of Tendermint is eventually fair.

Ethereum has undergone a recent change called the Merge , which made Ethereum a Proof-of-Stake blockchain shifting closer to BFT consensus. Ethereum, which wishes to keep the best of the two protocol designs (BFT and Nakomoto-style), now has a convoluted consensus protocol as its core. The result is a blockchain possibly being produced in a tree-like form while participants try to finalize blocks. We categorize different attacks jeopardizing the liveness of the protocol. The Ethereum community has responded by creating patches against some of them. We discovered a new attack on the patched protocol. To support our analysis, we propose a new high-level formalization of the properties of liveness and availability of the Ethereum blockchain, and we provide pseudo-code. We believe this formalization to be useful for other analyses as well. Our results yield that the Ethereum Proof-of-Stake has safety but only probabilistic liveness. The probability of the liveness is influenced by the parameter describing the time frame allowed for validators to change their mind about the current main chain.

In May 2023, the Ethereum blockchain experienced its first inactivity leak, a mechanism designed to reinstate chain finalization amid persistent network disruptions. This mechanism aims to reduce the voting power of validators who are unreachable within the network, reallocating this power to active validators. This paper investigates the implications of the inactivity leak on safety within the Ethereum blockchain. Our theoretical analysis reveals scenarios where actions by Byzantine validators expedite the finalization of two conflicting branches, and instances where Byzantine validators reach a voting power exceeding the critical safety threshold of one-third. Additionally, we revisit the probabilistic bouncing attack, illustrating how the inactivity leak can result in a probabilistic breach of safety, potentially allowing Byzantine validators to exceed the one-third safety threshold. Our findings uncover how penalizing inactive nodes can compromise blockchain properties, particularly in the presence of Byzantine validators capable of coordinating actions.

Federated Learning (FL) has gained prominence as a decentralized and privacy-preserving paradigm that enables multiple clients to collaboratively train a machine learning model under the supervision of a central server. Instead of centralizing the data, clients keep their data locally and share only model parameters during multiple communication rounds. However, recent attacks, such as gradient reconstruction attacks (GRAs) show privacy issues when an attacker knows the communication of a client. In the literature, these privacy issues are mainly explored when clients compute new parameters using a single gradient descent step on their data (FedSGD) and then send them back to the remote server. In a more realistic scenario, the clients' protocol is based on several gradient descent steps (FedAvg). This protocol adds intermediate computation steps, which are unknown from the attacker, thus making GRAs less successful. In this incremental paper, we conduct exhaustive experiments on four state-of-the-art attacks under the FedAvg protocol, on a very basic and a more complex neural network (ResNet-18) with CIFAR100 dataset. These experiments provide the following results 1) a privacy-utility trade-off analysis, 2) insights on the choice of attacks' hyperparameters, 3) the client's local learning rate has little impact on attacks' effectiveness 4) a proof that the privacy risk is not necessarily decreasing over rounds, contrary to common belief.

This paper investigates whether following the fork-choice rule in the Ethereum PoS consensus protocol constitutes a Nash equilibrium - i.e., whether the protocol that maintains the canonical chain in Ethereum is incentive-compatible. Specifically, we explore whether selfish participants may attempt to manipulate the fork-choice rule by forking out previous blocks and capturing the rewards associated with those blocks. Our analysis considers two strategies for participants: the obedient strategy, which adheres to the prescribed protocol, and the cunning strategy, which attempts to manipulate the fork-choice rule to gain more rewards. We evaluate the conditions under which selfish participants might deviate from the obedient strategy. We found that, in a synchronous system, following the prescribed fork-choice rule is incentive-compatible. However, in an eventually synchronous system, the protocol is eventually incentive-compatible - that is, only a limited number of proposers will find it profitable to fork the chain during the synchronous period. After this sequence of cunning proposers, subsequent proposers will find it more profitable to follow the protocol.

We consider the problem of supporting payment transactions in an asynchronous system in which up to f validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that, in the case of a single owner, this problem can be solved without consensus by using byzantine quorum systems (requiring a quorum of 2f + 1 validations per transaction). Nonetheless, the process of validating transactions remains sequential. For example, if one has a balance of ten coins and intends to make separate payments of two coins each to two distinct recipients, both transactions must undergo processing by a common correct validator. On the other hand, these two transactions are non-conflicting as they do not lead to double spending, allowing in principle for parallel validation. In this paper, we show that it is possible to validate payment transactions in parallel with less than f validations per transaction in an asynchronous system, provided that each transaction spends only a small fraction of a balance. Our solution relies on a novel class of probabilistic quorum systems that we introduce in this paper, termed (k1, k2) -quorum systems. In the absence of an adaptive adversary, (k1,k2)-quorum systems can be used to enable concurrent and asynchronous validation of up to k1 transactions while preventing validation of more than k2 transactions. In the presence of an adaptive adversary, at least k1 transactions can be validated concurrently, but validation of more than k′2 > k2 transactions is prevented, with the difference k′2 − k2 dependent on the quorum system's validation slack -- a term defined in this paper. Employing a (k1, k2)-quorum system, we introduce protocols enabling a payer to validate multiple fractional spending transactions in parallel with less than f + 1 validations per transaction. Subsequently, the payer reclaims any remaining funds through a fully validated transaction, referred to as a settlement transaction.

Federated Learning is a decentralized framework that enables multiple clients to collaboratively train a machine learning model under the orchestration of a central server without sharing their local data. The centrality of this framework represents a point of failure which is addressed in literature by blockchain-based federated learning approaches. While ensuring a fully-decentralized solution with traceability, such approaches still face several challenges about integrity, confidentiality and scalability to be practically deployed. In this paper we propose Fantastyc, a solution designed to address these challenges that have been never met together in the state of the art.

Fifth-generation wireless technology, or 5G, promises increased data speeds, lower latency and greater capacity for mobile communications, enabling the growth of the Internet of Things (IoT). Network slicing is an advantageous feature of 5G that enables the creation of multiple virtual networks to meet the performance, security, and reliability needs of different services. This feature, combined with blockchain technology, provides secure and transparent data sharing between devices and networks. In addition, blockchain-enabled network slicing improves 5G network management and creates new business models for industries such as healthcare, transportation, and manufacturing. However, most current blockchain systems are limited in their ability to handle high throughput, which is not equivalent to what 5G can do. Therefore, sharding-based blockchain is proposed as a possible solution to improve the scalability and throughput of blockchain networks. By dividing the network into parts or shards, transactions can be processed simultaneously, allowing for faster transaction verification times and increased network capacity. Although current sharding-based blockchain networks have some limitations, such as static sharding policies that cannot cope with the dynamic blockchain environment, an adaptive sharding blockchain system using Deep Reinforcement Learning (DRL) methods has been proposed to address this situation. The approach allows the system to change or adapt the shard specifications, such as shard size or block size, whenever necessary to ensure maximum throughput while maintaining the security and integrity of the blockchain network.

We consider the problem of validating payment transactions in an asynchronous system in which up to f validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that this problem can be solved without consensus by using byzantine quorum systems - requiring full-quorum validation, i.e. at least 2f + 1 validations per transaction. We show that it is possible to validate transactions in parallel with less than f validations per transaction if each transaction spends no more that a small fraction of an initial balance. Our solution relies on (k1, k2)-quorum systems, a novel class of quorum systems that we introduce in this paper. Under an adaptive adversary, these systems can be used to allow k1 transactions to be validated and prevent more than k′2 > k2 transactions from being validated, the difference k′2 − k2 being dependent on the quorum system's validation slack, which we define in this paper. Using (k1, k2)-quorum systems, a payer can execute multiple partial spending transactions to spend a portion of its initial balance with less than full quorum validation - less than f validations per transaction - then reclaim any remaining funds using one fully validated transaction, which we call a settlement transaction.

An accountable distributed system provides means to detect deviations of system components from their expected behavior. It is natural to complement fault detection with a reconfiguration mechanism, so that the system could heal itself, by replacing malfunctioning parts with new ones. In this paper, we describe a framework that can be used to implement a large class of accountable and reconfigurable replicated services. We build atop the fundamental lattice agreement abstraction lying at the core of storage systems and cryptocurrencies. Our asynchronous implementation of accountable lattice agreement ensures that every violation of consistency is followed by an undeniable evidence of misbehavior of a faulty replica. The system can then be seamlessly reconfigured by evicting faulty replicas, adding new ones and merging inconsistent states. We believe that this paper opens a direction towards asynchronous "self-healing" systems that combine accountability and reconfiguration.

International audience

An accountable distributed system provides means to detect deviations of system components from their expected behavior. It is natural to complement fault detection with a reconfiguration mechanism, so that the system could heal itself, by replacing malfunctioning parts with new ones. In this paper, we describe a framework that can be used to implement a large class of accountable and reconfigurable replicated services. We build atop the fundamental lattice agreement abstraction lying at the core of storage systems and cryptocurrencies. Our asynchronous implementation of accountable lattice agreement ensures that every violation of consistency is followed by an undeniable evidence of misbehavior of a faulty replica. The system can then be seamlessly reconfigured by evicting faulty replicas, adding new ones and merging inconsistent states. We believe that this paper opens a direction towards asynchronous "self-healing" systems that combine accountability and reconfiguration.

International audience

Reconfiguration is one of the central mechanisms in distributed systems. Due to failures and connectivity disruptions, the very set of service replicas (or servers) and their roles in the computation may have to be reconfigured over time. To provide the desired level of consistency and availability to applications running on top of these servers, the clients of the service should be able to reach some form of agreement on the system configuration. We observe that this agreement is naturally captured via a lattice partial order on the system states. We propose an asynchronous implementation of reconfigurable lattice agreement that implies elegant reconfigurable versions of a large class of lattice abstract data types, such as max-registers and conflict detectors, as well as popular distributed programming abstractions, such as atomic snapshot and commit-adopt.

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.

Committee-based blockchains are among the most popular alternatives of proof-of-work based blockchains, such as Bitcoin. They provide strong consistency (no fork) under classical assumptions, and avoid using energy-consuming mechanisms to add new blocks in the blockchain. For each block, these blockchains use a committee that executes Byzantine-fault tolerant distributed consensus to decide the next block they will add in the blockchain. Unlike Bitcoin, where there is only one creator per block, in committee-based blockchain any block is cooperatively created. In order to incentivize committee members to participate in the creation of new blocks, rewarding schemes have to be designed. In this paper, we study the fairness of rewarding in committee-based blockchains and we provide necessary and sufficient conditions on the system communication under which it is possible to have a fair reward mechanism.

Industry 4.0 is one of the most prominent initiatives towards the vision of smart manufacturing to foster efficiency and synergy among suppliers, producers, and customers. It will transform the production systems into a smart, fully integrated, and optimized cyber-physical production systems (CPPS) based on technology enablers such as Internet of Things (IoT). Moreover, the availability of a wide range of data and information in the context of CPPS provides a huge possibility to create novel business opportunities. However, for these business opportunities to materialize successfully there is an evident need to have an efficient communication and clear visualization of the new strategies and the underlying operational process among all the stakeholders involved in the manufacturing value chain. In this paper, we propose a model-based approach for creating and communicating business strategies (mission, goals, and tactics) and bridging the gap between the business strategies and corresponding operational processes using Business Motivation Model (BMM) and Business Process Modeling and Notation (BPMN) respectively. Concretely, we do the following, (i) create BMM models to communicate business ideas and connect corresponding business tactics to the processes models in BPMN, (ii) simulate processes to check achievable KPIs corresponding to different strategies (modeled in BMM), and (iii) define organizational units in BMM that perform tasks modeled in BPMN. We illustrate our approach through an exemplar case study about production of plastic cups by modeling high-level strategies and their underlying processes. To prove the feasibility of our work, we used and developed the BMM and BPMN plugins based on Eclipse Papyrus framework.

The adoption of AUTOSAR and Model Driven Engineering (MDE) for the design of automotive software architectures allows an early analysis of system properties and the automatic synthesis of architecture and software implementation. To select and configure the architecture with respect to timing constraints, knowledge about the worst case execution times (WCET) of functions is required. An accurate evaluation of the WCET is only possible when reusing legacy functionality or very late in the development and procurement process. To drive the integration of SW components belonging to systems with timing constraints, automotive methodologies propose to assign WCET budgets to functions. This paper presents two solutions to assign budgets, while considering at the same time the problem of SW/HW synthesis. The first solution is a one-step algorithm. The second is an iterative improvement procedure with a staged approach that scales better to very large size systems. Both methods are evaluated on industrial systems to study their effectiveness and scalability.

Synthesis of automotive architectures is a complex problem that needs an automated support. AUTOSAR, standard for the specification of automotive architectures, defines a synthesis process of software components and their connections in a set of fixed-priority OS tasks distributed over a network of ECUs. During the synthesis process software components are allocated on ECU-s. Since each component encapsulates a set of so-called runnable entities, synthesis completes by partitioning runnable entities in OS tasks with assigned fixed priorities. This paper proposes an optimization approach for the synthesis of AUTOSAR architectures based on genetic algorithms and mixed integer linear programming techniques. Optimization criteria consider end-to-end timing responses and memory consumption.

Modern development methodologies from the industry and the academia for complex real-time systems define a stage in which application functions are deployed onto an execution platform. The deployment consists of the placement of functions on a distributed network of nodes, the partitioning of functions in tasks and the scheduling of tasks and messages. None of the existing optimization techniques deal with the three stages of the deployment problem at the same time. In this paper, we present a staged approach towards the efficient deployment of real-time functions based on genetic algorithms and mixed integer linear programming techniques. Application to case studies shows the applicability of the method to industry-size systems and the quality of the obtained solutions when compared to the true optimum for small size examples.

The synthesis of a valid and optimized deployment model from functional and platform models is a crucial issue in the development of distributed real-time systems. The synthesis consists in the allocation of functions/signals to execution nodes/communication buses, the mapping of functions/signals into tasks/messages and the priority assignment to tasks/messages. Current approaches provide partial solutions for the synthesis of a deployment model on distributed platforms, as either the allocation or the mapping is fixed a-priori. In order to tackle this problem we propose an optimization technique, based on two different mathematical programming formulations, to handle optimization of both allocation and mapping. The optimization is multi-objective and considers extensibility maximization, latency minimization and minimization of the number of tasks. The obtained solutions satisfy timing and platform resources requirements. An automotive case study shows the effectiveness of our approach.

AUTOSAR (Automotive Open System Architecture) is enjoying increasing interest and broad acceptance in the automotive domain. AUTOSAR aims at defining an open standardized software architecture to face future challenges in automotive development including the development of time-critical systems (e.g. brake-by-wire or steer-by-wire). Mastering the development of such systems requires being able to analyze their real-time behavior. Scheduling analysis is the theory that studies how far a real-time system may satisfy its real-time requirements against its real-time properties. In this paper, we will study to what extent it is possible to apply some of those scheduling analysis techniques on real-time systems deployed on AUTOSAR-compliant architectures. The paper focuses on scheduling analysis techniques implemented in one open source tool. A concrete case study shows the feasibility of the approach and shows scheduling analysis results.

The paper extends the AUTOSAR meta-model to enable feasibility predictions on the provision of fault-tolerant support for application components. We focus on a fault-tolerant support based on software replication techniques. The meta-model is extended in order to evaluate different replication strategies, in terms of replication styles, types of faults to be tolerated, replicas placement. This extension is realized by a UML profile. A model-based approach is presented aiming at the definition of a so-called Application Replication View, in which a replication strategy is specified for safety critical application components. A separate model, called Application Timing View, defines timing constraints for system responses. The combination of the two views will enable schedulability analysis of the fault-tolerant application. Schedulability analysis considers the task set composed of application tasks and the additional tasks injected by replication. An automotive case study is presented showing the applicability of the approach.

In model based approaches for real-time systems (RTS) development, an iterative process that consists in the early stage verification of real-time constraints fulfillment according to a given design is usually performed in order to detect as early as possible unfeasible designs. Schedulability analysis allows this early verification of timing constraints according to so called Schedulability Analysis Model (SAM). This paper proposes a configurable framework for implementation synthesis of component oriented specification that is able to preserve the SAM timing properties that are validated at an early stage of the RTS design.

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.

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

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.

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.

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.