[Back]

M. Biely, J. Widder:
"Optimal Message-Driven Implementations of Omega with Mute Processes";
Talk: 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Dallas; 2006-11-17 - 2006-11-19; in: "Stabilization, Safety, and Security of Distributed Systems", (2006), 110 - 121.

We establish a lower bound on the number of processes required to implement Omega---the weakest failure detector that allows to solve consensus in asynchronous systems---with message-driven algorithms. This lower bound is strictly greater than the lower bound for time-driven algorithms. We then present two algorithms that actually implement Omega which show that the established lower bound is tight. Additionally our algorithms are efficient in the sense that not all processes have to send messages which is an improvement to previous message-driven failure detector implementations.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC06586928