Question

A number of peer-to-peer systems on the internet are based on overlay networks.
Rather than using the physical internet as the network on which to perform computation, these systems run protocols by which nodes choose collections of virtual “neighbors” so as to define a higher-level graph whose structure may bear little or no relation to the underlying physical network.
Such an overlay network is then used for sharing data and services, and it can be extremely flexible compared with a physical network, which is hard to modify in real time to adapt to changing conditions.
Peer-to-peer networks tend to grow through the arrival of new participants who join by linking into the existing structure.
This growth process has an intrinsic effect on the characteristics of the overall network.
Recently, people have investigated simple abstract models for network growth that might provide insight into the way such processes behave in real networks at a qualitative level.
Here is a simple example of such a model:
The system begins with a single node v1.
Nodes then join one at a time; as each node joins, it executes a protocol whereby it forms a directed link to a single other node chosen uniformly at random from those already in the system.
More concretely, if the system already contains nodes v1, v2, . . . , vk−1 and node vk wishes to join, it randomly selects one of v1, v2, . . . , vk−1 and links to that node.
Suppose we run this process until we have a system consisting of nodes v1, v2, . . . , vn; the random process described above will produce a directed network in which each node other than v1 has exactly one outgoing edge.
On the other hand, a node may have multiple incoming links, or none at all.
The incoming links to a node vj reflect all the other nodes whose access into the system is via vj ; so if vj has many incoming links, this can place a large load on it.
Then to keep the system load-balanced, we would like all nodes to have a roughly comparable number of incoming links.
That is unlikely to happen, however, since nodes that join earlier in the process are likely to have more incoming links than nodes that join later.
Let us try to quantify this imbalance as follows:
(a) Given the random process described above, what is the expected number of incoming links to node vj in the resulting network? Give an exact formula in terms of n and j, and also try to express this quantity asymptotically using Θ notation.
(b) Part (a) makes precise a sense in which the nodes that arrive early carry an “unfair” share of the connections in the network.
Another way to quantify the imbalance is to observe that, in a run of this random process, we expect many nodes to end up with no incoming links.
Give a formula for the expected number of nodes with no incoming links in a network grown randomly according to this model.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

1. a) If we consider Incoming(j) the amount of incoming links for the node vj, then we have the following relation that relates this amount to the number of incoming links between the node vj and the remaining nodes (vj+1, vj+2,….vn):
Incoming(j)=Incoming(j,j+1)+Incoming(j,j+2)…..+Incoming(j,n-1)+Incoming(j,n).
It is straightforward that for any k=j+1,n we have Incoming(j,k)=1 when vk connects to vj and Incoming(j,k)=0 when vk doesn’t connect to vj (as per problem statement).
Also per problem hypothesis, because vj randomly uniform chooses a single node among the set {v1,v2,….,vj-1} to connect => expected probability for Incoming(j,k)=1/(k-1) for any k>j....

This is only a preview of the solution. Please use the purchase button to see the entire solution

$15.00

or $1 if you
register a new account!

Assisting Tutor

Related Homework Solutions

Benchmarking Bellman-Ford's Algorithm
Homework Solution
$38.00
Bellman Ford
Algorithm
Graph
Single Source
Shortest Path
Critical Operation
Big-O
Analysis
Documentation
Test Plan
Complexity
Benchmark
Approach
Improvement
Dijkstra
Relaxation
Edge
Node
Lessons Learned
Get help from a qualified tutor
Live Chats