Towards a Theory of Consistency Primitives
Ueli Maurer
One of the classical results in the theory of distributed systems is the theorem by Lamport, Shostak, and Pease stating that among $n$ parties, any $t$ of which may be cheaters, one of the parties (the sender) can consistently broadcast a value to the other parties if and only if $t\leq n/3$. This is achieved by use of a protocol among the players, using bilateral channels. The purpose of this paper is to look at various generalizations of this result and to propose a new concept, called consistency specification, a very general type of consistency guarantee a protocol among $n$ parties $P_1, \dots, P_n$ can provide. A consistency specification specifies, for every possible set $H\subseteq\{P_1, \dots, P_n\}$ of honest players and for every choice of their inputs, a certain security guarantee, i.e., a consistency condition on their outputs. This models that security can degrade smoothly with an increasing number of cheaters rather than abruptly when a certain threshold is exceeded, as is the case in the previous literature.
BibTeX Citation
@inproceedings{Maurer04c,
author = {Ueli Maurer},
title = {Towards a Theory of Consistency Primitives},
editor = {R. Guerraoui},
booktitle = {International Symposium on Distributed Computing --- DISC 2004},
pages = 379--389,
series = {Lecture Notes in Computer Science},
volume = 3274,
year = 2004,
month = 10,
publisher = {Springer-Verlag},
}