Overlay networks that aim to share information are complex due to numerous factors including scale, decentralization, dynamism, and failures. Deploying, operating and maintaining such overlays can be not only very difficult, but also very costly. In this paper we show how a dynamic overlay can be built and maintained in a cost efficient manner while achieving strong locality properties in a decentralized, dynamic, and faulty environment. In our approach there is no central entity that configures, organizes, and repairs the system. To the contrary, we show that if each peer performs local cost efficient operations then by combining the joint effort of all peers the network manages, configures, and repairs itself.