Peer Selection Strategy

Requirements

Propagation

• in a network with N participants: messages of size S must be received by all nodes in the network in less than Tmax seconds and should be received in less than Tavg seconds. Assuming average bandwidth B the diameter (worst case) of the network must be less than Dmax, the average shortest path length should be less than SPLmax. There should be no bottlenecks so, therefore the load centrality of every node must be less than LCmax

Robustness

• in a network with N participants: the network must not split if a fraction F of the node goes down (due to partial network outages or attacks). Node connectivity must be > NC.

Bandwidth

• in a network with N participants, the bandwidth required by each node should be less than BWmax. Therefore the maximum number of peers of each node must be less than Pmax while supporting above requirements.

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.

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)

Solution

?