28622 articles – 22133 Notices  [english version]

inria-00583155, version 1

The weakest failure detector to implement a register in asynchronous systems with hybrid communication

Damien Imbs () a1, Michel Raynal () a1

N° PI-1972 (2011)

Résumé : This paper introduces an asynchronous crash-prone hybrid system model. The system is hybrid in the way the processes can communicate. On the one side, a process can send messages to any other process. On another side, the processes are partitioned into clusters and each cluster has its own read/write shared memory. In addition to the model, a main contribution of the paper concerns the implementation of an atomic register in this system model. More precisely, a new failure detector (denoted MΣ) is introduced and it is shown that, when considering the information on failures needed to implement a register, this failure detector is the weakest. To that end, the paper presents an MΣ-based algorithm that builds a register in the considered hybrid system model and shows that it is possible to extract MΣ from any failure detector-based algorithm that implements a register in this model. The paper also (a) shows that MΣ is strictly weaker than Σ (which is the weakest failure detector to implement a register in a classical message-passing system) and (b) presents a necessary and sufficient condition to implement MΣ in a hybrid communication system.

  • a –  Université de Rennes I
  • 1 :  ASAP (INRIA - IRISA)
  • CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
  • Domaine : Informatique/Autre
  • Mots-clés : Asynchronous message-passing system – Atomic register – Distributed algorithm – Failure detector – Fault-tolerance – Hybrid communication – Necessity proof – Process crash – Shared memory system – Weakest failure detector.
  • Référence interne : PI-1972
 
  • inria-00583155, version 1
  • oai:hal.inria.fr:inria-00583155
  • Contributeur : 
  • Soumis le : Mardi 5 Avril 2011, 08:54:19
  • Dernière modification le : Mardi 5 Avril 2011, 10:36:15