  Modern distributed systems often rely on so called weakly-consistent
databases, which achieve scalability by sacrificing the consistency guarantee
of distributed transaction processing. Such databases have been formalised in
two different styles, one based on abstract executions and the other based on
dependency graphs. The choice between these styles has been made according to
intended applications: the former has been used to specify and verify the
implementation of these databases, and the latter to prove properties of
programs running on top of the databases. In this paper, we present a set of
novel algebraic laws (i.e. inequations) that connect these two styles of
specifications; the laws relate binary relations used in a specification based
on abstract executions, to those used in a specification based on dependency
graphs. We then show that this algebraic connection gives rise to so called
robustness criteria, conditions which ensures that a program running on top of
a weakly-consistent database does not exhibit anomalous behaviours due to this
weak consistency. These criteria make it easy to reason about programs running
on top of these databases, and may become a basis for dynamic or static program
analyses. For a certain class of consistency models specifications, we prove a
full abstraction result that connects the two styles of specifications.
