Information Security and Cryptography Research Group

Towards a Theory of Consistency Primitives

Ueli Maurer

International Symposium on Distributed Computing — DISC 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 3274, pp. 379–389, Oct 2004.

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},
}

Files and Links