The Time-Complexity of Local Decision in Distributed Agreement

DOI10.1137/S0097539704446220MaRDI QIDQ3507518zbMATH OpenOpenAlexFDO

Authors Partha Sharathi Dutta, Bastian Pochon, Rachid Guerraoui

Publication date 19 June 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539704446220

zbMATH Keywords

agreement problemsdistributed systemslower bounds

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 6297761
• Towards a complexity theory for local distributed computing
• Convergence and asymptotic agreement in distributed decision problems
• Distributed Computing
• The complexity of deciding reachability properties of distributed negotiation schemes
• Byzantine agreement in polynomial expected time (extended abstract)
• Bounds on the time to reach agreement in the presence of timing uncertainty
• scientific article; zbMATH DE number 1405692
• On the complexity of local distributed graph problems

Cited in

(8)

• Unbeatable consensus
• Bounds on the time to reach agreement in the presence of timing uncertainty
• Consensus in Networks of Multiagents with Stochastically Switching Topologies and Time-Varying Delays
• Full and Local Information in Distributed Decision Making
• Distributed Computing
• SOFSEM 2004: Theory and Practice of Computer Science
• Time bounds for decision problems in the presence of timing uncertainty and failures
• Managed agreement: generalizing two fundamental distributed agreement problems

This page was built for publication: The Time-Complexity of Local Decision in Distributed Agreement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3507518)