Agreement Functions for Distributed Computing Models

2017/02/01 by Petr Kuznetsov, Kuznetsov, Petr, Thibault Rieutord +1
Computer Science · #Age of Information Optimization #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC

paper · pdf · doi:10.48550/arxiv.1702.00361

openalex publication_date 2017/02/01 · arxiv created 2017/03/10 · arxiv updated 2017/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

The paper proposes a surprisingly simple characterization of a large class of models of distributed computing, via an agreement function: for each set of processes, the function determines the best level of set consensus these processes can reach. We show that the task computability of a large class of fair adversaries that includes, in particular superset-closed and symmetric one, is precisely captured by agreement functions.

Citations

• Impossibility of distributed consensus with one faulty process
• Wait-free synchronization
• The topological structure of asynchronous computability

Related

• Set-Consensus Collections are Decidable
• Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks
• A Simple Lower Bound for Set Agreement in Dynamic Networks
• Logical Obstruction to Set Agreement Tasks for Superset-Closed Adversaries
• k-Dimensional Agreement in Multiagent Systems