To appear in ACM Transactions on Computer Systems (TOCS), August 2002.
Previous version: Technical Memorandum MIT-LCS-TM-593a Massachusetts Institute of Technology, Laboratory for Computer Science; also Technical Report CS99-623a University of California, San Diego, Department of Computer Science and Engineering, June 1999, revised September 2000.
Preliminary version appeared in the 20th International Conference on Distributed Computing Systems (ICDCS), pages 356-365, April 2000.
In addition to specifying the properties of the algorithm and proving that this specification is met, we provide empirical results of an implementation of Moshe running over the Internet. The empirical results justify the assumptions made by our design and exhibit good performance. In particular, Moshe terminates within a single communication round over 98% of the time. The experimental results also lead to interesting observations regarding the performance of membership algorithms over the Internet.