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
Loading...
Thumbnail Image
Name

Crime_and_Punishment___ICDCS_2022__Camera_Ready_.pdf

Type

Publisher

cris-layout.advanced-attachment.oaire.version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

License Condition

CC BY

Size

638.81 KB

Format

Adobe PDF

Checksum (MD5)

a092a11d239d2d8b048fc4b5039a461f

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