Packet Efficient Implementation of the Omega Failure Detector - Sorbonne Université Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

Packet Efficient Implementation of the Omega Failure Detector

Résumé

We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an implementation of the Omega Failure Detector under such an assumption. To motivate the study, we prove that the existence and sustainability of a leader is exponentially more probable in a multi-hop Omega implementation than in a single-hop one. An implementation is: \emph{message efficient} if all but finitely many messages are sent by a single process; \emph{packet efficient} if the number of packets used to transmit a message in all but finitely many messages is linear w.r.t the number of processes, packets of different messages may potentially use different channels, thus the number of used channels is not limited; \emph{super packet efficient} if the number of channels used by packets to transmit all but finitely many messages is linear. We present the following results for deterministic algorithms. If reliability and timeliness of one message does not correlate with another, i.e., there are no channel reliability properties, then a packet efficient implementation of Omega is impossible. If eventually timely and fair-lossy channels are considered, we establish necessary and sufficient conditions for the existence of a message and packet efficient implementation of Omega. We also prove that the eventuality of timeliness of channels makes a super packet efficient implementation of Omega impossible. On the constructive side, we present and prove correct a deterministic packet efficient implementation of Omega that matches the necessary conditions we established.
Fichier principal
Vignette du fichier
omega.tr.pdf (134.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01153111 , version 1 (19-05-2015)
hal-01153111 , version 2 (12-02-2016)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Quentin Bramas, Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil. Packet Efficient Implementation of the Omega Failure Detector. [Research Report] UPMC Université Paris VI; Kent State University. 2015. ⟨hal-01153111v2⟩
281 Consultations
204 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More