1EpidemicsPresented By:Lucas Cook and Wade FagenCS 525, The University of Illinois (UIUC)6 February 2007HistoryTwo schools of algorithms multicast:ProactiveReactiveExisting Algorithms/Implementations:SRMIP Multicast (best-effort)NNTP (gossip)IRC (hierarchical multicast)PSYC (multicast; more “web”-like than IRC)Multicast Routing“Reliable” Multicast Routing:Ensure that a message sent from any node is received by all other nodes within any distributed system.…but we don’t live in an “ideal”world.Multicast RoutingThree general categories:Algorithms that provide “strong”reliability properties. Ex: atomic multicastsRound:#1#2 #3 …Atomic MulticastNodes only process at the beginning of roundsNew rounds don’t start until all previous messages are receivedRound:#1#2 #3 …Multicast RoutingThree general categories:“strong” reliability algorithms“best-effort” reliability algorithms Ex: MUSE algorithm Provides no assurance of end-to-end reliability assuranceProblems and solutions exist both at the physical network layer and the overlay areaFocus of distributed systems: overlay2“Best Effort” Multicast RoutingMany algorithms implement some neighbor-based approach…“Best Effort” Multicast RoutingEnd-to-end assurance may be lost by one node’s failure:Multicast RoutingThree general categories:“strong” reliability algorithms“best-effort” reliability algorithms“proactively probabilistic” multicast algorithmsProvides predictable reliabilityGoal: Achieve better reliability than “best-effort” without the overhead of “strong”reliabilityMethod: EpidemicsEpidemic AlgorithmsEpidemics help ensure probabilistic end-to-end reliability with an assurance of “almost all” or “almost none” structureTradeoff between scale and reliability: epidemics allow for expansive scale with near-perfect reliabilityEpidemic AlgorithmsTo be less verbose, the following citations are used throughout the presentation:[1]: Bimodal multicast, K Birman et al, ACM TOCS 1999 [2]: Epidemic algorithms for replicated database maintenance, A. Demers et al, PODC 1987.[3]: Gossip-based ad hoc routing, Z. Haas et al, Infocom 2002Epidemic Algorithms in DatabasesSite updating has been a key problem since the beginning of distributed database work:Data is injected at one siteData needs to be updated at every siteIncoming Transaction3Epidemic Algorithms in DatabasesClassic Examples:NNTPFirst use of e-mail serversetc…Epidemic Algorithms in DatabasesThree core concepts:Direct Communication Bottleneck!Anti-Entropy Measure Possible full comparison (slow!)Rumor Management Only updates!Epidemic Algorithms in DatabasesThree states of a message /nodeSusceptive: Message not received at nodeInfective: Message is actively propagated by nodeRemoved: Message is no longer actively propagated by nodeEpidemic Algorithms in DatabasesDecide on two phase algorithm:Phase 1: Rumor Mongering Probabilistic spread of messages to (hopefully) nearly all nodes Considerations between Push/Pull modelsEpidemic Algorithms in DatabasesDecide on two phase algorithm:Phase 1: Rumor MongeringPhase 2: Epidemic (Anti-Entropy) Ran periodically in the background Ran at each nodeEpidemic Push/PullGeneric Epidemic MessageAn epidemic message contains a summary of recent events Two types: “push” and “pull”The different types of messages allow formalization of the mathematics4Epidemic Push/PullA “push” is a message sent from some infected site to a susceptible site.Incoming TransactionpushEpidemic Push/PullA “pull” is a message sent from some susceptible site to an infected siteIncoming TransactionpushpullpushEpidemic Algorithms in DatabasesWith the general idea, the specifics of [2] relate to databases:Two primary distributed operations “Data Insertion”: INSERT, UPDATE “Data Deletion”: DELETEEpidemic message for DELETE are augmented with a “death certificate”In [2], SELECT is simply done locally at each distributed end point of the databaseEpidemic Algorithms in DatabasesResults published in [2]Key Result: Replacing deterministic algorithms for database consistencyActual Results: Simulation-based solution only Showed internal based results Simulation of traditional schemes wasn’t done for accurate comparisonBimodal Multicast[1] presents a bimodal multicast algorithm called pbcastpbcast := “probabilistic broadcast”The pbcast Algorithm (from [1])Six Properties:Atomicity (probabilistically)Throughput StabilityOrdering (FIFO)Multicast StabilityDetection of Lost MessagesScalability[Acceptability of soft failures]5The pbcast Algorithm (from [1])Two sub-protocols:Part 1: Hierarchical broadcast Unreliable, “best-effort” approachPart 2: Anti-entropy to correct packet loss if needed Results in predictable end-to-end assurancesThe pbcast Algorithm (from [1])Basic Hierarchical Broadcast:m1m1m1Node 1: {1}Node 2: {1}Node 3: {1}Node 4: {1}The pbcast Algorithm (from [1])Basic Hierarchical Broadcast:m1m1m1m2m2m2m2m2m2m2m2m1m1m1m1m1Node 1: {1, 2}Node 2: {1, 2}Node 3: {1, 2}Node 4: {1, 2}The pbcast Algorithm (from [1])Basic Hierarchical Broadcast:m3m2m2m2m1m1m1m1m2m1m1m2m1m1m1m2m1m2m1m1m2m1m3m2m1m1m2m1m2m3m2m1m1m2m1Node 1: {1, 2}Node 2: {1, 2}Node 3: {1, 2, 3}Node 4: {1, 2}Node 1: {1, 2}Node 2: {1, 2}Node 3: {1, 2, 3}Node 4: {1, 2}Node 1: {1, 2}Node 2: {1, 2}Node 3: {1, 2, 3}Node 4: {1, 2}The pbcast Algorithm (from [1])Basic Hierarchical Broadcast:m2m3m2m1m1m2m1m4m4m4m1m1m1m1m1m1m2m1m1m1m2m2m1m1m1m3m2m2m1m1m1m2m3m2m2m1m1m1m4m2m4m1m2m4m1m1m2m4m2m1m1m2m4m1m2m1m1m2m4m2m1m2m1m1m2m4m3m2m1m2m1m1m2m4m4m3m2m1m2m1m1m2m4m4m4m3m2m1m2m1m1m2m4Node 1: {1, 2, 4}Node 2: {1, 2, 4}Node 3: {1, 2, 3, 4}Node 4: {1, 2, 4}Node 1: {1, 2, 4}Node 2: {1, 2, 4}Node 3: {1, 2, 3, 4}Node 4: {1, 2, 4}The pbcast Algorithm (from [1])Basic Hierarchical Broadcast:m4m4m3m2m1m2m1m1m2m4m5m5m5Node 1: {1, 2, 4}Node 2: {1, 2, 4, 5}Node 3: {1, 2, 3, 4, 5}Node 4: {1, 2, 4, 5}6The pbcast Algorithm (from [1])The anti-entropy protocol runs simultaneously with the broadcast messagesProtocol runs in rounds: Ran at every process Rounds longer than round-trip time Paper suggests: ~100ms… maybe a traffic-based metric would be
View Full Document
Unlocking...