This paper provides algorithms to maintain a ring-structure for structured peer-to-peer systems. The algorithms guarantee consistent lookup results in the presence of joins and leaves, regardless of at which node the lookup is initiated. Every join and leave event appears as if it happened atomically, thus guaranteeing that lookup results will be the same as if no joins or leaves took place. The ring maintenance algorithms guarantee that no routing failures occur as nodes are joining and leaving. We also show that lookup consistency is impossible to provide given failure detector, and show how the algorithms can be extended to handle failures. The correctness of all the provided algorithms is proven. Previous approaches to this problem either assume a fault-free environment, or have no proof of correctness.