0:18

This analysis willshow three claims.

Â The first that, uh, the, uh, gossip protocol is lightweight,

Â even when the groups are very large,

Â meaning they contain a large number of nodes,

Â uh, it spreads a multicast quickly, even in large groups,

Â and it is highly fault tolerant in spite of, uh, node failures

Â and in spite of packets being dropped.

Â 0:36

So, the analysis here is, uh,

Â derived from an old branch of mathematics called epidemiology,

Â and this is taken from a, uh, well-known textbook

Â on epidemiology by Bailey, published in 1975.

Â Um, essentially, epidemiology was a old branch of mathematics

Â that studied the spread of epidemic diseases

Â among prison populations

Â and among human populations in society.

Â Uh, the-the traditional, uh, classical version

Â of epidemi-epidemiology analysis

Â has a population of n+1 individuals

Â mixing homogenously.

Â Essentially, each of these individuals

Â is one of the nodes in our system

Â and consider these individuals or these molecules

Â being inside a jar and you're constantly shaking the jar

Â and these molecules are moving around

Â and hitting each other all the time.

Â The contact rate per time unit

Â between any pair of individuals is beta.

Â So, beta's typically a number between 0 and 1.

Â Uh, this is the probability

Â that two individuals will come in to contact with each other

Â during a given time unit.

Â At any time, each individual is either uninfected

Â and there are x such uninfected individuals,

Â or once it turns infected,

Â it stays infected and the number of infected is y.

Â Initially, only one infected, uh, individual is present.

Â This is the multicast center, so y_0=1 and the remaining, of,

Â uh, the remaining n individuals are all uninfected at time zero.

Â Of course, at all times,

Â because a-an individual is either uninfected or infected,

Â the sum of x+y at any given point of time should be n+1,

Â the number of individuals in the group.

Â 2:05

When an uninfected individual comes into contact

Â with any infected individual,

Â uh, the uninfected individual turns into infected

Â and it stays infected thereafter.

Â So, this sort of models, uh, the, uh, gossip-based protocol

Â that we have seen so far.

Â So, how do you analyze this?

Â Well, this is a continues time process

Â and you can essentially write this as a differential equation

Â where you write the rate of change of, uh, x,

Â which is the, uh, uh, uh, uninfected, uh, number

Â in the-in the system, um, as -beta*x*y.

Â First of all, it's negative because the number of uninfected

Â is obvious going down over time.

Â Uh, now, why is it, uh, -beta*x*y?

Â Well, x*y is the, uh,

Â total number of potential infected/uninfected contacts

Â per time unit,

Â and among those, um, uh, all possible x*y contacts,

Â only a fraction, beta, happen

Â because beta is, after all, the contact rate,

Â and for each of those contacts,

Â one uninfected turns into infected.

Â 3:29

One of the things for you to notice here is that, uh,

Â x over here, the equation for x,

Â uh, has, um, a t in it, which is the time,

Â which is the number of rounds

Â since the gossip-based protocol has started.

Â Remember again that here we are using a synchronous, uh, model

Â where all the processes or nodes proceed in lock step, uh,

Â from one round to another.

Â Uh, this is the only for the, uh, ease of analysis.

Â The analysis holds

Â even if, the, uh, processes are all unsynchronized.

Â 3:56

So, you notice that as t goes to infinity,

Â as t becomes very large,

Â the denominator is going to become extremely large

Â and x is gonna go down to zero.

Â Similarly, here, when t becomes very large,

Â this second, uh, uh, factor in the denominator, uh,

Â is, uh, going to go to zero, and so y is gonna go to n+1.

Â So, eventually the number of uninfected

Â becomes very close to zero

Â and the number of infected becomes very close to n+1,

Â which is the total number of nodes in the group.

Â So, eventually gossip converges

Â and everyone receives the gossip.

Â That's not surprising.

Â Well, what we want to show is

Â that gossip actually converges fairly fast.

Â 4:37

So, in the gossip based and epidemic multicast protocol,

Â the value beta is actually b/n.

Â Well, why is this?

Â Consider a, uh, an-an infected, uh, node

Â and consider one particular uninfected node.

Â The probability that this infected node

Â picks this particular uninfected node as a gossip target

Â during the round

Â is essentially the probability that it is one of the b targets

Â picked by the infected node during that round.

Â So, since there are n possible, um, uh, uh, targets, uh,

Â per round and the probability that this uninfected node

Â is picked as a gossip target, simply b/n.

Â So, you substitute this value beta

Â into the equation that we derived

Â and you substitute the value of t=clog(n)

Â this essentially says that you have, uh, n- uh, log(n) rounds

Â that have happened so far

Â and actually all the log(n) rounds

Â that have happened so far.

Â And you substitute in the previous equations,

Â you get the number, uh, of infected nodes

Â in the system is n+1,

Â the total number of nodes, minus this quantity 1/n^(cb-2)

Â This c comes from the clog(n) here,

Â and the b comes from, uh, the fan out of the gossip.

Â Now, if I set c to be some small number like 2

Â and b to be a small fan out like 2,

Â this, uh, term becomes 1/n^(4-2), or 1/n^2.

Â That's a very small number that's very close to zero.

Â Essentially what that's- what that is saying

Â is that after 2log(n) rounds,

Â as long as I'm using a gossip fan out of 2,

Â the, ah, number of infected nodes in the system

Â will be n+1 minus a very small number, 1/n^2,

Â which is very close to 0, and in fact, as n increases,

Â this number goes even closer to 0.

Â Essentially this is saying that the gossip converges

Â within a logarithmic number of rounds

Â and it gets very close to n+1 infected being in the system.

Â 6:16

So, as l- as long as you set c and b to be small numbers

Â that are independent of n,

Â they are constants, within clog(n) rounds.

Â This means low latency, all but a very small fraction of

Â number of nodes receive, uh, the multicast.

Â This means that the multicast is highly reliable

Â and it gets to almost everyone with high probability

Â within a logarithmic number of rounds.

Â And since only clog(n) rounds have happened, um,

Â nodes in the worst case are sent out, uh,

Â each node is sent out c*b*log(n) copies of the gossip message.

Â So, the order, the, ah, overhead

Â on each node is also logarithmic.

Â 7:00

Now, I hope that some of you are thinking,

Â "Well, it's log(n), it's not constant," right?

Â Um, the latency is O(log(n)), it's not constant,

Â um, the overhead is O(log(n)), it's not constant.

Â But, why is O(log(n)) so sacrosanct?

Â Well, log(n) is really not constant in theory,

Â but when it comes, uh, to practice, uh,

Â it is a very slowly growing number.

Â A log base 2(1000) = 10, log base 2(1M) = 20,

Â log base 2 (1B)~30,

Â and if you consider the IP before address space, uh,

Â log base 2(all IPv4 address)=32.

Â So, these are fairly small, uh, numbers,

Â and as far as practitioners are concerned,

Â many practitioners consider log(n)

Â to be a fairly small, uh, number

Â and a constant for practical purposes.

Â 7:55

Suppose 50% of the packets get dropped, uh,

Â from the network.

Â Again, we can analyze the protocol

Â by simply replacing b by b/2 because, after all, uh,

Â the gossip targets are selectived at random,

Â so even if you have, um, uh, uh, uh, packet losses

Â all over the network, uh,

Â these packet losses will be distributed uniformly

Â at random among the gossip messages.

Â So, you simply analyze b by, uh, nah, this,

Â do the same analysis as before by replacing b by b/2

Â because half the gossip messages get dropped,

Â and it turns out,

Â and you can check this for yourself, uh,

Â that to achieve the same reliability as 0% packet loss,

Â you only need to wait for twice as many rounds.

Â So, instead of using clog(n) rounds,

Â you wait for 2clog(n) rounds

Â and you get the same reliability as, uh, with a 50-

Â as with the 0% packet loss rate.

Â With node failure, 50% of the nodes fail, uh,

Â you replace n by n/2

Â because there are only half the nodes

Â that are alive in the system,

Â you care only about the reliability at them,

Â and you replace b by b/2, ah, again,

Â again, half the gossips get dropped

Â because they are sent to one of the failed nodes.

Â And once again, ah, you get a similar, um, a result

Â as, uh, before by increasing the number of log- uh,

Â the-the rounds by only a constant factor- um, uh,

Â multiplicative, constant multiplicative factor,

Â you get the same reliability

Â as if you had no node failures in the system.

Â 9:14

So, with failures,

Â one of the things that could happen with the gossip

Â is that it could die out very quickly

Â and this, uh, if it does happen,

Â typically happens very early in the gossip.

Â Very early in the gossip, if the sender, uh,

Â before it sends out a copy of the gossip dies, then obviously

Â you're not gonna get the gossip spread out anywhere.

Â The sender might send out one copy of the gossip, uh,

Â to a few nodes in the system, just one round,

Â and then all these, uh, first round recipients

Â and the sender byte might die.

Â Okay, the probability of this happening is very low

Â because these are selected at random,

Â so even if you have gossip running in a data center

Â and an entire rack goes out,

Â as long as one, um, er, process outside the rack got the gossip,

Â you'd still have the gossip spread and it is very resilient.

Â 9:55

So, once the gossip has infected a small amount of nodes

Â in the system, just a few rounds,

Â after that it's very hard to kill the gossip.

Â And this is kinda, should be familiar to you

Â because this is uh, paralleling

Â uh, the way in which disease is spread

Â in, uh, human populations or rumors spread in society.

Â Once a rumor of the disease gets out, uh, a little bit farther,

Â it's very hard to contain.

Â Okay, so, all the analysis that we've seen

Â in the previous slides is with high probability,

Â and this has been shown in another book, uh,

Â by Galey and Dani, uh, which also analyzed, uh, gossip.

Â 10:40

So, what about the pull-gossip protocol?

Â So far we have looked at the push-gossip protocol,

Â what about pull?

Â Uh, in all forms of gossip, whether it's push or pull,

Â it takes O(log(n)) rounds before the, uh, before, uh,

Â about half the nodes in the system get the gossip.

Â Why is this?

Â Well, uh, the best you can do

Â is essentially build a spanning tree

Â among the nodes in the system,

Â and if you have a constant fan out,

Â constant number of children

Â per node in f-in the spanning tree,

Â it takes O(log(n)) rounds for about half the nodes to get, uh,

Â this, uh, uh, gossip message in the best case.

Â However, thereafter,

Â after about half the nodes have received the gossip,

Â pull is faster than push.

Â Yeah, how-to see this, let's look at the following:

Â After the ith round,

Â let p_i be the fraction

Â of noninfected or uninfected processes in the system,

Â then in the i+1 round, uh,

Â the value of p_(i+1) is essentially (p_i)/(k+1)

Â where k is the, um, number of, um,

Â k is the number of, uh, gossip targets.

Â K=b in this particular case.

Â Why is this?

Â Well, the probability that you stay infected- uh, noninfected

Â at the end of the i+1 round

Â is the probability that you were uninfected

Â at the beginning of the i+1 round,

Â so that's p_i by itself,

Â and also the probability

Â that each of the k or b, um, uh, targets

Â that you contacted at random

Â were all also uninfected by the gossip,

Â and that's, uh, times (p_i)^k,

Â and that's how you get (p_i)^(k+1).

Â So, this goes around very quickly,

Â and in fact this goes around, uh, super exponentially,

Â faster than exponential,

Â and it can show that this is O(log(log(n)),

Â not just O(log(n)), but it's O(log(log(n)),

Â so it's much faster than logarithmic.

Â So, overall the pull gossip protocol is still O(log(n)),

Â but, ah, uh, it's much faster in the second half.

Â 12:23

So, this should give you an idea of getting,

Â b-of designing, perhaps, a push-pull hybrid protocol

Â where you use push in the beginning portion

Â to get the gossip out very quickly

Â and then use pull, uh, in the later rounds, uh,

Â to, uh, um, uh, to-to get it out

Â to everyone else in-in the system very quickly.

Â 12:42

Finally, uh, the gossip protocols

Â that we've discussed so far are not topology aware,

Â so, uh, when it comes to a hierarchical topology,

Â whether it's, uh, on the internet using subnets

Â or whether it's on-in a data center using, uh, racks,

Â uh, the core switches and routers

Â might get overloaded quite a bit.

Â So, for instance, consider a scenario

Â where I have two subnets, perhaps two racks;

Â uh, the top subnet and the bottom subnet

Â each with n/2 nodes, uh, from the group.

Â Since each node selects a gossip target uniformly at random,

Â about half the gossips are gonna go across from one subnet

Â to the other, okay, and also from the bottom to the top.

Â This means that the router sees, uh, n/2,

Â actually b*(n/2) gossips go out per, uh, gossip period

Â and so the load on the router

Â is going to be O(n), which is very, very high.

Â So, the fix to this is to do the following.

Â You have gossip that, uh, prefers nodes in your own subnet

Â with a high probability

Â and nodes outside your subnet with a lower probability.

Â If your subnet contains ni or n_i, uh, nodes, you, uh,

Â gossip, uh, um, uh, outside your subnet with probablity 1/(n_i).

Â With probability 1-(1/(n_i)),

Â you gossip within your own subnet.

Â So, this means that within your own subnet,

Â because the probability of gossiping

Â is still very close to one,

Â ah, it's gonna spread in O(log(n)) time,

Â and this is true for any one of these subnets.

Â And then after a subnet has been completely infected,

Â uh, since everyone gossips outside with probability 1/(n_i)

Â and there is n_i such nodes gossiping outside,

Â it takes O(1), uh, rounds on expectation

Â for the gossip to go across the router to the other, uh, subnet

Â and for someone in the other subnet to get infected.

Â After that, again, it's gonna take O(log(n)) rounds

Â to spread within that subnet itself.

Â So, overall it's still O(log(n)) +, uh, O(1) + O(log(n)), uh,

Â for it to get across

Â and so it's still O(log(n)) rounds dissemination time,

Â and instead what we have done

Â is that we have re-reduced the load on the router to be O(1).

Â Why is it O(1)?

Â Well, uh, because essentially you have n_i nodes in the-

Â in one subnet and since each of them

Â sends a gossip out with probability 1/(n_i),

Â the, uh, expected number of gossips going through the router

Â is (n_i*1)/(n_i), which is O(1).

Â