Packet Efficient Implementation of the Omega Failure Detector

摘要

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.