Soft real-time analysis of asynchronous agreement algorithms using Petri nets

A distributed algorithm comprises a collection of sequential-code entities, which are spread over different computers connected to a network. The process of designing a distributed algorithm is influenced by the assumptions we make on the computational environment. The model which makes no assumptions (and therefore can fit any real distributed system) is the asynchronous system model. In the asynchronous model there is no bound on message delays, clock drift or the time needed by a process to execute a step. The advantage of using the asynchronous model is that any algorithm designed under its assumptions preserves its correctness (safety) in any other system model. It has been argued that asynchronous algorithms cannot be used for time critical applications. One of the goals of this thesis is to clarify this point, by proving that designing algorithms under the asynchronous system model does not lead to loss of efficiency. The performance of distributed algorithms may be roughly approximated in terms of the number of messages exchanged during the execution or the number of communication steps, but the most precise performance metric is the termination time (i.e., the time needed for the algorithm to finish). The termination time of a distributed algorithm cannot be precisely measured if computation begins and ends on different processors because the clocks are not synchronized. Another difficulty with the performance measures approach is that results are usually biased by unpredictable network and stations loads, or by scheduling delays, not related to the studied algorithm. The approach taken in this thesis for evaluating the performance of distributed algorithms is based on modelling and simulation. One of the main difficulties and the interest of performance modelling is that results do not always conform to intuition. When an algorithm reaches a given complexity, it is difficult to predict the impact of modifying the input parameters on the termination time of the algorithm. Analytical methods can be applied successfully if the interactions and the interdependencies between the software layers of the algorithm under investigation are not too complex or can be simplified adequately without falsifying relevant system's characteristics. Discrete event simulation covers especially those cases which cannot be tackled by analytical methods. By simulation it is possible to evaluate the termination time of an algorithm with pretty good accuracy. The main purpose of this thesis is to provide a flexible framework for studying the performance of asynchronous distributed algorithms. Several important asynchronous algorithms are con- sidered in the thesis, in order to show the applicability and the interest of our framework. We consider algorithms related to fault-tolerance. Providing fault-tolerance in asynchronous distributed systems is closely related to solving agreement problems. All the agreement problems are related to the consensus problem, and agreement protocols can be built using a generic consensus service. This is the reason why we have focused on studying the behaviour and the performance of a consensus algorithm proposed by Chandra and Toueg. Simulation is used to study the behaviour of the algorithm under different input conditions (with or without crash failure) and to choose optimum values for the system parameters (time-outs). We show that there is an inevitable trade-off to make between obtaining (1) fast reaction to process crash, and (2) good performance in runs without crashes. Moreover, we provide the statistical guarantee that consensus will finish before a certain time with a given probability. This result can be used in soft real-time systems that can tolerate infrequent timing failures. The second class of algorithms studied within our framework are replication protocols. These are high-level protocols, built on top of the consensus algorithm. To achieve fault-tolerance in systems subject to failures, services are replicated on different sites and specific communication protocols are used to maintain consistency between replicas. Two replication strategies are usually considered: the primary-backup replication technique and the active replication technique. We compare the performance of the two replication techniques in two scenarios: failure free run and the worst case with the crash of one replica.

Towards reliable communication and agreement in mobile ad-hoc networks

David Cavin

During the last decade, the number of wireless devices like digital organizers, mobile phones and laptop computers has drastically increased. At the same time, several technologies, like Bluetooth, GPRS, or WiFi have become mature and offer a high-performance wireless infrastructure to mobile users. However, there exist still many non-equipped areas where no infrastructure is available. For example, during emergency operations, rescuers may want to deploy temporarily an autonomous (or ad-hoc) network. Under these settings, mobile devices (or nodes) operate in a self-organized manner and can only communicate with their immediate wireless neighbors. To send a packet to a remote destination, a node relies on the routing capabilities of the other nodes. In a mobile ad-hoc network (MANET), problems are inherently more complicated to solve than in a regular wired network because of the dynamic topology and the absence of an underlying communication infrastructure. Many algorithms and protocols have been proposed for mobile ad-hoc networks, but very little has been done to evaluate these solutions in real environments. In most cases, algorithms are evaluated by simulation. Such a solution leads however to incorrect conclusions, as we show in the thesis. In order to avoid the shortcomings of simulations, an adequate software framework must be available, in order to ease the development and the deployment of applications or algorithms. We have developed FRANC, a lightweight Java framework dedicated to the implementation of real ad-hoc applications. FRANC is composed of an extensible library of building blocks that can be composed to build more complex applications. The thesis is not limited to practical contributions. We have also addressed two important problems that are at the root of many other distributed computing algorithms. Although extensively studied in wired networks, this research domain is however still in its early stages in MANETs. We first propose a simple broadcast protocol that disseminates efficiently and reliably a message in a one dimensional graph like a car highway. Then, we study the consensus problem and identify the necessary and sufficient conditions for solving it in self-organized networks when the participants are unknown (in the absence of crashes). Finally, we discuss a pragmatic solution to consensus with crashes based on weak ordering oracles. More specifically, we propose an implementation of these oracles and present results collected in a real small-scale wireless testbed.

EPFL2006

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Dan Alistarh, Seth Gilbert, Rachid Guerraoui

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. The complexity of set agreement in synchronous networks has also been a significant research challenge. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. In this paper, we analyze the complexity of set agreement in such a “partially synchronous” setting, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. We also present an asymptotically matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony. By relating environments with differing degrees of synchrony, our simulation technique is of independent interest. In particular, it allows us to obtain a new lower bound on the complexity of early deciding k-set agreement complementary to that of [12], and to re-derive the combinatorial topology lower bound of [13] in an algorithmic way.

Springer2009

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Dan Alistarh, Seth Gilbert, Rachid Guerraoui

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. In synchronous networks, too, the complexity of set agreement has been a significant research challenge that has now been resolved. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. Nothing specific is known about the complexity of set agreement in such a ``partially synchronous'' setting. In this paper, we address this challenge, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in a fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this simulation technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. Specifically, we show that every set agreement protocol requires at least

\floor{t}{k} + 2

synchronous rounds to decide. We present an (asymptotically) matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony. From these two results, we derive the size of the minimal window of synchrony needed to solve set agreement. By relating synchronous, asynchronous and partially synchronous environments, our simulation technique is of independent interest. In particular, it allows us to obtain a new lower bound on the complexity of early deciding

k

-set agreement complementary to that of~\cite{Gafni2005}, and to re-derive the combinatorial topology lower bound of~\cite{Herlihy2006} in an algorithmic way.

2012

Towards reliable communication and agreement in mobile ad-hoc networks

David Cavin

EPFL2006

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Dan Alistarh, Seth Gilbert, Rachid Guerraoui

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. In synchronous networks, too, the complexity of set agreement has been a significant research challenge that has now been resolved. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. Nothing specific is known about the complexity of set agreement in such a ``partially synchronous'' setting. In this paper, we address this challenge, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in a fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this simulation technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. Specifically, we show that every set agreement protocol requires at least

\floor{t}{k} + 2

k

-set agreement complementary to that of~\cite{Gafni2005}, and to re-derive the combinatorial topology lower bound of~\cite{Herlihy2006} in an algorithmic way.

2012