Technical note: Replication graphs revisited

The article “Replication and consistency in a distributed environment” by Breitbart and Korth [Yuri Breitbart, Henry F. Korth, J. Comput. System Sci. 59 (1) (1999) 29–69] presents replication graphs as an efficient means to handle concurrency control in replicated databases.This technical note identifies and explains two inaccuracies in this article:•The basic global serializability-protocol BGS given by Breitbart and Korth [Yuri Breitbart, Henry F. Korth, Replication and consistency in a distributed environment, J. Comput. System Sci. 59 (1) (1999) 29–69] does not always guarantee serializability if combined with two-phase locking. We show that this problem can be avoided with a minor change to the protocol.•The theorem on minimal deadlock sets for the protocol BGS appears incorrect, and we give a counterexample to support this claim together with a brief discussion on the consequence of this. Please note that this does not affect the applicability of replication graphs as a concept.