1983 1995 Thinking Consistency Detection of Mutual Inconsistency in Distributed Systems Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System Brewer's conjecture & the feasibility of consistent, available, partition-tolerant web services 2002
2015 2011 Conflict-free replicated Data Types Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity Thinking Consistency
High availability “In some environments it is desirable or necessary to permit users to continue modifying resources such as files when the network is partitioned”
Version Vectors “A Version Vector for a file f is a sequence of n pairs, where n is the number of sites at which f is stored … the ith vector entry counts the number Vi of updates to f made at site Si”
Conflict Resolution “A conflict detection mechanism, while valuable, has increased effect if there is also a method for reconciling conflicts automatically”
Bayou Summary System designed for weak connectivity Eventual consistency via application- defined dependency checks and developer defined merge procedures Epidemic algorithms to replicate state
Feral mechanisms for keeping DB integrity Application-level mechanisms Analyzed 67 open source Ruby on Rails Applications Unsafe > 13% of the time (uniqueness & foreign key constraint violations)
Concurrency control is hard! Availability is important to application developers Home-rolling your own concurrency control or consensus algorithm is very hard and difficult to get correct!
Eventual Consistency We want highly available systems so we must use weaker forms of consistency (remember CAP) Application semantics helps us make better tradeoffs Do not recreate the wheel, leverage existing research allows us to not repeat past mistakes Forced into a feral world but this may change soon! Tl;DR