SKR 5302: Advanced Distributed Computing

8.3. The gossip architecture

The emphasis is on giving client 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. 

The gossip architecture

• Proposed by Ladin et al. [1992]
• Framework for implementing highly available services by replicating data close to the points where groups of clients need it. 
• The replica managers exchange ‘gossip’ messages periodically in order to convey the updates they have each received from clients. 
• It maybe used to create a highly available electronic bulletin board or diary service. 
• Two basic operations:
• Queries – read only operations
• Updates – modify but do not read the state
  
  

  Figure 5: Query and update operations in a gossip service
  

• Front ends send queries and updates to any replica manager they choose, provided it is available and can provide reasonable response times. 
• Two guarantees:
  • Each client obtains a consistent service over time
  • Relaxed consistency between replicas
• To support relaxed consistency, the gossip architecture supports causal update ordering. 
• Example: 
  • Consider an electronic bulletin board application, in which a client program executes on the user’s computer and communicates with a local replica manager. 
  • The client sends the user’s posting to the local replica manager and the replica manager sends new postings in gossip messages to other replica managers. 
  • Readers of bulletin boards experience slightly out-of-date lists of posted items, but this does not usually matter. 
  • Causal ordering could be used for posting items. 
  • General postings could appear in different orders at different replica managers but that, for example, a posting whose subject is ‘Re: oranges’ will always be posted after the message about ‘oranges’ to which it refers. 
  • Forced ordering could be used for adding a new subscriber to a bulletin board. 
• Outline of how a gossip service processes queries and update operations is as follows:
• Request: 
  • The front end normally sends requests to only a single replica manager at a time.
  • A front end will communicate with a different replica manager when the one it normally uses fails, becomes unreachable or heavily loaded. 
• Update response:
  • If the request is an update, then the replica manager replies as soon as it has received the update. 
• Coordination
  • The replica manager that receives a request does not process it until it can apply the request according to the required ordering constraints. 
  • This may involve receiving updates from other replica managers, in gossip messages. 
• Execution
• Query response
  • If the request is a query, then the replica manager replies at this point.
• Agreement
• The replica managers update one another by exchanging gossip messages, which contain the most recent updates they have received.
• Gossip messages may be exchanged only occasionally, after several updates have been collected, or when a replica manger finds out that it is missing an update sent to one of its peers that it needs to process a request.

The front end’s version timestamp

• In order to control the ordering of operation processing, each front end keeps a vector timestamp that reflects the version of the latest data values accessed by the front end. 
• This timestamp, denoted by prev.
• The front end sends it in every request message to a replica manager, together with a description of the query or update operation itself. 
• When a replica manager returns a value as a result of a query operation, it supplies a new vector timestamp (new).
• An update operation returns a vector timestamp (UpdateID) that is unique to the update. 
• Each returned timestamp is merged with the front end’s previous timestamp to record the version of the replicated data that has been observed by the client. 
• Clients exchange data by accessing the same gossip service and by communicating directly to one another. 
  

  
  Figure 6: Front ends propagate their timestamps
  whenever clients communicate directly
  

Replica manager state

• Value:
  • Value of the application state as maintained by the replica manager.
  • Replica manager is a state machine, which begins with a specified initial value and is thereafter solely the result of applying update operations to that state.
• Value timestamp:
  • Vector timestamp that represents the updates that are reflected in the value. 
  • Contain one entry for every replica manager.
  • Updated whenever an update operation is applied to the value. 
• Update log:
• All update operations are recorded in this log as soon as they are received. 
• Replica manager keeps updates in a log because:
• The replica manager cannot yet apply the update because it is not yet stable. Stable update – the one that may be applied consistently with its ordering guarantees. 
• Even though the update has become stable and has been applied to the value, the replica manager has not received confirmation that this update has been received at all other replica managers. 
• In the meantime, it propagates the update in gossip messages. 

• Replica timestamp:
  • Vector timestamp that represents those updates that have been accepted by the replica manager – that is, placed in the manager’s log. 
  • Differs from the value timestamp in general, because not all updates in the log are stable. 

• Executed operation table:
  • The same update may arrive at a given replica manager from a front end and in gossip messages from other replica managers. 
  • To prevent an update being applied twice, the ‘executed operation’ table containing the unique front-end-supplied identifiers of updates that have been applied to the value. 
  • The replica managers check this table before adding an update to the log.
• Timestamp table:
• Vector timestamp for each other replica manager, filled with timestamps that arrive from them in gossip messages. 
• Replica managers use the table to establish when an update has been applied at all replica managers.
  
  

  Figure 7: A gossip replica manager,
  showing its main state components
  

Discussion of the gossip architecture

• Aimed at achieving high availability for services. 
• Ensures that clients can continue to obtain a service even when they are partitioned from the rest of the network, as long as at least one replica manager continues to function in their partition. 
• For objects such as bank accounts, where sequential consistency is required, it is not suitable as it enforcing relaxed consistency. 
  • Fault tolerant system should be much better. 
• Its lazy approach to update propagation makes it inappropriate for updating replicas in near-real time. 
  • Multicast-based system would be more appropriate.
• Scalability issue
  • As the number of replica managers grows, the number of gossip messages and the size of the timestamps used grow.