Global invariants under weak consistency

Developing applications that run correctly under weak consistency is challenging because the execution of concurrent updates may lead the application to an incorrect state.

To address this challenge, we proposed explicit consistency (aka just-right consistency), a novel consistency model where the state of all replicas always enforces a set of invariants specified by the application.

Additionally, we explored two complementary approaches to enforce explicit consistency.

First, a conflict-avoidance approach where the execution of operations that may lead to invariant-violation is controlled by a reservation system. Each replica can obtain reservations that allow it to execute operations locally.

Second, an invariant-preservation approach where operations are modified to guarantee that the execution of concurrent operations never leads to an invariant-violation. When no concurrent operation is executed, the modified version of the operations have the exact same effect on the database. When concurrent updates occur, the modifications guarantee that invariants are maintained in the final database state.

To help programmers develop applications using these approaches, we have developed

We have applied these ideas to implement AQL, a SQL interface for a NoSQL database, AntidoteDB, that enforces some of the most common SQL constraints: primary key, check and foreign key constraints.



Valter Balegas (FCT/UNL)
Sérgio Duarte (FCT/UNL)
Carla Ferreira (FCT/UNL)
Rodrigo Rodrigues (INESC/Id)
Nuno Preguiça (FCT/UNL)
Marc Shapiro (INRIA/LIP6)


This work is partially support by: EU SyncFree project, grant nº 609551, FCT/MCTES, project PEst-OE/EEI/UI0527/2013, NOVA LINCS and an AWS in Education Grant.


Copyright notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

ACM copyright: Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or

IEEE copyright: Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. Contact: Manager, Copyrights and Permissions / IEEE Service Center / 445 Hoes Lane / P.O. Box 1331 / Piscataway, NJ 08855-1331, USA. Telephone: + Intl. 732-562-3966.