Skip to Main content Skip to Navigation
Reports

Visiting Gafni's Reduction Land: from the BG Simulation to the Extended BG Simulation

Damien Imbs 1 Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : The Borowsky-Gafni (BG) simulation algorithm is a powerful tool that allows a set of t + 1 asynchronous sequential processes to wait-free simulate (i.e., despite the crash of up to t of them) a large number n of processes under the assumption that at most t of these processes fail (i.e., the simulated algorithm is assumed to be t-resilient). The BG simulation has been used to prove solvability and unsolvability results for crash-prone asynchronous shared memory systems. In its initial form, the BG simulation applies only to colorless decision tasks, i.e., tasks in which nothing prevents processes to decide the same value (e.g., consensus or k-set agreement tasks). Said in another way, it does not apply to decision problems such as renaming where no two processes are allowed to decide the same new name. Very recently (STOC 2009), Eli Gafni has presented an extended BG simulation algorithm (GeBG) that generalizes the basic BG algorithm by extending it to “colored” decision tasks such as renaming. His algorithm is based on a sequence of sub-protocols where a sub-protocol is either the base agreement protocol that is at the core of BG simulation, or a commit-adopt protocol. This paper presents the core of an extended BG simulation algorithm that is particularly simple. This algorithm is based on two underlying objects: the base agreement object used in the BG simulation (as does GeBG), and (differently from GeBG) a new simple object that we call arbiter. As in GeBG, while each of the n simulated processes is simulated by each simulator, each of the first t + 1 simulated processes is associated with a predetermined simulator that we called its “owner”. The arbiter object is used to ensure that the permanent blocking (crash) of any of these t + 1 simulated processes can only be due to the crash of its owner simulator. After being presented in a modular way, the proposed extended BG simulation algorithm is proved correct.
Document type :
Reports
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00389682
Contributor : Anne Jaigu <>
Submitted on : Friday, May 29, 2009 - 11:54:40 AM
Last modification on : Tuesday, June 15, 2021 - 4:14:48 PM
Long-term archiving on: : Friday, June 11, 2010 - 12:01:57 AM

File

PI-1931.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00389682, version 1

Citation

Damien Imbs, Michel Raynal. Visiting Gafni's Reduction Land: from the BG Simulation to the Extended BG Simulation. [Research Report] PI 1931, 2009, pp.12. ⟨inria-00389682⟩

Share

Metrics

Record views

570

Files downloads

516