...
Design relies on an underlying distributed data sharing service, Sinfonia [1], which provides fault tolerance and a light-weight distributed atomic primitive. They provide 1) transactional access and 2) online migration of tree nodes. An Insert operation may have to split a B-tree node, which requires modifying the node (stored on one server) and its parent (stored possibly on a different server); clients use transactions to perform such modifications atomically, without having to worry about concurrency or locking protocols. If all comparisons succeed, the mini-transaction returns the contents of the locations specified by the read items and updates the locations specified by the write items with the specified data. Sinfonia uses a variant of two-phase commit to execute and commit mini-transactions in two phases.
...