[mostly by Andrew Clausen, with some discussion with Peter Eckersley] John Casey kindly pointed out this link, which has some much better solutions to the problem: http://zgp.org/pipermail/p2p-hackers/2004-December/002283.html * single server for each segment of arc is bad: - DoS attack - slow (although, other solutions are available) * reminder of why we have a circle: - index servers don't want to index the entire network (too much storage) - too much work to keep all index servers in sync - "single point of failure" removed * overlapping servers: - each index server can decide which arc they want to serve. They may shrink if they want to reduce bandwidth or storage they are consuming in order to provide the service. - setting the arc is the fundamental operation: * entering == changing from NULL to something * leaving == changing from something to NULL - setting the arc: * growing: tell some servers (choose ones that trust you) that you are now serving on a range, and also fetch all indexes in that range (that you trust, anyway) * shrinking: off-load (i.e. make sure someone else can handle) all of the pointers that are now out-of-range. Servers will learn of your disappearance when you NAQ or timeout their requests. - routing: (1) pick the server you know that is above your trust threshold that is closest to the thing you want, and send a request (2) if the response is in range, you're done. If not, repeat :) Note: if you didn't find what you were looking for, try lowering trust threshold - issues: * subjective vs. objective models: - you allow collisions on keys, and servers choose a subset of pointers for each key (based on trust) Thus, the system is subjective, depending on which index servers you trust - as above, except you only "don't trust" a server/pointer if you believe it to be 'fake' (as opposed to irrelevant). The common case, therefore, is "to trust". * good algorithm needed for keeping in sync. Similar problem to backbone routers keeping distance vectors in sync. (Minimum spanning tree "send to all neighbours in tree except the one we received the diff from")