1CS514: Intermediate Course in Computer SystemsLecture 15: Oct. 18, 2003Epidemic Protocols (or, Gossip is Good)Slides by Robbert Van RenesseCS514Up to now…| We’ve looked at a few forms of replicationz Hot standby, group communications systems, pub/sub architectures| Or focus has been on relatively synchronized replicationz and other strict properties, like ordering| Its time for a change of pace!2CS514Well, its still about replication . . .| In fact, CS514 in a way is almost entirely about replication!| But lets spend some time looking at weaker, less synchronous forms of “replication”z Perhaps better called “dissemination”CS514What is wrong with ISIS, Totem, Spread, etc?| In a word, scalability (that is, they don’t have much)z The lockstep nature of these protocols leads to a “weakest link” phenomenon … the slowest member dominates performancez Recall that ISIS deployment in French ATC was limited to groups of 5-6 machines over LANs3CS514What is wrong with ISIS, Totem, Spread, etc?| Furthermore, they are complex protocols, which speaks badly for fault tolerancez Complex software is more buggy| And they are overkill for many applicationsz We just happen to be focusing on particular extreme requirementsCS514So what do we want?| Systems with simple protocols| Systems that have “only” probabilistic guarantees| Systems that scale to very large numbers of nodesz No “weakest link” phenomenon| Systems that are relatively insensitive to “churn”z Nodes coming and going| Systems that disseminate data pretty fast4CS514“Push” versus “pull”| Pablo showed us Content Distribution Networks (CDN)| As used by Akamai, these are “pull” based systemsz User requests drive the distribution of data into caches| The pub/sub systems we looked at are “push” based systemsz Publish events drive the distribution of dataCS514We’re interested in both| But for now we are going to focus on push based systemsz First gossip, then reliable multicast (of various forms)| Later we’ll look (a little more) at pull (caching) based systems5CS514Basic goal:| Distribute some data among a group of nodesz Should be fast, but no synchrony guaranteesz Should be robust (some nodes may crash, but still works)z Should scale to many nodesz Should be efficientCS514Basic goal: fast, robust data dissemination6CS514Basic goal: fast, robust data disseminationCS514One way…sender sends message to all other nodes one at a time| Efficient, in that exactly N-1 copies are sent| But slow !z (N-1)*L, where N is the number of nodes, and L is the time it takes to send the message| So to overcome this, we want to exploit some kind of parallelism| (Also, how does the sender learn about all the other nodes?)7CS514Another way…build a treeCS514Another way…build a tree| Very fast (lots of parallelism)| Very efficientz N-1 copies sentz And spread over many nodes (not just one sender)| But fragile, and complexz Hard to build these treesz If one node crashes, other nodes are partitioned, at least for a while8CS514Tree partitionCS514Another way…flood the data9CS514Another way…flood the dataCS514Another way…flood the data10CS514Another way…flood the dataCS514Another way…flood the data| Robust, fast, and scales well| But quite inefficientz Most nodes receive the message multiple times…worse with higher node degreez Also, each node must remember identifier of specific received messages (so that the flood can terminate)11CS514Another way…gossip (a.k.a. epidemic algorithm)| Gossip is something like floodingz Robust, not perfect efficiency| Flooding paradigm is message forwardingz Gossip paradigm is state exchange| Flooding nodes forward messages immediatelyz Gossip nodes exchange state periodically| Flooding nodes keep list of recent message identifiersz Gossip nodes keep current stateCS514Another way…gossip (a.k.a. epidemic algorithm)| Flooding nodes talk to small number of “neighbors”z Gossip nodes talk at random with any other node| Flooding is a fast burst of activityz Gossip is a slow persistent burn| Ultimately gossip is more robust because it continuously tries to synchronize statez With flooding, if a node fails to receive a message, it doesn’t get a second chance12CS514History of Gossip| Grapevine/Clearinghouse Directory Service (Demers, Xerox PARC, 1987)| Refdbms (Golding, UCSC, 1993)| Bayou (Xerox PARC, 1995)| Bimodal Multicast (Cornell, 1998)| Astrolabe (Cornell, 1999)CS514State Monotonic Property| A gossip message contains the state of the sender of the gossip.| The receiver uses a Merge function to merge the received state and the sent state:z State’ = Merge(State, Gossip)| Need some kind of monotonicity:z State’ ≥ State, State’ ≥ Gossipz Without this, old “news” will constantly chase new “news”z Can be implemented with a per datum sequence number set by the state originator13CS514Anti-Entropy| This gossip scheme with monotonic merge is sometimes called anti-entropy.| The protocol is called a simpleepidemic.CS514How fast (and how well) does gossip spread?| Epidemic theory (e.g., Bailey …)| Assume a fixed population of size n.| For now, assume homogeneous spreadingz simple epidemic: anybody can infect anyone else with equal probability| Assume k members already infected.| Assume infection occurs in rounds.14CS514Probability of Infection?| What is the probability Pinfect(k, n) that a particular uninfected member is infected in a round if k are already infected?Pinfect(k, n)= 1 – P(nobody infects member)= 1 – (1 – 1/n)^kkn...E(#newly infected members) =(n – k) × Pinfect(k, n)(binomial distribution)CS514Phase 1: fast growth of infection| Early on, most state exchanges result in a new infectionz Initial rate of infection: factor of 2| In the middle, start reaching saturationz Half way: factor of 1.4| In the end, most data exchanges are redundant, but the remaining uninfected nodes are infected rapidly z Near end, factor ≈ 115CS514Intuition: 2 phases| Phase 1: 1 → n/2 (first half)| Phase 2: n/2 → n (second half)| For large n, Pinfect(n/2, n) ≈ 1 − (1/e)^.5 ≈ .4| Half way:• Infection grows by factor 1.4• Uninfection declines by factor .4CS514Exponential growth| Taken together: #rounds necessary to infect the entire population grows O(log n)| Base of log: 1.585 (experimental)| Even under bad conditions (see later):z member failuresz message lossz but base of log decreases16CS514Number of new infectionsCS514Number of
View Full Document
Unlocking...