A combinatorial characterization of the distributed 1-solvable tasks

DOI10.1016/0196-6774(90)90020-FzbMath0705.68018OpenAlexW2001757616WikidataQ106202808 ScholiaQ106202808MaRDI QIDQ3485850

Shmuel Zaks, Ofer Biran, Shlomo Moran

Publication date: 1990

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(90)90020-f

zbMATH Keywords

lower boundsprotocolfaulty processordistributed agreement

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed algorithms (68W15)

Related Items (25)

Collapsibility of read/write models using discrete Morse theory ⋮ An algorithmic approach to the asynchronous computability theorem ⋮ Unnamed Item ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ The topology of distributed adversaries ⋮ Communication Complexity of Wait-Free Computability in Dynamic Networks ⋮ Wait-free computing ⋮ Impure Simplicial Complexes: Complete Axiomatization ⋮ About informatics, distributed computing, and our job: a personal view ⋮ On the Validity of Consensus ⋮ Unnamed Item ⋮ The renaming problem in shared memory systems: an introduction ⋮ Closed schedulers: a novel technique for analyzing asynchronous protocols ⋮ The BG distributed simulation algorithm ⋮ Hundreds of impossibility results for distributed computing ⋮ Condition-based consensus solvability: a hierarchy of conditions and efficient protocols ⋮ The minimum information about failures for solving non-local tasks in message-passing systems ⋮ Tight bounds on the round complexity of distributed 1-solvable tasks ⋮ An Introduction to the Topological Theory of Distributed Computing with Safe-consensus ⋮ Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures ⋮ A simplicial complex model for dynamic epistemic logic to study distributed task computability ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks ⋮ A distributed computing perspective of unconditionally secure information transmission in Russian cards problems ⋮ A classification of wait-free loop agreement tasks

This page was built for publication: A combinatorial characterization of the distributed 1-solvable tasks