EpidemicsHistoryMulticast RoutingSlide 4Atomic MulticastSlide 6“Best Effort” Multicast RoutingSlide 8Slide 9Epidemic AlgorithmsSlide 11Epidemic Algorithms in DatabasesSlide 13Slide 14Slide 15Slide 16Slide 17Epidemic Push/PullSlide 19Slide 20Slide 21Slide 22Bimodal MulticastThe pbcast Algorithm (from [1])Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Ad-Hoc Routing EpidemicsSlide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56OverviewDiscussionSlide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69EpidemicsPresented 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 algorithmsEx: MUSE algorithmProvides no assurance of end-to-end reliability assuranceProblems and solutions exist both at the physical network layer and the overlay areaFocus of distributed systems: overlay“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 TransactionEpidemic Algorithms in DatabasesClassic Examples:NNTPFirst use of e-mail serversetc…Epidemic Algorithms in DatabasesThree core concepts:Direct CommunicationBottleneck!Anti-Entropy MeasurePossible 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 MongeringProbabilistic spread of messages to (hopefully) nearly all nodesConsiderations between Push/Pull modelsEpidemic Algorithms in DatabasesDecide on two phase algorithm:Phase 1: Rumor MongeringPhase 2: Epidemic (Anti-Entropy)Ran periodically in the backgroundRan at each nodeEpidemic Push/PullGeneric Epidemic MessageAn epidemic message contains a summary of recent eventsTwo types: “push” and “pull”The different types of messages allow formalization of the mathematicsEpidemic 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 onlyShowed internal based resultsSimulation 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]The pbcast Algorithm (from [1])Two sub-protocols:Part 1: Hierarchical broadcastUnreliable, “best-effort” approachPart 2: Anti-entropy to correct packet loss if neededResults 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
View Full Document
Unlocking...