|
|
|
In 1976, people were just starting to think about how distributed transactions and replication could be added to a database system. I believe the first good paper on the topic -- and still one of the best -- was Bob Thomas' ``A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases.'' It was first published in 1976 as a Bolt Beranek and Newman technical report, and was widely distributed in that form. The paper introduced two very important ideas that are much used today. First, it defined majority consensus as a way to determine which processes are available in the face of communications failures. This was later extended by Dave Gifford to be a weighted majority, or quorum. Most practical process failure detection algorithms today use this technique. Second, it introduced the use of timestamps to tag transactions, updates, and data items. The timestamp-based rule that bears his name allows updates to propagate in any order, yet all replicas of a data it! em will eventually converge to the same value. Today, this technique is used in most of the world's directory services, and in some multi-master replication algorithms for database systems.
The paper was very influential on early work on distributed transactions and replication, particularly on mine. The timestamping approach motivated our work on the SDD-1 distributed DBMS at Computer Corporation of America (gone, but not forgotten). It was also a challenge when developing serializability theory, as replication and majority consensus were aspects that a complete theory had to account for. It motivated some of Leslie Lamport?s early work on reliable distributed computing. Moreover, the many multi-master replication algorithms that use timestamp vectors are direct descendants of this algorithm. Judged by density of new ideas and influence on both research and products, this is one of my favorite papers in the transaction literature.
Copyright © 1999 by the author(s). Review published with permission.