Project topics and materials
Get Complete Project Material File(s) Now! »
Relating Models via Agreement-Based Simulations
Distributed simulations were introduced to provide a generic way for a model to emulate executions of another model. A classic simulation technique is the universal construction by Herlihy in [Her91]. The idea consists in using the ability of a system to solve consensus to reach agreement on all simulated operations one by one. But most distributed systems cannot solve the consensus task. Hence, managing to produce valid simulated executions while submitted to concurrency is an important feature for widely applicable simulation techniques. In this thesis, we primarily focus on simulation techniques inspired by BG simulation, the classical simulation tool invented by Borowsky and Gafni [BG93a,BGLR01]. Our goal is to design a novel agreement-based simulation using insights from Gafni and Guerraoui [GG09]. We proceed incrementally. We start with a simple BG-like simulation. We then add additional features, one at a time, each time yielding a more rened and powerful simulation. This approach also helps to compare the simulations and to understand the advantages each feature provides. The nal simulation, mixing a exible agreement-based synchronization and a simple round-by-round structure, is widely applicable and yet very simple to use. We start, in Section 3.2, by recalling the principles of BG simulation. In particular, we focus on the safe-agreement protocol which allows synchronizing simulators to avoid potential con icts in simulated operations. It also enables us to dene formally the basic structures and properties followed by the distributed simulations presented in this chapter.
Next, in Section 3.3, we improve the simulation by providing the ability to abort pending simulation steps, which results in a simulation similar to Extended BG simulation introduced by Gafni [Gaf09]. We continue, in Section 3.4, by rening the use of this abort mechanism and proposing a simpler variant of Extended BG simulation. This new simulation has a straightforward round-by-round structure which can be used to easily prove ne properties of the simulated executions. We proceed to the last improvement in Section 3.5, by replacing the safe-agreement protocol with a more exible agreement-based synchronization. This last simulation will be instrumental in comparing models task computability in the next chapter.
Safe Agreement and BG Simulation
We use here a dierent approach than the original BG-simulation technique [BG93a, BGLR01]. We rst provide an explicit simulation of atomic update and snapshot operations that is expected to build a valid AS (atomic snapshot) run, under the condition that the simulation calls respect certain restrictions.
Then we introduce a non-blocking version of the safe-agreement protocol that can be used to ensure agreement on simulated steps. Using these two constructs, we provide the simulation scheme that meets the specied requirement and brie y discuss how it can be applied. We assume in this chapter that an n-process (of n simulators) model intends to simulate an m-process model (of m simulated processes). Moreover, we assume that simulated processes run the full-information protocol, i.e., they start with an update operation using their initial state as a parameter and then alternate between snapshot and update operations, each time using the output of the preceding snapshot operation as a parameter for the update.
Abortable BG Simulation
The main issue with BG simulation is that a simulator crashing while simulating a process step may block the simulation of this process forever. If the task is not colorless, the simulators may have dierent termination conditions. Hence, it may happen that a failed simulator which, based on the current state of the simulation, can already terminate keeps blocking a safe-agreement protocol. But correct simulators may require the output of this blocked simulated process to compute their outputs. Avoiding this possible deadlock is the motivation behind the Extended BG-simulation proposed by Gafni [Gaf09]. The idea is to provide an abort mechanism which takes all processes out of the computation and thus let only correct, non-terminated, processes come back to the simulation. In the original extended BG-simulation, simulators can abort individual simulation steps. For convenience, we present here a dierent approach where the abort mechanism is simulation-wide. An alternative solution was proposed by Imbs and Raynal [IR09]. Their solution consists, intuitively, in improving the properties of the safe-agreement protocols to equip the simulators with relative priorities. Roughly, the user denes for each safe-agreement protocol a priority order among simulators such that a simulator cannot be blocked in a safe-agreement protocol by another simulator with a lower priority. Implementing this extra property is relatively easy, which produces elegant solutions. But we believe that this solution is not as exible as the abort mechanism. Indeed, the priorities are xed and cannot adapt easily to the actual simulation execution. Moreover, as we will show in the following section, the abort mechanism can be automated, and hence, its use becomes invisible from the simulation application perspective.
Table of contents :
1 Introduction
1.1 Distributed Computability in Shared-Memory Models
1.2 Simulations and Iterated Models
1.3 Distributed Computing through Combinatorial Topology
1.4 Contributions
1.5 Organization
1.6 Publications
2 Preliminaries
2.1 Basic Notions
2.2 Shared-Memory Models
2.3 Distributed Tasks
2.4 IIS Model
3 Distributed Simulations
3.1 Relating Models via Agreement-Based Simulations
3.2 Safe Agreement and BG Simulation
3.3 Abortable BG Simulation
3.4 Round-Based Simulation
3.5 Agreement-Based Simulation
4 Agreement Functions
4.1 Denition of Agreement Functions
4.2 Properties and Classication of Agreement Functions
4.3 Fairness through Active Resilience
4.4 Agreement Functions for Adversaries
4.5 Shared-Memory Models and Agreement Functions
5 Combinatorial Topology
5.1 Simplicial Complexes
5.2 Basic Operations
5.3 Subdivisions
5.4 Characterization of the Wait-Free Model
6 Ane Tasks
6.1 Preliminaries
6.2 Ane Tasks for k-Test-and-Set
6.3 Ane Tasks for k-Obstruction-Free Adversaries
6.4 Ane Tasks for Fair Adversaires
6.4.1 Denition of RA
6.4.2 Solving RA in the -Model
6.4.3 From R A to the Fair Adversarial A-Model
7 Stable Storage in Comparison-Based Models
7.1 Motivation
7.2 Model
7.3 Upper Bound: k-Lock-Free SWMR Memory with n + k 1 Registers
7.4 Lower Bound: 2-Obstruction-Free SWMR Memory Requires n + 1 Registers
7.4.1 Proof Overview
7.4.2 The Notion of Confusion
7.4.3 Lower Bound Proof
7.5 Related Problems
7.5.1 Resilient SWMR Memory Implementation.
7.5.2 SWMR Allocation
7.5.3 Anonymous and Adaptive Stable Storage
7.6 Concluding Remarks
8 Conclusion and Open Questions
8.1 Distributed Simulations
8.2 Measuring Models Relative Task Computability
8.3 Ane Tasks
List of Figures
List of Algorithms
Bibliography
