  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
eventuallytimely 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 efficientimplementation 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.
