We present a framework for overlay network design that combines many advantages of client/server and peer-to-peer networks. Our approach, the supervised peer-to-peer overlay networking (SPON) model, uses a single supervisor node which is assumed to be reliable to organize the remaining participants in the network. The supervisor is far less powerful than a server, in that at any given time it is aware of very few (O(1) or O(log n)) members of the network, and is only involved with node join and leave operations. Furthermore, a multicast group of redundant supervisors can be used in any SPON system to remove the reliability assumption with very little additional cost.
We present a structure based on a forest of binary trees that can guarantee broadcasting in a dynamic network against a limited-power adversary; we also use this structure for provably efficient storage management as part of a monitoring system for intrusion detection or other security applications. We present two structures based on the DeBruijn graph which function as distributed hash tables for nodes of uniform or arbitrary nonuniform load demands.