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