|
| Brown CS Spring 2008 CSCI 2950-X |
| Visit this group |
How do you allow dozens, hundreds, thousands of users to edit shared documents? How do you synchronize their changes? How do you cope with volunteers who don't commit, machines that aren't reliable, and simultaneous edits, i.e., the Internet? How do you do this with low space- and time-overhead?
The field of optimistic replication tackles these questions. It sits squarely between systems and theory, depending on the former to scope out the problem and constrain solutions, and the latter to ensure the solutions make sense.
This is a hot topic, with new results constantly appearing in print. We will study some classic literature, examine contemporary results, and then identify projects in which we attempt to make our own contributions.
DivaScheme: King, Pantel, Yoo
Static Reasoning: Gordon, McCorkle
Drawing: Bartholomew, Bascetincelik, Baskin (the Killer B's)
Middleware: Fischer, O'Donnell
Semantic Web-Browser: Barratt, Bromfield, Goldmints-Orlov, Guha (Mostly Killer B's)
|
Fischer and Michael
Sacrificing serializability to attain high availability of data in an unreliable network PODS 1982 link |
Herlihy
Apologizing vs. asking permission: optimistic concurrency control for abstract data types TODS 1990 link |
|
Terry, et al.
Session guarantees for weakly consistent replicated data PDIS 1994 formal link actual paper (flaky link, may need reloading) |
Terry, et al.
Managing update conflicts in Bayou, a weakly connected replicated storage system SOSP 1995 link |
|
Sun and Ellis
Operational transformation in real-time group editors: issues, algorithms, and achievements CSCW 1998 link |
|
Foster, et al.
Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem TOPLAS 2007 link |
|
Shapiro, Bhargavan, Krishna
A constraint-based formalism for consistency in replicated systems OPODIS 2004 link |
Shapiro, Bhargavan
The Actions-Constraints approach to replication: definitions and proofs MSR-TR-2004-14 link |
|
|
|
Oster, Molli, Urso, Imine
Tombstone transformation functions for ensuring consistency in collaborative editing systems CollaborateCom 2006 link |
Imine, Rusinowitch, Oster, Molli
Formal design and verification of operational transformation algorithms for copies convergence TCS 2006 link |