Assume you have a graph/network N;

Boundary Conditions:

  • each vertex/node $n \in N$ can support a maximum number of $e_{max}$ connections

  • Nodes can join and leave the graph.

  • Each node $n$ has an address $0 < a < 1$, e.g. $v_{0.123987144}$. The addresses are roughly uniformly distributed.

  • Each node can destroy any connection between itself and a neighbor.

  • Each vertex can build a connection between itself and any other node in the network.

  • No node can ever know $|N|$ exactly.

  • Each node knows only the addresses of the vertices it is connected to.

  • Blind requests possible: When building a new edge, a node has to send a request with a specific address to one of its neighbors. That neighbor can choose to relay the request to one of its neighbors, and so on. Alternatively, any recipient node can choose to accept the request and "impersonate" the goal vertex.

Initial Conditions:

The network is fully connected: $|N|<e_{max}$, but growing rapidly.


  • Minimize degrees of separation

  • make paths predictable, given two addresses (no pathfinding required/heuristics are perfect)

  • Prevent feedback loops and make it "stable"

  • Prevent mitosis (graph separation)

Strategies needed

  1. What address requests should a vertex send into the graph, and when?

  2. Which edges should a vertex drop, and when?

  3. When should a vertex honor a request?

  • 2
    $\begingroup$ This is a rather open-ended question... $\endgroup$ Sep 15 '17 at 8:35
  • 1
    $\begingroup$ You might want to google for "compact routing schemes". $\endgroup$
    – adrianN
    Sep 15 '17 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.