Summary
We establish a new worst-case upper bound on the Membership problem: We present a simple algorithm that is able to always achieve Agreement on Views within a single message latency after the final network events leading to stability of the group become known to the membership servers. In contrast, all of the existing membership algorithms may require two or more rounds of message exchanges. Our algorithm demonstrates that the Membership problem can be solved simpler and more efficiently than previously believed. By itself, the algorithm may produce disagreement (that is, inconsistent, transient views) prior to the "final" view. Even though this is allowed by the problem specification, such views may create overhead at the application level, and are therefore undesirable. We propose a new approach for designing group membership services in which our algorithm for reaching Agreement on Views is combined with a filter-like mechanism for reducing disagreements. This approach can use the mechanisms of existing algorithms, yielding the same multi-round performance as theirs. However, the power of this approach is in being able to use other mechanisms. These can be tailored to the specifics of the deployment environments and to the desired combinations of the speed of agreement vs. the amount of preceding disagreement. We describe one mechanism that keeps the combined performance to within a single-round, and sketch another two.