Random Notes

Search…

Theory

Operating System

Storage

Coordination

Fault Tolerance

Cloud Computing

Systems for ML

ML for Systems

Machine Learning

Video Analytics

Networking

Serverless

Resource Disaggregation

Edge Computing

Security/Privacy

Misc.

Session Guarantees for Weakly Consistent Replicated Data

http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/SessionGuaranteesBayou.pdf

TL;DR:

Session Guarantees provides a view of the database that is consistent with their own actions, even if read and write from various, potentially inconsistent servers.

Summary:

Eventually consistent systems are great in terms of availability. However, they may not be satisfactory for some applications seeking stronger guarantees. Session Guarantees[1] can easily be layered[2] on top of a weakly-consistent replicated data system. We assume the underlying systems are eventually consistent and symmetric, which means Reads and Writes may be performed at any server.

Definitions:

1) DB(S,t) is the ordered sequence of Writes that have been received by server S at or before time t.

2) RelevantWrites(S,t,R) denotes the function that returns the smallest set of Writes that is complete[3] for Read R and DB(S,t).

3) WriteOrder(W1,W2) be a boolean predicate indicating whether Write W1 should be ordered before Write W2.

[1] A session is an abstraction for the sequence of read and write operations performed during the execution of an application. For example, it could be a session which is created for each user and must exist for the lifetime of the user's account.

[2] They can be provided using vector clocks.

[3] We say a Write set WS is complete for Read R and DB(S,t) if and only if WS is a subset of DB(S,t) and for any set WS2 that contains WS and is also a subset of DB(S,t), the result of R applied to WS2 is the same as the result of R applied to DB(S,t).

Copy link

On this page

TL;DR:

Summary:

Definitions: