8 Decentralized overlay networks I

In the next two sections we present overlay networks that are completely decentralized, i.e., they do not depend on a supervisor. We assume that, in principle, every peer has the right to initiate the integration of new peers into the system and that every peer knows at least one peer currently in the system so that publicly available entry points such as a supervisor are not necessary any more. In this section, we will focus on overlay networks that are based on the continuous-discrete approach [5], and in the next section overlay networks are presented that are based on so-called skip graphs [2]. Each each section, we will first assume that all peers are reliable and honest, and then we show how to remove this assumption. 8.1 Overlay networks for reliable, honest peers Recall the hierarchical decomposition approach in Section 7. Our basic approach for the decentralized case is that each time a new peer p enters the system, a random label ℓ(p) ∈ {0, 1} ∗ is generated for it, and this will be used to assign it to some place in the decomposition tree so that the following invariant is maintained (which only differs from the corresponding invariant in Section 7 by the missing item 3, which demands that peers are located at close-by levels). Invariant 8.