  We present the design and evaluation of Rapid, a distributed membership
service. At Rapid's core is a scheme for multi-process cut detection (CD) that
revolves around two key insights: (i) it suspects a failure of a process only
after alerts arrive from multiple sources, and (ii) when a group of processes
experience problems, it detects failures of the entire group, rather than
conclude about each process individually. Implementing these insights
translates into a simple membership algorithm with low communication overhead.
  We present evidence that our strategy suffices to drive unanimous detection
almost-everywhere, even when complex network conditions arise, such as one-way
reachability problems, firewall misconfigurations, and high packet loss.
Furthermore, we present both empirical evidence and analyses that proves that
the almost-everywhere detection happens with high probability. To complete the
design, Rapid contains a leaderless consensus protocol that converts
multi-process cut detections into a view-change decision. The resulting
membership service works both in fully decentralized as well as logically
centralized modes.
  We present an evaluation of Rapid in moderately scalable cloud settings.
Rapid bootstraps 2000 node clusters 2-5.8x faster than prevailing tools such as
Memberlist and ZooKeeper, remains stable in face of complex failure scenarios,
and provides strong consistency guarantees. It is easy to integrate Rapid into
existing distributed applications, of which we demonstrate two.
