New version page

UI CS 449 - Davis / Wakerly

Course: Cs 449-
Pages: 7
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly!The following discussion is based on a paper by Davis and Wakerly–Synchronization and Matching in Redundant Systems–IEEE Trans. on Computers–Vol. c-27, No 6, June 1978–This is an example of what can happen when one can make assumptions about the capabilities of components of the system!Main objective:–this is an old paper, but there are important messages, e.g.:»agreement can be “rolled out” in (or supported by) hardware»one can manipulate the fault assumptions1Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !Hardware aided solution–requires processors + extra hardware–Synchronizer modulevoter delay d2Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !processors with synchronizer modulesProc.AvoteProc.BvoteProc.CvoteS-moduleS-moduleS-module3Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !Configuration # of lanes # of stagesP1P2P3S11S12S13S21S22S23stagestagelane4Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !Simplex: Data Transition ErrorProc.AvoteProc.BvoteProc.Cvoteinputto Ato Bto C5Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly –Hardware Interstages = Broadcast Repeaters–Processors vote on multiple copies receivedProc.AvoteProc.BvoteProc.Cvoteinputto Ato Bto Cinterstageinterstageinterstage6Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly!Simplex–Case 1: Processor A is faulty (commander is traitor)»Interstages may receive different values»But: each interstage receives only ONE value»Each interstage correctly forwards the values received»Each processor receives the SAME three values»Majority votes are identical–Case 2: An Interstage is faulty (commander is loyal)»All interstages receive the same value from Processor A»Two correct interstages forward correct value»Each processor receives 2 correct values»2-of-3 majority7Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !Difference from OM(1) Algorithm–Processor Broadcast => Round 0 (initial broadcast)–Interstage Broadcast => Round 1 (rebroadcast)–Single-fault lies either in processor or in interstage, but not in both!»fault can not cause error in both rounds»therefore there is one error free round»same effect as discarding data in OM(1) algorithm»can thus achieve agreement without discarding data–Result: can achieve agreement with 3 processing lanes instead of 4 processors required by OM(1)–Disadvantage: requires extra hardware (stages)8Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !Multiplex Solution–Option 1: just replicate Simplex Solution»each interstage receives 3 messages and broadcasts 9 messages»each processor receives 9 values to vote uponProc.AvoteProc.BvoteProc.Cvoteinputto Ato Bto Cinterstageinterstageinterstageinputinput9Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly –Option 2: Install voters in interstages»each interstage receives 3 messages and broadcasts 3 messages»each processor receives 3 values to vote uponProc.AvoteProc.BvoteProc.Cvoteinputto Ato Bto C vote vote voteinputinput10Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly!Multiplex –Case 1: Processor A is faulty (commander is traitor)»Interstages may receive different values»Interstage may send different values»But: each interstage sends the same value to all processors»Each processor receives the SAME set of values»Majority votes are identical–Case 2: An Interstage is faulty (commander is loyal)»All interstages receive identical sets of values»Two interstages forward correct value to all processors»Each processor receives 2 correct values»All processors get the same majority11Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !Hardware Requirements–Number of Lanes (rows) = 3»need to get 2-of-3 majority–Number of Stages (columns) = 2»needed to assure one error free round»agreement is achieved at output of first non-faulty state.»once agreement is achieved, a minority of faulty nodes cannot disrupt it.12Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17 to Ato Bto Cto Dto EProc.AvoteProc.BvoteProc.CvoteinputinputinputProc.DvoteProc.Evoteinputinput vote vote vote vote vote vote vote vote vote voteTwo fault solution13Page: © 2009 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 17Davis / Wakerly !Summary Davis / Wakerly OM(t)messagesHW


View Full Document
Download Davis / Wakerly
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Davis / Wakerly and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Davis / Wakerly 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?