Packet Efficient Implementation of the Omega Failure Detector - Sorbonne Université Access content directly
Journal Articles Theory of Computing Systems Year : 2019

Packet Efficient Implementation of the Omega Failure Detector

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. To motivate the study, 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 it is message efficient and the number of packets used to transmit all but finitely many messages is proportional to the number of processes in the system; super packet efficient if it is message efficient and the number of channels used to transmit all but finitely many packets is proportional to the number of processes in the system. We prove that a super packet efficient implementation of Omega is impossible. We establish necessary conditions for the existence of a packet efficient implementation of Omega and present an algorithm that implements Omega under these conditions.

Dates and versions

hal-02084539 , version 1 (29-03-2019)

Identifiers

Cite

Quentin Bramas, Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil. Packet Efficient Implementation of the Omega Failure Detector. Theory of Computing Systems, 2019, 63 (2), pp.237-260. ⟨10.1007/s00224-018-9856-3⟩. ⟨hal-02084539⟩
51 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More