1Leiden; Dec 06 Gossip-Based Networking Workshop 1Epidemic Algorithms and Emergent ShapeKen BirmanLeiden; Dec 06 Gossip-Based Networking Workshop 2On Gossip and Shapen Why is gossip interesting?n Powerful convergence properties?n Especially in support of epidemicsn Mathematical elegance?n But only if the system model cooperatesn New forms of consistency?n But here, connection to randomness stands out as a particularly important challengeLeiden; Dec 06 Gossip-Based Networking Workshop 3On Gossip and Shapen Convergence around a materialized “graph” or “network topology” illustrates several of these pointsn Contrasts convergence with logical determinism of traditional protocolsn Opens the door to interesting analysisn But poses deeper questions about biased gossip and randomnessLeiden; Dec 06 Gossip-Based Networking Workshop 4Value of convergencen Many gossip/epidemic protocols converge exponentially quicklyn Giving rise to “probability 1.0” outcomesn Even model simplifications (such as idealized network) are washed away!n A rarity: a theory that manages to predict what we see in practice!Leiden; Dec 06 Gossip-Based Networking Workshop 5Convergencen I’ll use the term to refer to protocols that approach a desired outcome exponentially quicklyn Implies that new information mixes (travels) with at most log(N) delayLeiden; Dec 06 Gossip-Based Networking Workshop 6Consistencyn A term to capture the idea that if A and B could compare their states, no contradiction is evidentn In systems with “logical” consistency, we say things like “A’s history is a closed prefix of B’s history under causality”n With probabilistic systems we seek exponentially decreasing probability (as time elapses) that A knows “x” but B doesn’tn Gossip systems are usually probabilistic2Leiden; Dec 06 Gossip-Based Networking Workshop 7Convergent consistencyn To illustrate our point, contrast Cornell’s Kelips system with MIT’s Chordn Chord: The McDonald’s of DHTsn Kelips: DHT by Birman, Gupta, Linga. n Prakash Linga is extending Kelips to support multi-dimensional indexing, range queries, self-rebalancingn Kelips is convergent. Chord isn’tLeiden; Dec 06 Gossip-Based Networking Workshop 8Kelips30110230 202Take a a collection of “nodes”Leiden; Dec 06 Gossip-Based Networking Workshop 9Kelips0 1 230110230 2021N−Nmembers per affinity groupMap nodes to affinity groupsAffinity Groups:peer membership thru consistenthashLeiden; Dec 06 Gossip-Based Networking Workshop 10Kelips0 1 230110230 202Affinity Groups:peer membership thru consistenthash1N−Affinity group pointersNmembers per affinity grouprtthbeatid30ms32223090ms23430Affinity group view110 knows about other members –230, 30…Leiden; Dec 06 Gossip-Based Networking Workshop 11Affinity Groups:peer membership thru consistenthashKelips0 1 230110230 2021N−Contact pointersNmembers per affinity grouprtthbeatid30ms32223090ms23430Affinity group view……2022contactNodegroupContacts202 is a “contact” for 110 in group 2Leiden; Dec 06 Gossip-Based Networking Workshop 12Affinity Groups:peer membership thru consistenthashKelips0 1 230110230 2021N−Gossip protocol replicates data cheaplyNmembers per affinity grouprtthbeatid30ms32223090ms23430Affinity group view……2022contactNodegroupContacts……110cnn.cominforesourceResource Tuples“cnn.com” maps to group 2. So 110 tells group 2 to “route” inquiries about cnn.com to it.3Leiden; Dec 06 Gossip-Based Networking Workshop 13How it worksn Kelips is entirely gossip based!n Gossip about membershipn Gossip to replicate and repair datan Gossip about “last heard from” time used to discard failed nodesn Gossip “channel” uses fixed bandwidthn … fixed rate, packets of limited sizeLeiden; Dec 06 Gossip-Based Networking Workshop 14How it worksn Basically…n A stream of gossip data passes by each node, containing information on various kinds of replicated datan Node “sips” from the stream, for example exchanging a questionable contact in some group for a better onen Based on RTT, “last heard from” time, etcLeiden; Dec 06 Gossip-Based Networking Workshop 15How it worksn Heuristic: periodically ping contacts to check liveness, RTT… swap so-so ones for better ones.Hmm…Node 19 looks like a great contact in affinity group 2Node 102Gossip data streamLeiden; Dec 06 Gossip-Based Networking Workshop 16Convergent consistencyn Exponential wave of infection overwhelms disruptionsn Within logarithmic time, reconvergesn Data structure emerges from gossip exchange of data. n Any connectivity at all suffices….Leiden; Dec 06 Gossip-Based Networking Workshop 17… subject to a small caveatn To bound the load, Kelipsn Gossips at a constant raten Limits the size of packetsn …Kelips has limited incoming “info rate”n Behavior when the limit is continuously exceeded is not well understood.Leiden; Dec 06 Gossip-Based Networking Workshop 18What about Chord?n Chord is a “true” data structure mapped into the networkn Ring of nodes (hashed id’s)n Superimposed binary lookup treesn Other cached “hints” for fast lookupsn Chord is not convergently consistent4Leiden; Dec 06 Gossip-Based Networking Workshop 19… so, who cares?n Chord lookups can fail… and it suffers from high overheads when nodes churnn Loads surge just when things are already disrupted… quite often, because of loadsn And can’t predict how long Chord might remain disrupted once it gets that wayn Worst case scenario: Chord can become inconsistent and stay that wayLeiden; Dec 06 Gossip-Based Networking Workshop 20Chord picture01231992022412552481081776430Cached linkFinger linksLeiden; Dec 06 Gossip-Based Networking Workshop 21Chord picture01231992022412552481081776430EuropeUSA01231992022412552481081776430Transient Network PartitionLeiden; Dec 06 Gossip-Based Networking Workshop 22The problem?n Chord can enter abnormal states in which it can’t repair itselfn Chord never states the global invariant… in some partitioned states, the local heuristics that trigger repair won’t detect a problemn If there are two or more Chord rings, perhaps with finger pointers between them, Chord will malfunction badly!The Fine PrintThe scenario you have been shown is of low probability. In all likelihood, Chord would repair itself after any partitioning failure that might really arise. Caveat emptor and all that.Leiden; Dec 06 Gossip-Based Networking Workshop 23So… can Chord be fixed?n Epichorddoesn’t have this