Selected sections of this report will be published in the Proceedings of the International Parallel and Distributed Processing Symposium, Rome, Italy, May 2009.
We prove that, unlike DME, WME is solvable in a partially synchronous model, i.e. a system where the bounds on communication latency and on relative process speeds are not known in advance, or are known but only hold after an unknown time.
Finally we demonstrate that diamond P is the weakest failure detector for solving WME, and present an algorithm that solves WME using diamond P with a majority of correct processes.
Also available extended report (pdf).