[SOLVED] data structure algorithm 782

782
Credit: Distributed Systems: Concepts and Design, 5th Edition
George Coulouris, Cambridge University
Jean Dollimore, Formerly of Queen Mary, University of London TimKindberg,matter2media
Gordon Blair, Lancaster University
2012 | Pearson
18.4 Casestudiesofhighlyavailableservices: The gossip architecture, Bayou and Coda
In this section, we consider how to apply replication techniques to make services highly available. Our emphasis now is on giving clients access to the service with reasonable response times for as much of the time as possible, even if some results do not conform to sequential consistency. For example, the user on the train described at the beginning of this chapter may be willing to cope with temporary inconsistencies between copies of data such as diaries if they can continue to work while disconnected and fix any problems later.
In Section 18.3, we saw that fault-tolerant systems transmit updates to the replica managers in an eager fashion: all correct replica managers receive the updates as soon

SECTION 18.4 CASE STUDIES OF HIGHLY AVAILABLE SERVICES 785 In terms of our basic replication model, an outline of how a gossip service
processes queries and update operations is as follows:
l. Request: The front end normally sends requests to only a single replica manager at a time. However, a front end will communicate with a different replica manager when the one it normally uses fails or becomes unreachable, and it may try one or more others if the normal manager is heavily loaded. Front ends, and thus clients, may be blocked on query operations. The default arrangement for update operations, on the other hand, is to return to the client as soon as the operation has been passed to the front end; the front end then propagates the operation in the background. Alternatively, for increased reliability, clients may be prevented from continuing until the update has been delivered tof+ l replica managers, ensuring that it will be delivered everywhere despite up toffailures.
2. Update response: If the request is an update, then the replica manager replies as soon as it has received the update.
3.Coordination: Thereplicamanagerthatreceivesarequestdoesnotprocessituntil it can apply the request according to the required ordering constraints. This may involve receiving updates from other replica managers, in gossip messages. No other coordination between replica managers is involved.
4.Execution: Thereplicamanagerexecutestherequest.
5. Query response: If the request is a query, then the replica manager replies at this
point.
6. Agreement: The replica managers update one another by exchanging gossip messages, which contain the most recent updates they have received. They are said to update one another in a lazy fashion, in that gossip messages may be exchanged only occasionally, after several updates have been collected, or when a replica manager finds out that it is missing an update sent to one of its peers that it needs to process a request.
We now describe the gossip system in more detail. We begin by considering the timestamps and data structures that front ends and replica managers maintain in order to maintain update ordering guarantees. Then, in terms of these, we explain how replica managers process queries and updates. Much of the processing of vector timestamps needed to maintain causal updates is similar to the causal multicast algorithm of Section 15.4.3.