  The Chord distributed hash table (DHT) is well-known and frequently used to
implement peer-to-peer systems. Chord peers find other peers, and access their
data, through a ring-shaped pointer structure in a large identifier space.
Despite claims of proven correctness, i.e., eventual reachability, previous
work has shown that the Chord ring-maintenance protocol is not correct under
its original operating assumptions. It has not, however, discovered whether
Chord could be made correct with reasonable operating assumptions. The
contribution of this paper is to provide the first specification of correct
operations and initialization for Chord, an inductive invariant that is
necessary and sufficient to support a proof of correctness, and the proof
itself. Most of the proof is carried out by automated analysis of an Alloy
model. The inductive invariant reflects the fact that a Chord network must have
a minimum ring size (the minimum being the length of successor lists plus one)
to be correct. The invariant relies on an assumption that there is a stable
base, of the minimum size, of permanent ring members. Because a stable base has
only a few members and a Chord network can have millions, we learn that the
obstacles to provable correctness are anomalies in small networks, and that a
stable base need not be maintained once a Chord network grows large.
