Correctness conditions for highly available replicated databases
Nancy Ann Lynch, Barbara T. Blaustein, Michael D. Siegel · 1986
C<,retoness conditicms arc given which describe some nf tile pt'tq~crlie~ c×hibiLed by Ilighly aw~itable distributed database systems sttch a:; the 511,'x.RI) (Systcnl I~n' l lighly Available Replicated Data) ,¢.ystem cuurcntlv be~hg developed at Comptller Corporation of /~l]lOi'iC;i.This svslcm allows a da~d~ase application to contilme OpClatlt:~l ill tile lace o1" communicatiun faih.llCS,incheding fietwork pa0"tidons.A penalty is paid tbr thir; c×tz'a availability: the usual corrc,:tncss conditi,n,~; serializability of tr:msactions and preservation of iritcgrily c,n.~traims, ,:re not guaranteed.I Iowevcr, it is still possihle to make intcrestin~g claims about the beh,vior e,f the system.The kinds of claims whicli can be 9roved include bom~ds on tile costs oF violatior, of integrity cofistraints, and Ihirness guma,tces.In comrast to serializ~bility:s all-or-m~thing character, this work has a "continuous" flavor:small changes in available inform~itiou lead a) small perturbations in corrcctuess conditk)ns."['l:.iswork is novel, because there has been very little previous success in'stating .inlcresti'ngproperties whk:h are guaranteed by nonscrializable systems.