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