EpidemicsProblem: MulticastChallengesEpidemic Algorithm for Replicated Database MaintenanceMotivation: Replicated databaseApproachDirect MailAnti-EntropyAnti-Entropy: Push and PullPull > PushAnti-Entropy: OptimizationComplex Epidemics: “Not Anti-entropy” Rumor SpreadingSlide 13Designing a Good EpidemicVariants of Rumor SpreadingProblem with DeletionDiscussionBimodal MulticastDilemmaProbabilistic Broadcast: pbcastPbcast 2-stage ProtocolPbcast: Best Effort DisseminationPbcast: Random Spanning TreeSlide 24Slide 25Slide 26Pbcast: Hierarchical MulticastSlide 28Slide 29Pbcast: Two phase anti-entropyPbcast: Anti-entropyOptimizations (2)Optimizations (1)Analytic ResultsBimodal Delivery DistributionExperimental SetupSource to dest latency distributionsThroughput variation as a function of scale (25% nodes perturbed)Slide 39Exploring the Energy – Latency Trade-off for Broadcasts in Energy-Saving Sensor NetworksWSN ApplicationsBackground: IEEE 802.11 PSMReducing Latency : Immediate BroadcastProbability-Based Broadcast Forwarding (PBBF)Effect of p and q on Reliability, Energy, LatencySlide 46Energy, ELatency, LReliability, REnergy – Latency TradeoffAdaptive PBBFConclusionSlide 53AcknowledgmentsEpidemicsSpring 2008: CS525Farhana Ashraf and Fariba Khan1Problem: MulticastSimultaneously deliver information to a group of destinations.Examples:News groupsUpdate for replicated database systems Real-time media (i.e. Sports)Conference bridgeSoftware update in ad-hoc and sensor network2ChallengesReliable: Strong Best-effort Probabilistic (bimodal)DelayBandwidthFault-tolerance3Epidemic Algorithm for Replicated Database MaintenanceAlan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swineheart, Doug TerryPODC 19874Motivation: Replicated databaseXerox ClearinghouseData is replicated in 300 sites worldwide. An update in any site has to be forwarded to other 299.Financial Distributed SystemsData and Code replicated worldwide. There is a 7-hour window between the stock market closing in Tokyo and opening in NYC.5ApproachNaiveDirect MailEpidemicAnti-entropyRumor-mongering6Direct MailTimelyImmediately mailed from the entry site to all other siteNot entirely reliableIncomplete information about other sitesMail may be lostPostMailPostMailPostMailPostMailPostMailPostMailSusceptible nodeInfectious nodeAnti-EntropyExtremely reliableResolves difference with random site periodicallySlow & ExpensiveExamines the contents of the entire databasesDatabase content sent over networkSusceptible nodeInfectious nodeResolveDiffResolveDiffResolveDiffResolveDiffAnti-Entropy: Push and PullSusceptible nodeInfectious nodePUSHPULLNot updatedNot updatedPUSH - PULLPull > PushIf Anti-entropy is back-up for, e.g., Direct-MailPull converges faster than push, thus providing better delaypi1pi2pi1pi11nn1piPullPushpi – Probability that a node is susceptible after the ith roundAnti-Entropy: OptimizationChecksumExchange checksum first, compare database if checksum disagree [saves network traffic]As network size increases, time to distribute update to all sites increase [more possibility of checksum mismatch]Recent update listExchange recent update list within T to update database and new checksumCompare databases if new checksum disagreeChoice of T criticalInverted index of database by timestampExchange updates in reverse timestamp order, compute checksum until checksum matchCost of additional inverted index at each siteSynchronization of timeComplex Epidemics: “Not Anti-entropy”Rumor SpreadingLess expensiveRequire fewer resourcesCan be done more frequently than anti-entropyLess reliableSome chance that updates will not reach all sitesSusceptible nodeInfectious nodeRemoved nodeComplex Epidemics: “Not Anti-entropy”Rumor SpreadingLess expensiveRequire fewer resourcesCan be done more frequently than anti-entropyLess reliableSome chance that updates will not reach all sitesSusceptible nodeInfectious nodeRemoved nodeDesigning a Good EpidemicResidueNumber of sites not receiving the update, when epidemic ends TrafficAverage number of messages sent from a typical siteDelaytavg: difference between initial injection and avg. arrival of update at a given siteTlast: Delay until reception by the last site that receives the update during epidemicVariants of Rumor SpreadingBlind vs. FeedbackBlind: sender looses interest with prob. 1/k regardless of recipientFeedback: sender looses interest with prob. 1/k only if recipient already knows the rumorCounter vs. CoinCounter: loose interest only after k unnecessary contactsPush vs. PullProblem with DeletionProblemAbsence of an item does not spreadPropagation of old copies of deleted item will cause insertion of the item back to the siteSolutionReplace deleted item with Death Certificate (DC)DiscussionDirect Mail or Epidemics?Economics and Industry?Anti-entropy or Rumor?Bimodal MulticastKen Birman, Mark Hayden, Oznur Ozkasap, Zhen Xiao, Mihai Budiu, Yaron MinskyACM TOCS 199918DilemmaApplication is extremely critical: stock market, air traffic control, medical systemHence need a strong model, guaranteesBut these applications often have a soft-realtime subsystemSteady data generationMay need to deliver over a large scaleProbabilistic Broadcast: pbcastAtomicity: bimodal delivery guaranteealmost all or almost noneThroughput stability: variation can be characterizedOrdering: FIFO per senderMulticast stability: safely garbage collected (no dormant death certificate)Detection of lost messagesScalability: cost is a function of network sizeSoft failure recovery: bounded number of recoveries from buffer overflow, transient network. 20Pbcast 2-stage ProtocolStage 1: Best effort disseminationHierarchical broadcastUnreliable best-effort approachStage 2: Anti-entropyExchange digest and correct lossProbabilistic end-to-end21Pbcast: Best Effort DisseminationIP multicastor“virtual” multicast spanning treesSender randomly generates a spanning treeNeighbors forward based on the tree identifierNumber of random trees can be tuned22Pbcast: Random Spanning TreeP QR S23Pbcast: Random Spanning TreeP QR S24Pbcast: Random Spanning TreeP QR S25Pbcast: Random Spanning TreeP QR
View Full Document
Unlocking...