Update Propagation in Distributed System

Update Propagation

• A comparison between push-based and pull-based protocols in the case of multiple client, single server system

Epidemic Protocols

• Update propagation for systems that only need eventual consistency
• Randomized approaches based on the theory of epidemics
• Infective, susceptible and removed servers
• Anti-entropy propagation model
• A server P picks another server Q at random, and exchanges updates
• Three approaches
• P only pushes updates to Q
• P only pulls new updates from Q
• P and Q send updates to each other
• If many infective servers, pull-based approach is better
• If only one infective server, eitehr approach will eventually propagate all updates
• Rumor spreading (Gossiping) will speed up propagation
• If server P has been updated, it randomly contacts Q and tries to push the update to Q, if Q was already updated by another server, with some probability (1/k), P loses interest in spreading the update any further

The Gossip System

• Guarantees
• Each client obtains a consistent service over time
• i.e., replica managers only provide a client with data that reflect the updates the client has observed so far
• Relaxed consistency between replicas
• Primarily causal consistency, but support also provided for sequential consistency
• Choice up to the application designer
• Procedure
• Request
• Front Ends sends a query or update request to a replica manager that is reachable
• Update Response
• RM replies as soon as it receives updates
• Coordination
• RM does not process the request until it can meet 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, the RM replies at this point
• Agreement
• The replica managers update each other by exchanging gossip messages, which contains the most recent updates they have received
• This is one in lazy fashion
• Query and update operations in a gossip service

• Front ends propagate their timestamps whenever clients communicate directly

• A gossip replica manager, showing its main state components

Bayou: Eventual Consistency

• If no updates take place for a long time, all replicas will gradually become consistent
• Domain specific conflict detection and resolution
• Appropriate for applications like shared calendars

Motivation for eventual consistency

• Sequential consistency requires that at every point, every replica has a value that could be the result of the global-agreed sequential application of writes
• This does not require that all replicas agree at all times, just that they always take on the same sequence of value
• Writes
• When they arrive, are applied in the same order at all replicas
• Easily done with timestamps

Conflict Resolution

• Dealing with inconsistency
• Every Bayou update contains a dependency check and a merger procedure in addition to the operation's specification
• Replication not transparent to application
• Only the application knows how to resolve conflicts
• Split of responsibility
• Replication system
• Propagate updates
• Application
• resolve conflicts
• Optimistic application of writes require that writes be "undoable"

Rolling Back Updates

• Keep log of updates
• Order by timestamp
• When  a new update comes in, place it in the correct order and repapply log of updates
• Need to establish when you can truncate the log
• Requires old updates to be "committed", new ones tentative
• Committed order can be achieved by designing a replica manager as the primary replica manager