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

    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