CS 525 Advanced Distributed Systems Spring 09Question…Critical Value? Answer = 0.5“Tipping Point”Epidemic ProtocolsEpidemic Algorithms for Replicated Database MaintenanceIntroductionEpidemic MulticastEpidemic Multicast (Push)Epidemic Multicast (Pull)Pull > PushAnti-entropy: OptimizationsEpidemic FlavorsDeletion and Death CertificatesPerformance MetricsPerformance EvaluationDiscussionBimodal Multicast“Traditional” Multicast ProtocolsVs. PbcastPbcast: Probabilistic Broadcast ProtocolThe second stageOptimizationsBimodality of PbcastLatency for DeliveryThroughput ComparisonSlide 27PBBF: Probability-Based Broadcast ForwardingBroadcast in an Ad-Hoc NetworkIEEE 802.11 PSMProtocol Extreme #1Protocol Extreme #2Probability-Based Broadcast Forwarding (PBBF)Analysis: ReliabilityApplication: Energy and LatencyAdaptive PBBFAdaptive PBBF (TOSN paper)Slide 38Slide 39Next Week Onwards1CS 525 Advanced Distributed SystemsSpring 09Indranil GuptaLecture 7More on Epidemics (or “Tipping Point Protocols”)February 12, 2009(gatorlog.com)(epath.org)2Question…What fraction of main roads need to be randomly knocked out before source and destination are completely cut off?DestinationSource3Critical Value? Answer = 0.5Tipping Point!SourceDestination(Comes from Percolation Theory)4“Tipping Point”[Malcolm Gladwell, The Tipping Point, Little Brown and Company, ISBN: 0316346624] Tipping is that (magic) moment when an idea, trend or social behavior crosses a threshold, and spreads like wildfire.5Epidemic Protocols•A specific class of tipping point protocols•Local behavior at each node – probabilistic•Determines global, emergent behavior at the scale of the distributed system•As one tunes up the local probabilities, the global behavior may undergo a threshold behavior (or, a phase change)•Three papers:1. Epidemic algorithms2. Bimodal multicast3. PBBF (sensor networks)6Epidemic Algorithms for Replicated Database MaintenanceAlan Demers et. al.Xerox Palo Alto Research CenterPODC 1987[Some slides borrowed from presentation by: R. Ganti and P. Jayachandran]7Introduction•Maintain mutual consistency of updates in a distributed and replicated database•Used in Clearinghouse database – developed in Xerox PARC and used for many years•First cut approaches –Direct mail: send updates to all nodes•Timely and efficient, but unreliable–Anti-entropy: exchange database content with random site •Reliable, but slower than direct mail and uses more resources–Rumor mongering: exchange only ‘hot rumor’ updates•Less reliable than anti-entropy, but uses fewer resources8Epidemic Multicast Protocol Protocol roundsrounds (local clock) (local clock) b b random targets per roundrandom targets per round UninfectedUninfected InfectedInfectedGossip Message (UDP)Gossip Message (UDP)(from Lecture 1)9Epidemic Multicast (Push) Protocol Protocol roundsrounds (local clock) (local clock) b b random targets per roundrandom targets per round UninfectedUninfected InfectedInfectedGossip Message (UDP)Gossip Message (UDP)10Epidemic Multicast (Pull) Protocol Protocol roundsrounds (local clock) (local clock) b b random targets per roundrandom targets per round UninfectedUninfected InfectedInfectedGossip Message (UDP)Gossip Message (UDP)11Pull > Push•Pull converges faster than push, thus providing better delay•Push-pull hybrid variant possible (see Karp and Shenker’s “Randomized Rumor Spreading”)pi1pi2pi1pi11nn1piPullPushpi – Probability that a node is susceptible after the ith round12Anti-entropy: Optimizations•Maintain checksum, compare databases if checksums unequal•Maintain recent update lists for time T, exchange lists first•Maintain inverted index of database by timestamp; exchange information in reverse timestamp order, incrementally re-compute checksums13Epidemic Flavors•Blind vs. Feedback–Blind: lose interest to gossip with probability 1/k every time you gossip–Feedback: Loss of interest with probability 1/k only when recipient already knows the rumor•Counter vs. Coin–Coin: above variants–Counter: Lose interest completely after k unnecessary contacts. Can be combined with blind.•Push vs. Pull14Deletion and Death Certificates•Absence of item does not spread; On the contrary, it can get resurrected!•Use of death certificates (DCs) – when a node receives a DC, old copy of data is deleted•How long to maintain a DC?–Typically twice (or some multiple of) the time to spread the information–Alternately, use Chandy and Lamport snapshot algorithm to ensure all nodes have received–Certain sites maintain dormant DCs for a longer duration; re-awakened if item seen again15Performance Metrics•Residue: Fraction of susceptibles left when epidemic finishes•Traffic: (Total update traffic) / (No. of sites)•Delay: Average time for receiving update and maximum time for receiving update•Some results:–Counters and feedback improve delay–Pull provides lower delay than push16Performance EvaluationTipping Point Behavior17DiscussionPick your favorite:•Push vs. pull vs. push-pull–Name one disadvantage of each•Direct mail vs. anti-entropy vs. rumor mongering–Name one disadvantage of each•Random neigbhor picking–Disadvantage in wired networks?–In Sensor network?18Bimodal MulticastKenneth P. Birman et. al.ACM TOCS 1999[Some slides borrowed from presentation by: W. Fagen and L. Cook]19“Traditional” Multicast Protocols20Vs. Pbcast•Atomicity: All or none delivery •Multicast stability: Reliable immediately delivery of messages•Scalability: Bad. Costs >= quadratic with group size.•Ordering•Atomicity: Bimodal delivery guarantee, almost all or almost none (immediately)•Multicast stability: Reliable eventual delivery of messages•Scalability: Costs logarithmic w.r.t. network size. Throughput stability.•OrderingTraditional Multicast Pbcast21Pbcast: Probabilistic Broadcast Protocol•Pbcast has two stages:1. Unreliable, hierarchical, best-effort broadcast. Eg. IP Multicast2. Two-phase anti-entropy protocol: runs simultaneously with the broadcast messages•First phase detects message loss•Second phase corrects such losses22The second stage•Anti-entropy round:–Gossip Messages:•Each process chooses another random process and sends a summary of its recent messages–Solicitation Messages:•Messages sent back to the sender of the gossip message requesting a resend of a given set of messages (not necessarily the original
View Full Document
Unlocking...