3. Collaborative Problem. 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 vi. 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 ui, U2, . . . , Uk-1 and node uk 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 ui, ,uni the random process described above will produce a directed network in which each node other than v 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 ; so if v, 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) [20 pointsl 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 (vian an expression without large summations) using notation. (b) [20 pointsl 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. 3. Collaborative Problem. 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 vi. 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 ui, U2, . . . , Uk-1 and node uk 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 ui, ,uni the random process described above will produce a directed network in which each node other than v 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 ; so if v, 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) [20 pointsl 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 (vian an expression without large summations) using notation. (b) [20 pointsl 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