SKR 5302: Advanced Distributed Computing

System model

• Data in the system consist of a collection of items called objects. 
• An ‘object’ could be a file (example: Java object).
• Each such logical object is implemented by a collection of physical copies called replicas. 
• Replicas are physical objects, each stored at a single computer, with data and behaviour that are tied to some degree of consistency by the system’s operation. 
• The ‘replicas’ of a given object are not necessarily identical, at least not at any particular point in time. 
• Some replicas may have received updates that others have not received. 
• Assume that an asynchronous system in which processes may fail only by crashing. 
• Involves replicas held by distinct replica managers – components that contain the replicas on a given computer and perform operations upon them directly.  
• Replica manager applies operations to its replicas recoverably. 
  • An operation at a replica manager does not leave inconsistent result if it fails part way through.
• A replica manager applies operations to its replicas atomically. 
• The state of the replicas is a deterministic function of their initial states and the sequence of operations that it applies to them. 
• The set of replica managers may be static or dynamic. 
• In a dynamic system
  • New replica managers may appear.
  • Replica managers may crash, then they are then deemed to have left the system (may be replaced).
• In a static system
  • Replica managers do not crash.
  • But they may cease operating for an indefinite period. 
• A collection of replica managers provides a service to clients. 
• Each client’s request are first handled by a component called a front end. 
• Front end: 
• to communicate by message passing with one or more of the replica managers.
• Making replication transparent. 
  
  

  Figure 1: A basic architectural model for the management of replicated data
  

Five phases are involved in the performance of a single request upon the replicated objects

• Requests: 
  • The front end issues the request to one or more replica managers.
• Coordination:
  • The replica managers coordinate in preparation for executing the request consistently. 
  • They decide on the ordering of this request relative to others. 
• Execution
  • The replica managers execute the request – perhaps tentatively: they can undo its effect later.
• Agreement
  • The replica managers reach consensus on the effect of the request – if any – that will be committed. 
• Response
• One or more replica managers responds to the front end. 
• The front end pass back the response to the client.

The role of group communication

• Requirement for dynamic membership where processes join and leave the group as the system executes.
• Users may add or withdraw a replica manager, or a replica manager may crash and thus need to be withdrawn from the system’s operation. 
• Fault-tolerant system – systems that can adapt as processes join, leave and crash – require more advanced features in failure detection and notification of membership changes. 
• Group views
  • List of the current group members, identified by their unique process identifiers.
  • The list is ordered
    • Example: according to the sequence in which the members joined the group.
  • New group view is generated each time that a process is added or excluded. 

• Process is suspended
  • Group membership service exclude it. 
  • The process is not crashed.
  • Might be communication failure -> process unreachable but it continues to execute normally. 
  • Effect of exclusion:
  • No messages will be delivered to that process
  • If that process becomes connected again, any messages it attempts to send will not be delivered to the group members. 
  • The process have to re-join the group (obtain new identifier), or abort its operation. 
  • However, false suspicion may reduce the group’s effectiveness.
  • Design challenge
    • Ensure that a system based on group communication does not behave incorrectly if a process is falsely suspected. 

For network partitions, group management differ in whether they are primary-partition or partitionable. 

Primary-partition

• The management service allows at most one subgroup (a majority) to survive a partition
• The remaining processes are informed that they should suspend operations.
• Appropriate in the case where the processes manage important data and the costs of inconsistencies between two or more subgroups is high. 

Partitionable

• Acceptable for two or more subgroups to continue to operate
• Example: 
• An application in which users hold an audio or video conference to discuss some issues. 
• Maybe acceptable for two or more subgroups of users to continue their discussion independently despite a partition.
• They can merge their results when the partition heals and the subgroups are connected again. 

View delivery

• For each group g the group management service delivers to any member process p  g a series of views vo(g), v1(g), v2(g), etc. 
• For example: a series of views could be vo(g) = (p), v1(g) = (p, p’) and v2(g) = (p) – p joins an empty group, then p’ joins the group, then p’ leaves it. 
• Although several membership changes may occur concurrently, the system imposes an order on the sequence of views given to each process. 
• Basic requirement for view delivery
• Order: if a process p delivers view v(g) and then view v’(g), then no other process q ≠ p delivers v’(g) before v(g).
• Integrity: if process p delivers view v(g), then p \( \in \) v(g).
• Non-triviality: If process q joins a group and is or becomes indefinitely reachable from process p ≠ q, then eventually q is always in the views that p delivers. Similarly, if the group partitions and remains partitioned, then eventually the views delivered in any one partition will exclude any processes in another partition.

View-synchronous group communication

• For simplicity, assume partitions may not occur.
• Makes guarantees additional to those above about the delivery ordering of view notifications with respect to the delivery of multicast messages. 
• The guarantees:
  • Agreement: Correct processes deliver the same sequence of views (starting from the view in which they join the group) and the same set of messages in any given view. That is, if a correct process delivers message m in view v(g), then all other correct processes that deliver m also do so in the view v(g). 
  • Integrity: If a process p delivers message m, then it will not deliver m again. 
  • Validity: Correct process always deliver the messages that they send. Let p be any correct process that delivers message m in view v(g). If some process q \( \in \) v(g) does not deliver m in view v(g), then the next view v’(g) that p delivers has q \( \notin \) v’(g). 
    
    

    Figure 2: View-synchronous group communication