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. Journal articles
  4. The disagreement power of an adversary
 
research article

The disagreement power of an adversary

Delporte-Gallet, Carole
•
Fauconnier, Hugues
•
Guerraoui, Rachid  
Show more
2011
Distributed Computing

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where t processes can crash is exactly t + 1. In other words, an adversary that can crash any subset of size at most t can prevent the processes from agreeing on t values. But what about all the other 22n−1−(n+1) adversaries that are not uniform in this sense and might crash certain combination of processes and not others? This paper presents a precise way to classify all adversaries. We introduce the notion of disagreement power: the biggest integer k for which the adversary can prevent processes from agreeing on k values. We show how to compute the disagreement power of an adversary and derive n equivalence classes of adversaries.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

the_disag_pow_of_ad_2Fs00446-010-0122-4.pdf

Type

Publisher's Version

Version

Published version

Access type

openaccess

Size

285.12 KB

Format

Adobe PDF

Checksum (MD5)

3be1d59da12ee4667257decf83941f1d

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