Skip to content

Peer Selection Strategy

Jump to bottom
João Carvalho edited this page Feb 10, 2019 · 9 revisions

Requirements

Propagation

  • in a network with N=10k participants: messages of size S=16kbytes must be received by all nodes in the network in less than Tmax=8 seconds and should be received in less than Tavg=6 seconds. Assuming average net upload bandwidth B=100kbytes/s the diameter (worst case) of the network must be no more than Dmax=7, the average shortest path length should be less than SPLmax=4.5.

Indicators:

  • closeness centrality at a node is 1/average distance to all other nodes (higher is better).
  • load centrality of a node is the fraction of all shortest paths that pass through that node (lower is better)
  • average shortest path length of a graph is the average of all shortest paths between any combination of nodes (shorter is better)
  • rsd_* the relative standard deviation of above values is an indicator of the well-formedness (lower is better)
  • diameter of a graph is the longest shortest path (worst case) (shorter is better, should be log(n))
  • node connectivity of a graph is the minimum number of node that disconnect the graph (network split) when deleted (higher is better)

Robustness

  • in a network with N=10k participants: the network must not split with a probability ofP=0.95 if a fraction F=1/3 of the nodes go down (due to partial network outages or attacks). Node connectivity must at least be NC=4.

Sybil Attacks

  • in a network with N participants: the network must not fail if a fraction F of nodes with an average elapsed time TEavg since their first appearance, conspire to attack the network.

Simulation results

The results of the simulation of various strategies suggest, that the below peer selection strategy seems to be sufficient regarding above propagation and robustness requirements:

  • calculate N random addresses
  • looks up the endpoints of nodes with minimized xor distance to the addresses (i.e. one recursive find_node discovery task for each peer)
  • connect the endpoints

The number of peers per node shapes the network properties; higher num_peer settings of a node increase the number of uploads, thus limiting throughput. Low num_peer settings reduce the edges in the network graph, leading to higher avg shortest paths lengths, higher diameter, lower node connectivity and closeness centrality. The results gave avg_peer_count=10.4 as the optimum (within the specified bandwidth, latency, etc.). It allows to propagate messages of size S=16Kbytes to all nodes on average in Tavg=5.4s and has Tmax=7.6s as the worst case. Node connectivity is NC=4. Nodes with higher bandwidth can connect to a higher number of peers as long as num_peers < bandwidth * (avg_propagation_time / avg_shortest_path_length - latency) / message_size

Sybil attack scenarios were not part of the simulation.

Clone this wiki locally