Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Crime and Punishment in Distributed Byzantine Decision Tasks
 
conference paper

Crime and Punishment in Distributed Byzantine Decision Tasks

Civit, Pierre
•
Gilbert, Seth  
•
Gramoli, Vicent
Show more
2022
2022 Ieee 42Nd International Conference On Distributed Computing Systems (Icdcs 2022)
42nd IEEE International Conference on Distributed Computing Systems (ICDCS)

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, called tau(scr),( )of any non-synchronous distributed protocol solving a decision task into its accountable version. Our tau(scr) 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.

  • Files
  • Details
  • Metrics
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés