Abstract
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≤ 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,..., P n can provide. A consistency specification specifies, for every possible set H⊆{P 1,..., 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aschwanden, R.: Diploma Thesis, Dept. of Computer Science, ETH Zurich (May 2001)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. 20th ACM Symposium on the Theory of Computing (STOC), pp. 1–10 (1988)
Chaum, D., Crépeau, C., Damgård, I.: Multi-party unconditionally secure protocols (extended abstract). In: Proc. 20th ACM Symposium on the Theory of Computing (STOC), pp. 11–19 (1988)
Considine, J., Fitzi, M., Franklin, M., Levin, L.A., Maurer, U., Metcalf, D.: Byzantine agreement in the partial broadcast model (July 2004) (manuscript)
Fitzi, M., Gottesman, D., Hirt, M., Holenstein, T., Smith, A.: Detectable Byzantine agreement secure against faulty majorities. In: Proc. 21st ACM Symposium on Principles of Distributed Computing (PODC) (July 2002)
Fitzi, M., Hirt, M., Holenstein, T., Wullschleger, J.: Two-threshold broadcast and detectable multi-party computation. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 51–67. Springer, Heidelberg (2003)
Fitzi, M., Hirt, M., Maurer, U.: General adversaries in unconditional multi-party computation. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 232–246. Springer, Heidelberg (1999)
Fitzi, M., Maurer, U.: Efficient Byzantine agreement secure against general adversaries. In: Kutten, S. (ed.) DISC 1998. LNCS, vol. 1499, pp. 134–148. Springer, Heidelberg (1998)
Fitzi, M., Maurer, U.: From partial consistency to global broadcast. In: Proc. 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), pp. 494–503. ACM Press, New York (2000)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game — a completeness theorem for protocols with honest majority. In: Proc. 19th ACM Symposium on the Theory of Computing (STOC), pp. 218–229 (1987)
Hirt, M., Maurer, U.: Complete characterization of adversaries tolerable in secure multi-party computation. In: Proc. 16th ACM Symposium on Principles of Distributed Computing (PODC), August 1997, pp. 25–34 (1997)
Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Transactions on Programming Languages and Systems 4, 382–401 (1982)
Kuhn, F., Strobl, R.: Towards a general theory for consistency primitives. Term project report, Dept. of Computer Science, ETH Zurich (November 2000)
Maurer, U.: Secure multi-party computation made simple. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 14–28. Springer, Heidelberg (2003)
Rabin, T., Ben-Or, M.: Verifiable secret-sharing and multiparty protocols with honest majority. In: Proc. 21st ACM Symposium on the Theory of Computing (STOC), pp. 73–85 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maurer, U. (2004). Towards a Theory of Consistency Primitives. In: Guerraoui, R. (eds) Distributed Computing. DISC 2004. Lecture Notes in Computer Science, vol 3274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30186-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-30186-8_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23306-0
Online ISBN: 978-3-540-30186-8
eBook Packages: Springer Book Archive