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. Reports, Documentation, and Standards
  4. Early Local Decisions in Distributed Agreement
 
report

Early Local Decisions in Distributed Agreement

Dutta, Partha  
•
Guerraoui, Rachid  
•
Pochon, Bastian
2003

When devising a distributed agreement algorithm, it is common to minimize the time complexity of global decisions, which is typically measured as the number of communication rounds needed for all correct processes to decide. In practice, what we might want to minimize is the time complexity of local decisions, which we define as the number of communication rounds needed for at least one correct process to decide. The motivation of this paper is to figure out whether there is any difference between local and global decision bounds, and if there is, whether the same algorithm can match both bounds. We address these questions for several models and various agreement problems. We show that, in a synchronous model with crash failures, the local decision bound is generally strictly smaller than the global decision bound, and rather surprisingly, depending on the number of failures that occur, these bounds cannot both be achieved by a single algorithm. In synchronous runs of the eventually synchronous model however, we show that the local decision bound is the same as the global bound. All our bounds are tight, i.e., we give optimal algorithms to match each of our bounds.

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

IC_TECH_REPORT_200324.pdf

Access type

openaccess

Size

427.17 KB

Format

Adobe PDF

Checksum (MD5)

a017b74ae4ac6610dcc354bc43629c3d

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