# 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\pp P_n$ can provide. A consistency
specification specifies, for every possible set $H\subseteq\{P_1\pp
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.