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. The Disagreement Power of an Adversary
 
conference paper

The Disagreement Power of an Adversary

Delporte-Gallet, Carole
•
Fauconnier, Hugues
•
Guerraoui, Rachid  
Show more
2009
Proceedings of the 23rd International Symposium on Distributed Computing
23rd International Symposium on 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 the remaining (2^2^n - n) adversaries that might crash certain combination of processes and not others? This paper presents a precise way to characterize such adversaries by introducing 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 how this notion enables to derive n equivalence classes of adversaries.

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

disc2009.pdf

Access type

openaccess

Size

213.63 KB

Format

Adobe PDF

Checksum (MD5)

4c568e4dbb7aee8fe80b7c911acda114

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