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