8. One of the less popular candidates is polling at very small numbers in most of

the states. They want to analyze the "topology-aware gossip" protocol you've

seen in lecture. However, instead of the lecture slide example of 2 subnets joined

by 1 router, here we have a total of N nodes (processes), evenly spread out across

√N subnets (each subnet containing √N nodes), all joined by 1 router. The

subnets are numbered S0, S1, S2, ... S(√ N-1). All these √N subnets are connected

together via 1 router. You can assume all nodes have a full membership list, and

there are no failures (messages or processes). The topology-aware gossip works

as follows. Consider a process Pj choosing gossip targets. The process' gossip

targets depend on the subnet Si that it lies in. During a gossip round, the process

Pj selects either b "inside-subnet Si gossip targets" with probability (1-1/√N), OR

b "outside-subnet Si gossip targets" with probability 1/√N. The only

"restriction" is that after process Pj is infected, for the next O(log(/√N)) rounds

Pj picks only inside-subnet targets (no outside-subnet targets) -- thereafter in a

gossip round at Pj, either all its targets are inside-subnet or all are outside-

subnet. Inside-subnet gossip targets from Pj (in Si) are selected uniformly at

random from among the processes of Si. Outside-gossip targets from Pj (in Si) are

only picked from the processes in the "next" subnet S((i+1)mod√N), and they are

picked uniformly at randomly from the processes lying in that “next” subnet.

The gossiping of a message does not stop (i.e., it is gossiped forever based on the

above protocol). Does this topology-aware gossip protocol satisfy both the

requirements of: (i) O(log(N)) average dissemination time for a gossip (with one

sender from any subnet), and (ii) an O(1) messages/time unit load on the router

at any time during the gossip spread? Justify your answers.