WARNING:
JavaScript is turned OFF. None of the links on this concept map will
work until it is reactivated.
If you need help turning JavaScript On, click here.
This Concept Map, created with IHMC CmapTools, has information related to: ch15 repl faul2, Fault-tolerant services Discussion of passive replication To survive f process crashes, f+1 RMs are required it cannot deal with byzantine failures because the client can't get replies from the backup RMs To design passive replication that is linearizable View synchronous communication has relatively large overheads Several rounds of messages per multicast After failure of primary, there is latency due to delivery of group view variant in which clients can read from backups which reduces the work for the primary get sequential consistency but not linearizability Sun NIS uses passive replication with weaker guarantees Weaker than sequential consistency, but adequate to the type of data stored achieves high availability and good performance Master receives updates and propagates them to slaves using 1-1 communication. Clients uses either master or slave updates are not done via RMs - they are made on the files at the master, The five phases in performing a client request are as follows: 1. Request: a FE issues the request, containing a unique identifier, to the primary RM 2. Coordination: the primary performs each request atomically, in the order in which it receives it relative to other requests it checks the unique id; if it has already done the request it re-sends the response. 3. Execution: The primary executes the request and stores the response. 4. Agreement: If the request is an update the primary sends the updated state, the response and the unique identifier to all the backups. The backups send an acknowledgement. 5. Response: The primary responds to the FE, which hands the response back to the client ???? This system implements linearizability, since the primary sequences all the operations on the shared objects If the primary fails, the system is linearizable, if a single backup takes over exactly where the primary left off, i.e.: the primary is replaced by a unique backup surviving RMs agree which operations had been performed at take over view-synchronous group communication can achieve this when surviving backups receive a view without the primary, they use an agreed function to calculate which is the new primary. The new primary registers with name service view synchrony also allows the processes to agree which operations were performed before the primary failed. E.g. when a FE does not get a response, it retransmits it to the new primary The new primary continues from phase 2 (coordination -uses the unique identifier to discover whether the request has already been performed., Fault-tolerant services Active replication - five phases in performing a client request Request FE attaches a unique id and uses totally ordered reliable multicast to send request to RMs. FE can at worst, crash. It does not issue requests in parallel Coordination the multicast delivers requests to all the RMs in the same (total) order. Execution every RM executes the request. They are state machines and receive requests in the same order, so the effects are identical. The id is put in the response Agreement no agreement is required because all RMs execute the same operations in the same order, due to the properties of the totally ordered multicast. Response FEs collect responses from RMs. FE may just use one or more responses. If it is only trying to tolerate crash failures, it gives the client the first response., Fault-tolerant services Passive (primary-backup) replication. Five phases The five phases in performing a client request are as follows: 1. Request: a FE issues the request, containing a unique identifier, to the primary RM 2. Coordination: the primary performs each request atomically, in the order in which it receives it relative to other requests it checks the unique id; if it has already done the request it re-sends the response. 3. Execution: The primary executes the request and stores the response. 4. Agreement: If the request is an update the primary sends the updated state, the response and the unique identifier to all the backups. The backups send an acknowledgement. 5. Response: The primary responds to the FE, which hands the response back to the client, Request FE attaches a unique id and uses totally ordered reliable multicast to send request to RMs. FE can at worst, crash. It does not issue requests in parallel Coordination the multicast delivers requests to all the RMs in the same (total) order. Execution every RM executes the request. They are state machines and receive requests in the same order, so the effects are identical. The id is put in the response Agreement no agreement is required because all RMs execute the same operations in the same order, due to the properties of the totally ordered multicast. Response FEs collect responses from RMs. FE may just use one or more responses. If it is only trying to tolerate crash failures, it gives the client the first response. ???? As RMs are state machines we have sequential consistency due to reliable totally ordered multicast, the RMs collectively do the same as a single copy would do it works in a synchronous system in an asynchronous system reliable totally ordered multicast is impossible – but failure detectors can be used to work around this problem. How to do that is beyond the scope of this course. this replication scheme is not linearizable because total order is not necessarily the same as real-time order To deal with byzantine failures For up to f byzantine failures, use 2f+1 RMs FE collects f+1 identical responses To improve performance, FEs send read-only requests to just one RM