Paper 2022/121

Crime and Punishment in Distributed Byzantine Decision Tasks (Extended Version)

Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, and Adi Serendinschi


A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. A distributed protocol solves a decision task if it enables processes to produce admissible output values despite arbitrary (Byzantine) failures. Unfortunately, it has been known for decades that many decision tasks cannot be solved if the system is overly corrupted, i.e., safety of distributed protocols solving such tasks can be violated in unlucky scenarios. By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes irrevocably detect some faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity. In this paper, we propose a generic transformation of any non-synchronous distributed protocol solving a decision task into its accountable version. Our transformation is built upon the well-studied simulation of crash failures on top of Byzantine failures and increases the communication complexity by a quadratic multiplicative factor in the worst case.

Available format(s)
Publication info
Published elsewhere. Major revision. 42nd IEEE International Conference on Distributed Computing Systems
accountabilityByzantine fault detectiondistributed tasks
Contact author(s)
pierrecivit @ gmail com
2022-04-25: last of 2 revisions
2022-02-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pierre Civit and Seth Gilbert and Vincent Gramoli and Rachid Guerraoui and Jovan Komatovic and Zarko Milosevic and Adi Serendinschi},
      title = {Crime and Punishment in Distributed Byzantine Decision Tasks (Extended Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2022/121},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.