Packet Efficient Implementation of the Omega Failure Detector

Quentin Bramas 1 Dianne Foreback 2, 3 Mikhail Nesterenko 2, 3 Sébastien Tixeuil 1, 4, 5
1 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
2 Kent State University
3 Department of computer science
4 IUF - Institut Universitaire de France
5 LINCS - Laboratory of Information, Network and Communication Sciences
Abstract : We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an Omega Failure Detector implementation. We prove the existence and sustainability of a leader is exponentially more probable in a multi-hop than in a single-hop implementation. An implementation is: message efficient if all but finitely many messages are sent by a single process; 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; super packet efficient if the number of channels used by packets to transmit all but finitely many messages is linear. Our results for deterministic algorithms implementing Omega follow. If reliability and timeliness of messages do not correlate, packet efficiency is impossible. We establish necessary and sufficient conditions for the existence of message and packet efficiency and prove correct our deterministic implementation. We prove the eventuality of channels’ timeliness makes super packet efficiency impossible.
Type de document :
Communication dans un congrès
International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016), Nov 2016, Lyon, France. Springer, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016), 10083, pp.70-87, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-49259-9_6〉
Liste complète des métadonnées
https://hal.sorbonne-universite.fr/hal-01491817
Contributeur : Sébastien Tixeuil <>
Soumis le : vendredi 17 mars 2017 - 14:08:48
Dernière modification le : mardi 4 décembre 2018 - 01:22:42

Identifiants

Collections

UPMC | INSTITUT-TELECOM | LIP6 | INRIA | SORBONNE-UNIVERSITE

Citation

Quentin Bramas, Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil. Packet Efficient Implementation of the Omega Failure Detector. International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016), Nov 2016, Lyon, France. Springer, International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016), 10083, pp.70-87, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-49259-9_6〉. 〈hal-01491817〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

383

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD