Abstract Publish/subscribe is a mature communication paradigm to route and deliver events from publishers to interested subscribers. Initially conceived for large scale systems, e.g., the Internet, it has been used more recently in new scenarios, e.g., wireless sensor networks and the Internet of Things (IoT), where mobility and dynamicity are the norm. The loose-coupling and asynchronicity of publish/subscribe makes it an interesting choice for IoT scenarios, i.e., each node in an IoT network can choose a different role depending on its location, capabilities, etc. This paper presents MFT-PubSub, a fully mobile and fault tolerant content-based publish/subscribe protocol. Our proposal is a purely reactive solution for mobility in a publish/subscribe system without any kind of limits on the mobility patterns of the nodes. A wireless ad hoc network is created without the need of any previous connections or knowledge on the nodes. Handling the mobility, be it physical or logical, of both clients and brokers. We prove the validity of our solution by experimentation, and compare it with AODV, a routing protocol for mobile ad hoc networking. The simulations show an improvement on message delivery rate over previously used protocols.

This paper introduces a new leaderless Byzantine consensus called the Democratic Byzantine Fault Tolerance (DBFT) for blockchains. While most blockchain consensus protocols rely on a correct leader or coordinator to terminate, our algorithm can terminate even when its coordinator is faulty. The key idea is to allow processes to complete asynchronous rounds as soon as they receive a threshold of messages, instead of having to wait for a message from a coordinator that may be slow. The resulting decentralization is particularly appealing for blockchains for two reasons: (i) each node plays a similar role in the execution of the consensus, hence making the decision inherently “democratic” (ii) decentralization avoids bottlenecks by balancing the load, making the solution scalable. DBFT is deterministic, assumes partial synchrony, is resilience optimal, time optimal and does not need signatures. We first present a simple safe binary Byzantine consensus algorithm, modify it to ensure termination, and finally present an optimized reduction from multivalue consensus to binary consensus whose fast path terminates in 4 message delays.

The proposed research addresses the problem of communicating events in a reliable and efficient manner between the producing and consuming devices. To do so, we will focus on the publish/subscribe paradigm. Commonly, this model has assumed a static topology of brokers that optimize event dissemination. The next step is to relax the conditions of the broker network in order to include fault tolerance and mobility in its elements, developing and validating new algorithms for highly dynamic publish/subscribe systems.

Fault-tolerant broadcast is a fundamental service in distributed systems, by which processes can communicate with each other consistently and reliably. It has two main forms: Reliable Broadcast (RB) and Uniform Reliable Broadcast (URB). This service has been extensively investigated in non-anonymous distributed systems where processes have unique identifers, usually assume the communication channels are reliable, which is not always the case in real systems. In this paper, the fault-tolerant broadcast service is studied in an anonymous asynchronous message passing distributed system model with fair lossy communication channels. Firstly, two simple and non-quiescent algorithms implementing RB and URB are given. Secondly, two new classes of failure detectors A_Theta and AP* are proposed. Finally, with the information provided by A_Theta and AP*, quiescent algorithms for both RB and URB are given.

In this work we consider the problem of leader election, abstraction used by many distributed services to select a unique process for coordinating actions. We propose an eventual leader election algorithm for partially synchronous systems prone to concurrent crash-recovery and omission failures where any process may suffer failures forever as long as a majority of processes meet some weak connectivity and reliability conditions.

We investigate the performance of the ChandraToueg and Paxos consensus algorithms, using as case study TrustedPals, a smartcard-based framework which allows to implement security policies in distributed systems. The current architecture of TrustedPals uses the Chandra-Toueg consensus algorithm adapted to the omission failure model. In this work, we propose to alternatively use the Paxos consensus algorithm, in order to extend the applicability of the framework to the crash-recovery failure model as well. We have performed simulations to compare these two consensus algorithms under different failure scenarios. Our results show that Paxos is more efficient than Chandra-Toueg if the first process which coordinates or leads a round suffers a failure, while both algorithms perform similarly when there are no failures.

This paper presents an evaluation of three communication-efficient algorithms implementing the Omega class of failure detectors, which provides an eventual leader election functionality, in distributed systems where processes can crash and recover. Communication efficiency means that eventually only a correct process, i.e., the elected leader, keeps sending a message periodically to the rest of processes. The first algorithm relies on the use of stable storage to store the identity of the leader and an incarnation number. The second algorithm does not use stable storage, but requires a majority of correct processes. Also, it is near-communication-efficient, since besides the leader, unstable processes, i.e., those that crash and recover infinitely often, may send messages periodically before they receive a message from the leader. Finally, the third algorithm does neither use stable storage nor require a majority of correct processes, but assumes that each process has access to a nondecreasing and persistent local clock. Using the OMNeT++ network simulation framework, we evaluate the performance and the quality of service provided by these algorithms, in terms of the number of messages exchanged among processes and the capability of the failure detector to provide a single leader, respectively.

This paper addresses the leader election problem in dynamic distributed systems with mobile processes. To do so, it is assumed that the system alternates periods of good and bad behavior, in the line of the timed asynchronous model of Cristian and Fetzer. We extend the eventual leadership properties recently proposed by Larrea et al. for non-mobile dynamic systems, defining two new properties that take into account graph joins/fragmentations due to process mobility. We also propose a new leader election algorithm in a weak mobile dynamic distributed system model. Using a categorization framework, we compare our system model with a number of models proposed in the literature, showing that our leader election algorithm works in a model which is weaker than the rest.

The integration of mobile devices within distributed systems introduces a wide range of constraints for developers. Some constraints arise from the hardware, software and interaction features of mobile platforms, while others stem from the use of wireless networks that are more dynamic, less reliable and performing than wired networks. In either case, software engineering processes have to tackle these constraints in order to provide mobility-enabled systems and applications. Based on first-hand experience in the field, this paper provides a framework to categorise these constraints and their severity, and describes some of the strategies that can be used to cope with them, with an emphasis in those relevant to middleware design.

This paper presents Phoenix, a routing protocol for content-based publish/subscribe systems that supports seamless client mobility. Our protocol is based on the Simple Routing approach and requires brokers to maintain a global vision of the system with regards to its subscribers. As a consequence, Phoenix provides optimal event routing in both static and mobile client scenarios, and avoids mobility-related flooding of messages. Although the choice of Simple Routing sacrifices maximum scalability due to global propagation of subscriber interest, we show that several optimizations significantly minimize the loss of performance. In fact, when optimized, the performance of the Phoenix routing algorithm is suitable for the scenarios we envision: hybrid wireless networks for sensor/actuator deployments. Additionally, we note that our protocol can be extended to provide brokers with the ability to enforce client migrations for load-balancing purposes.

We present a modular redesign of TrustedPals, a smart card-based security framework for solving Secure Multiparty Computation (SMC). Originally, TrustedPals assumed a synchronous network setting and allowed to reduce SMC to the problem of fault-tolerant consensus among smart cards. We explore how to make TrustedPals applicable in environments with less synchrony and show how it can be used to solve asynchronous SMC. Within the redesign we investigate the problem of solving consensus in a general omission failure model augmented with failure detectors. To this end, we give novel definitions of both consensus and the class \diamond {\cal P} of failure detectors in the omission model, which we call \diamond {\cal P}({ om}), and show how to implement \diamond {\cal P}({ om}) and have consensus in such a system with very weak synchrony assumptions. The integration of failure detection and consensus into the TrustedPals framework uses tools from privacy enhancing techniques such as message padding and dummy traffic.

This paper presents an Adaptive Predictive Control strategy based on Neural Networks for nonlinear systems. In order to train the Neural Network controller, an identification of the system is carried out by the Neural Network Identifier. This second Neural Network provides the training terms related to the nonlinear system dynamics. In this way it is possible to train the Neural Network controller online. The simulation results show a correct online adaptation of the NN controller and the validity of the proposed control strategy.

No abstract available.

This work addresses the leader election problem in distributed systems where processes can crash and recover. More precisely, it focuses on implementing the Omega failure detector class, which provides a leader election functionality, in the crash-recovery failure model. The concepts of quiescence and near-quiescence for an algorithm implementing Omega are defined. Depending on the use or not of stable storage, the property satisfied by unstable processes, i.e., those that crash and recover infinitely often, varies. Two algorithms implementing Omega are presented. In the first algorithm, which is quiescent and uses stable storage, eventually and permanently unstable processes agree on the leader with correct processes. In the second algorithm, which is near-quiescent and does not use stable storage, unstable processes agree on the leader with correct processes after receiving a first message from a correct process. An adaptation of this second algorithm that avoids the disagreement of unstable processes by providing instability awareness is also presented.

Unreliable failure detectors are mechanisms providing information about process failures. This paper addresses the implementation of the Eventually Perfect failure detector class, denoted P, in the crash-recovery failure model. The approach followed is to transform existing implementations of the Omega failure detector, which provides an eventual leader election functionality, into P. In a system with the minimal requirements to implement P, we first propose a generic transformation algorithm that uses the underlying Omega as a black box. Then, we enhance the algorithm to provide a common set of k correct processes. The algorithms do not require the membership of the system to be known a priori.

This paper presents an evaluation of several communication-optimal algorithms implementing the diamP class of failure detectors. The first algorithm is based on a reliable broadcast primitive, involving a quadratic number of messages to manage a suspicion. The second algorithm uses exclusively one-to-one communication, involving a linear number of messages to manage a suspicion, but with a higher latency to propagate the suspicion to the rest of processes. A third algorithm reduces this latency using an additional one-to-all communication mechanism. We evaluate the quality of service provided by these algorithms, in terms of the capability of the failure detector to provide right answers and the reaction time after a failure.

No abstract available.

Unreliable failure detectors provide information about process failures. A particular failure detector called Omega has been shown to be the weakest for solving consensus with a majority of correct processes. This work addresses the implementation of Omega in the crash-recovery failure model. Firstly, the definition of Omega is adapted to that model, assuming that processes do not use stable storage. After that, an algorithm implementing Omega under some weak assumptions on communication reliability and synchrony is proposed.

Unreliable failure detectors are mechanisms providing information about process failures that allow solving several problems in asynchronous systems, e.g., Consensus. A particular class of failure detectors, Omega, provides an eventual leader election functionality. This paper addresses the implementation of Omega in the crash-recovery failure model. Recently we have proposed an algorithm assuming that eventually the correct process with the smallest identifier and minimum incarnation number can communicate timely with the rest of processes. Here we propose two Omega algorithms which assume only that processes are reachable from some correct process, independently of its identifier and incarnation number. The first one requires the membership to be known a priori, while the second one relaxes this assumption too

This paper presents an evaluation of two families of ring-based algorithms implementing the eventually perfect failure detector class (diamPscr). The evaluation is based on two kinds of performance parameters: communication efficiency, which refers to the number of links that carry messages forever, and quality of service, which includes the capability of the failure detector for providing right answers as well as reaction and initial stabilization times. The first family of algorithms includes several communication-efficient implementations of diamPscr introduced in a previous work. For the second family, introduced in this work, we start from the design of a non communication-efficient diamQscr algorithm, and then we apply a transformation to obtain a diamPscr algorithm, including some optimizations to improve the quality of service

Ubiquitous (or pervasive) systems are characterized by component distribution and dynamic behavior. In a ubiquitous environment, such as a future automated home (also called a domotic environment), user devices explore the environment to discover resources and services to control. This paper analyzes architectures for ubiquitous systems based on the structure of the environment and the way discovery mechanisms (such as Jini and UPnP) operate. As a result, a framework to classify the architectures is provided. As an example, a UPnP-based prototype for a domotic environment is presented. We use standard devices, such as PDAs and cell phones, to allow users to access and control virtual resources. The system provides user management capabilities, persistence, and standard interfaces, while preserving full UPnP compatibility. The prototype can be easily transferred to future realistic domotic installations.

Unreliable failure detectors were proposed by Chandra and Toueg as mechanisms that provide information about process failures. Chandra and Toueg defined eight classes of failure detectors, depending on how accurate this information is, and presented an algorithm implementing a failure detector of one of these classes in a partially synchronous system. This algorithm is based on all-to-all communication and periodically exchanges a number of messages that is quadratic on the number of processes. We study the implementability of different classes of failure detectors in several models of partial synchrony. We first show that no failure detector with perpetual accuracy (namely, P, Q, S, and W) can be implemented in these models in systems with even a single failure. We also show that, in these models of partial synchrony, it is necessary a majority of correct processes to implement a failure detector of the class /spl theta/ proposed by Aguilera et al. Then, we present a family of distributed algorithms that implement the four classes of unreliable failure detectors with eventual accuracy (namely, /spl diams/P, /spl diams/Q, /spl diams/S, and /spl diams/W). Our algorithms are based on a logical ring arrangement of the processes, which defines the monitoring and failure information propagation pattern. The resulting algorithms periodically exchange at most a linear number of messages.

No abstract available.

The concept of unreliable failure detecto was introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. This mechanism has been used to solve different problems in async hronous systems, in particular the Consensus problem.

Unreliable failure detectors were introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. They showed how unreliable failure detectors can be used to solve the Consensus problem in asynchronous systems. They also showed in [1] that one of the classes of failure detectors they defined, namely Eventually Strong (⋄S), is the weakest class allowing to solve Consensus1.

The concept of unreliable failure detector was introduced by T.D. Chandra and S. Toueg (1996) as a mechanism that provides information about process failures. Depending on the properties which the failure detectors guarantee, they proposed a taxonomy of failure detectors. It has been shown that one of the classes of this taxonomy, namely Eventually Strong (/spl nabla/S), is the weakest class allowing a solution of the Consensus problem. The authors present a new algorithm implementing /spl nabla/S. Our algorithm guarantees that eventually all the correct processes agree on a common correct process. This property trivially allows us to provide the accuracy and completeness properties required by /spl nabla/S. We show then that our algorithm is better than any other proposed implementation of /spl nabla/S in terms of the number of messages and the total amount of information periodically sent. In particular, previous algorithms require periodic exchange of at least a quadratic amount of information, while ours only requires O(n log n) (where n is the number of processes). However, we also propose a new measure to evaluate the efficiency of this kind of algorithm, the eventual monitoring degree, which does not rely on a periodic behavior and expresses the degree of processing required by the algorithms better. We show that the runs of our algorithm have optimal eventual monitoring degree.

Non-blocking atomic commitment protocols enable a decision (commit or abort) to be reached at every correct participant, despite the failure of others. The cost for non-blocking implies however (1) a high number of messages and communication steps required to reach commit, and (2) a complicated termination protocol needed in the case of failure suspicions. In this paper, we present a non-blocking protocol, called MDSPC (Modular and Decentralized Three Phase Commit), which enables to trade resiliency against efficiency. As conveyed by our performance measures, MDSPC is faster than existing non-blocking protocols, and in the case of a broadcast network and a reasonable resiliency rate (e.g. 2 or 3) is almost as efficient as the classical (blocking) 2PC. The termination protocol of MDSPC is encapsulated inside a majority consensus protocol. This modularity leads to a simple structure of MDSPC and enables a precise characterization of its liveness in an asynchronous system with an unreliable failure detector.

In a transactional system, an atomic commitment protocol ensures that for any transaction, all data manager processes agree on the same outcome (commit or abort). A non-blocking atomic commitment protocol enables an outcome to be decided at every correct process despite the failure of others. In this paper we apply, for the first time, the fundamental result of T. Chandra and S. Toueg (1991) on solving the abstract consensus problem, to non-blocking atomic commitment. More precisely, we present a non-blocking atomic commitment protocol in an asynchronous system augmented with an unreliable failure detector that can make an infinity of false failure suspicions. If no process is suspected to have failed, then our protocol is similar to a three phase commit protocol. In the case where processes are suspected, our protocol does not require any additional termination protocol: failure scenarios are handled within our regular protocol and are thus much simpler to manage.