Asynchronous ConsensusOutline of talkDistributed Computing ModelsAsynchronous network modelAn asynchronous networkSlide 6Slide 7Justification?ParadigmsConsensus problemSlide 11Fault-toleranceIf some process stays up…If one process stays upAlgorithmAnother algorithmFLP resultBasic ideaSlide 19Transitions between configurationsBasic LemmaSlide 22Main resultBasic FLP theoremSlide 25Single step decidesSlide 27Notes on FLPFLP intuitionKey insightFLP and our first algorithmFLP in the real worldChandra/TouegChandra/Toueg IdeaSample propertiesSlide 36A sampling of failure detectorsPerfect Detector?Example of a failure detectorW: Weakest failure detectorRotating a token versus 2-phase commitSlide 42Set of problems solvable in:Building systems with WWould we want to?French ATC system (simplified)Potential applicationsBroad conclusions?Value of FLP/ConsensusNature of debateAsynchronous ConsensusKen BirmanOutline of talkReminder about modelsAsynchronous consensus: Impossibility resultSolution to the problemWith an “oracle” that detects failuresWithout oracles, using timeoutBig issues? Revisit from Byzantine agreementIs this model realistic? In what ways is it “legitimate”?Should we focus on impossibility, or “possibility”?Asynchronous consensus in real world systemsDistributed Computing ModelsRecall that we had two modelsTo reason about networks and applications we need to be precise about the setting in which our protocols runBut “real world” networks are very complexThey can drop packets, or reorder themIntruders might be able to intercept and modify dataTiming is totally unpredictableAsynchronous network modelAsynchronous because we lack clocks:Network can arbitrarily delay a messageBut we assume that messages are sequenced and retransmitted (arbitrary numbers of times), so they eventually get through.“Free” to say: lossless, orderedNo value to assumptions about process speedFailures in asynchronous model?Usually, limited to process “crash” faultsIf detectable, we call this “fail-stop” – but how to detect?An asynchronous networkNot causal!An asynchronous networkTime shrinks…An asynchronous networkTime shrinks…Time stretches…Justification?If we can do something in the asynchronous model, we can probably do it even better in a real networkClocks, a-priori knowledge can only help…But today we will focus on an impossibility resultBy definition, impossibility in this model means “xxx can’t always be done”ParadigmsFundamental problems, the solution of which yields general insight into a broad class of questionsIn distributed systems:Agreement (on value proposed by a leader)Consensus (everyone proposes a value… pick one)Electing a leaderAtomic broadcast/multicast (send a message, reliably, to everyone who isn’t faulty, such that concurrent messages are delivered in the same order everywhere)Deadlock detection, clock or process synchronization, taking a snapshot (“picture”) of the system state….Consensus problemModels distributed agreementComes in various forms (with subtle differences in the associated results)!With a leader: leader gives an order, like “attack”, and non-faulty participants either attack or do nothing, despite some limited number of failures: Byzantine AgreementWithout a leader: participants have an initial vote; protocol runs and eventually all non-faulty participants chose the same outcome, and it is one of the initial votes (typically, 0 or 1): Fault-tolerant ConsensusConsensus problemP0Q0R1P1Q1R1Fault-toleranceGoal: an algorithm tolerant of one failureFailure: process crashes but this is not detectableSo the algorithm must work both in the face of arbitrary message delay caused by the network, and in the event of a single failureIf some process stays up…Suppose we knew that P won’t failThen P could simply broadcast it’s inputAll would “decide” upon this valueSolves the problemIf one process stays upIndeed, suppose that P stays up only long enough to send one messageBut there is only one failureAnd we knew that P would “lead”Then we can relay P’s message, using an all-to-all broadcastAlgorithmP: broadcast my inputQ  P: on receiving P’s message for first time, broadcast a copyTolerates anything except failure of P in the first step, but we need to agree upon “P” before starting (ie P is the least ranked process, using alphabetic ranking)Another algorithmAll processes start by broadcasting own value to all other processesIf we know that there is always exactly one failure, could wait until n-1 messages received, then using any deterministic ruleBut doesn’t work if sometimes we have one failure, sometimes noneFLP resultConsiders general caseAssumes an algorithm that can decide with zero or one failuresProves that this algorithm can be prevented from reaching decision, indefinitelyBasic ideaThink of system state as a “configuration”Configuration is v-valent if decision to pick v has become inevitable: all runs lead to vIf not 0-valent or 1-valent, configuration is bivalentInitial configuration includesAt least one 0-valent: {0,0,0….0}At least one 1-valent: {1,1,1…..1}At least one bivalent: {0,0,…1,1}Basic idea0-valentconfigurations1-valentconfigurationsbi-valentconfigurationsTransitions between configurationsConfiguration is a set of processes and messagesApplying a message to a process changes its state, hence it moves us to a new configurationBecause the system is asynchronous, can’t predict which of a set of concurrent messages will be delivered “next”But because processes only communicate by messages, this is unimportantBasic LemmaSuppose that from some configuration C, the schedules 1, 2 lead to configurations C1 and C2, respectively.If the sets of processes taking actions in 1 and 2, respectively, are disjoint than 2 can be applied to C1 and 1 to C2, and both lead to the same configuration C3Basic Lemma2C1C3CC2211Main resultNo consensus protocol is totally correct in spite of one faultNote: Uses total in formal sense (guarantee of termination)Basic FLP theoremSuppose we are in a bivalent configuration now and later will enter a univalent configurationWe can draw a form of frontier, such that a single message to