iKen BirmanCornell University. CS5410 Fall 2008. Gossip 201y Last time we saw that gossip spreads in log(system size) timeB i hi ll “f ”yBut is this actually “fast”?d1.0% infected0.0Time →Gossip in distributed systemsy Log(N) can be a very big number!y With N=100,000, log(N) would be 12y So with one gossip round per five seconds, information needs one minute to spread in a large system!ySome gossip protocols combine pure gossip with an ySome gossip protocols combine pure gossip with an acceleratory For example, Bimodal Multicast and lpbcast are p,pprotocols that use UDP multicast to disseminate data and then gossip to repair if any loss occursBt th i ’t til th i tl yBut the repair won’t occur until the gossip protocol runsA thought questiony What’s the best wa y toy Count the number of nodes in a system?y Compute the average load, or find the most loaded nodes, or least loaded nodes?y Options to considery Pure gossip solutionuegoss p so ut oy Construct an ov erlay tree (via “flooding”, like in our consiste nt snapshot algorithm), then count nodes in the ll h f h l h tree, or pull the answer from the leaves to the root…… and the answer isy Gossip isn’t very good for some of these tasks!y There are gossip solutions for counting nodes, but they i it d llgive approximate answers and run slowlyy Tricky to compute something like an average because of “re‐counting” effect, (best algorithm: Kempe et al)g , ( gp)y On the other hand, gossip works well for finding the c most loaded or least loaded nodes (constant c)y Gossip solutions will usually run in time O(log N) and generally give probabilistic solutionsYet with flooding… easy!y Recall how flooding works321332Labels: distance of the node from the rooty Basically: we construct a tree by pushing data to wards th l d li ki d t it t h th t 3the leaves and linking a node to its parent when that node first learns of the floodyCan do this with a fixed topology or in a gossip style by yCan do this with a fixed topology or in a gossip style by picking random next hopsThis is a “spanning tree”y Once we have a spanning treey To count the nodes, just have leaves report 1 to their t d i d t th l f th i parents and inner nodes count the values from their childreny To compute an average, have the leaves report their value p g, pand the parent compute the sum, then divide by the count of nodesT fi d h l ldd d i d yTo find the least or most loaded node, inner nodes compute a min or max…yTree should have roughly log(N) depth, but once we Tree should have roughly log(N) depth, but once we build it, we can reuse it for a whileNot all logs are identical!y When we say that a gossip protocol needstime log(N) to run, we mean log(N) roundsAd i l ll d yAnd a gossip protocol usually sends one message every five seconds or so, hence with 100,000 nodes, 60 secsyBut our spanning tree protocol is constructed using a But our spanning tree protocol is constructed using a flooding algorithm that runs in a hurryy Log(N) depth, but each “hop” takes perhaps a millisecond. y So with 100,000 nodes we have our tree in 12 ms and answers in 24ms! answers in 24ms! Insight?y Gossip has time complexity O(log N) but the “constant” can be rather big (5000 times larger in our example)example)y Spanning tree had same time complexity but a tiny constant in frontconstant in frontyBut network load for spanning tree was much higherBut network load for spanning tree was much highery In the last step, we may have reached roughly half the nodes in the systemy So 50,000 messages were sent all at the same time!Gossip vs “Urgent”?y With gossip, we have a slow but steady storyy We know the speed and the cost, and both are lowyA constant, low‐key, background costy And gossip is also very robusty Urgent protocols (like our flooding protocol, or 2PC, or reliable virtually synchronous multicast) reliable virtually synchronous multicast) y Are way fastery But produce load spikesy And may be fragile, prone to broadcast storms, etcIntroducing hierarchyy One issue with gossip is that the messages fill upy With constant sized messages…y … and constant rate of communicationy … we’ll inevitably reach the limit!y Can we inroduce hierarchy into gossip systems?Astrolabey Intended as help for applications adrift Astrolabeapplications adrift in a sea of informationy Structure emerges fddfrom a randomized gossip protocoly This approach is robust and scalable robust and scalable even under stress that cripples traditional systemsDeveloped at RNS, Cornellbby By Robbert van Renesse, with many others helping…yToday used yToday used extensively within Amazon.comAstrolabe is a flexible monitoring overlayNameTimeLoadWeblogic?SMTP?WordNameTimeLoadWeblogic?SMTP?WordNameTimeLoadWeblogic?SMTP?Word Versionswift 2011 2.0 0 1 6.2falcon 1971 1.5 1 0 4.1cardinal 2004 4.5 1 0 6.0NameTimeLoadWeblogic?SMTP?Word Versionswift 2271 1.8 0 1 6.2falcon 1971 1.5 1 0 4.1cardinal 2004 4.5 1 0 6.0swift.cs.cornell.eduPeriodically, pull data from monitored systemsName Time Load Weblogic?SMTP? Word Versionswift 2003 .67 0 1 6.2falcon 1976 2.7 1 0 4.1cardinal 2201 3.5 1 1 6.0Name Time Load Weblogic?SMTP? Word Versionswift 2003 .67 0 1 6.2falcon 1976 2.7 1 0 4.1cardinal 2231 1.7 1 1 6.0cardinal.cs.cornell.eduAstrolabe in a single domainy Each node owns a single tuple, like the management information base (MIB)yNodes discover oneanother through a simple yNodes discover one‐another through a simple broadcast scheme (“anyone out there?”) and gossip about membershipy Nodes also keep replicas of one‐another’s rowsy Periodically (uniformly at random) merge your state with some else…with some else…State Merge: Core of Astrolabe epidemicNameTimeLoadWeblogic?SMTP?WordNameTimeLoadWeblogic?SMTP?Word Versionswift 2011 2.0 0 1 6.2falcon 1971 1.5 1 0 4.1cardinal 2004 4.5 1 0 6.0swift.cs.cornell.eduName Time Load Weblogic?SMTP? Word Versionswift 2003 .67 0 1 6.2falcon 1976 2.7 1 0 4.1cardinal 2201 3.5 1 1 6.0cardinal.cs.cornell.eduState Merge: Core of Astrolabe epidemicNameTimeLoadWeblogic?SMTP?WordNameTimeLoadWeblogic?SMTP?Word Versionswift 2011 2.0 0 1 6.2falcon 1971 1.5 1 0 4.1cardinal 2004 4.5 1 0 6.0swift.cs.cornell.eduswift 2011 2.0cardinal 2201 3.5Name Time Load Weblogic?SMTP? Word Versionswift 2003 .67 0 1 6.2falcon 1976 2.7 1 0 4.1cardinal 2201