Player-centric byzantine agreement

Martin Hirt*, Vassilis Zikas

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Most of the existing feasibility results on Byzantine Agreement (BA) are of an all-or-nothing fashion: in Broadcast they address the question whether or not there exists a protocol which allows any player to broadcast his input. Similarly, in Consensus the question is whether or not consensus can be reached which respects pre-agreement on the inputs of all correct players. In this work, we introduce the natural notion of player-centric BA which is a class of BA primitives, denoted as , parametrized by subsets of the player set. For each primitive the validity is defined on the input(s) of the players in . Broadcast (with sender p) and Consensus are special (extreme) cases of primitives for and , respectively. We study feasibility of in the presence of a general (aka non-threshold) mixed (active/passive) adversary, and give a complete characterization for perfect, statistical, and computational security. Our results expose an asymmetry of Broadcast which has, so far, been neglected in the literature: there exist non-trivial adversaries which can be tolerated for Broadcast with sender some but not for some other being the sender. Finally, we extend the definition of by adding fail corruption to the adversary's capabilities, and give exact feasibility bounds for computationally secure (aka Consensus) in this setting. This answers an open problem from ASIACRYPT 2008 concerning feasibility of computationally secure multi-party computation in this model.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication38th International Colloquium, ICALP 2011, Proceedings
EditorsLuca Aceto, Monika Henzinger, Jiří Sgall
Place of PublicationBerlin, Heidelberg
Number of pages12
EditionPart 1
ISBN (Electronic)978-3-642-22006-7
ISBN (Print)978-3-642-22005-0
Publication statusPublished - 11 Jul 2011
Event38th International Colloquium on Automata, Languages and Programming - Zurich, Switzerland
Duration: 4 Jul 20118 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer, Berlin, Heidelberg
NumberPart I
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference38th International Colloquium on Automata, Languages and Programming
Abbreviated titleICALP 2011

Fingerprint Dive into the research topics of 'Player-centric byzantine agreement'. Together they form a unique fingerprint.

Cite this