{small lecturenumber - heblocknumber :} Consensus and agreementaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Coordination via emailaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Failure modelsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Failure detectionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Failure detectionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Failure detectionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Multicast: a brief digressionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} What is multicast?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Multicast groupsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: centralized serveraddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: centralized serveraddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: token ringaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: token ringaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: multicastaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: multicastaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: multicastaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Mutual exclusion: multicastaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Dealing with failuresaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Election algorithmsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Choosing a leaderaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Ring-based election algorithmsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Ring-based election algorithmsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Ring-based election algorithmsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Bully algorithmaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Bully algorithmaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Consensusaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Consensusaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Consensusaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Byzantine generalsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Consensus in synchronous systemsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Byzantine generals in a synchronous systemaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Byzantine generals in an asynchronous systemaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} What do we do in practice?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Summarizingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Summaryaddtocounter {blocknumber}{1}Distributed Software DevelopmentConsensusChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p.1/??7-0: Consensus and agreementA fundamental problem in distributed systems is getting aset of processes or nodes to agree on one or more values.Is a procedure continuing or aborted?What value is stored in a distributed database?Which process is serving as coordinator?Has a node failed?There are a set of related problems that require a set ofprocesses to coordinate their states or actions.Department of Computer Science — University of San Francisco – p.2/??7-1: Coordination via emailAn example:Two people (A and B) want to meet at dusk tomorrowevening at a local hangout.Each wants to show up only if the other one will bethere.They can send email to each other, but email may notarrive.Can either one guarantee that the other will be there?Department of Computer Science — University of San Francisco – p.3/??7-2: Failure modelsWe’ll want to distinguish what sorts of failures thesealgorithms can tolerate.No failureSome of the algorithms we’ll see can’t tolerate a failure.Crash failureThis means that a node stops working and fails torespond to all messages.Byzantine failureA node can exhibit arbitrary behavior.This makes things pretty hard for us ...Department of Computer Science — University of San Francisco – p.4/??7-3: Failure detectionHow can we detect whether a failure has happened?A simple method:Every t seconds, each process sends an “I am alive”message to all other processes.Process p knows that process q is either unsuspected,suspected, or failedIf p sees q’s message, it knows q is alive, and sets itsstatus to unsuspected.What if it doesn’t receive a message?Department of Computer Science — University of San Francisco – p.5/??7-4: Failure detectionDepends on our communication model.Synchronous communication: if after d seconds (where dis the maximum delay in message delivery) we haven’treceived a message from p, p has failed.Ansychronous or unreilable communication: if themessage is not received, we can say that p is suspectedof failure.Department of Computer Science — University of San Francisco – p.6/??7-5: Failure detectionOther problems:What if d is fairly large?We can think processes are still running that have infact crashed.This is what’s called an unreliable failure detector.It will make mistakes, but, given enough information, itmay still be of use.Can provide hints and partial information.As we look at different algorithms, we’ll need to thinkabout whether we can detect that a process has failed.Department of Computer Science — University of San Francisco – p.7/??7-6: Multicast: a brief digressionThe Couloris chapter talks quite a bit about how to achivedifferent properties with multicast communication.Reliable multicastOrdered multicastFIFO orderingTotal orderingCausal orderingThe punchline: Totally ordered multicast is equivalent tothe consensus problem.Implementing one or more of these on top of IP multicastcould be a cool final
View Full Document
Unlocking...