An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems | Zendy

Maurice Herlihy | Zendy; Sergio Rajsbaum | Zendy; Mark R. Tuttle | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems

Author(s) -

Maurice Herlihy,

Sergio Rajsbaum,

Mark R. Tuttle

Publication year - 2009

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2009.02.018

Subject(s) - asynchronous communication , set (abstract data type) , computer science , simple (philosophy) , operator (biology) , axiom , axiomatic system , theoretical computer science , construct (python library) , algorithm , topology (electrical circuits) , mathematics , combinatorics , programming language , computer network , philosophy , biochemistry , chemistry , geometry , epistemology , repressor , transcription factor , gene

We present a unified, axiomatic approach to proving lower bounds for the k-set agreement problem in both synchronous and asynchronous message-passing models. The proof involves constructing the set of reachable states, proving that these states are highly connected, and then appealing to a well-known topological result that high connectivity implies that set agreement is impossible. We construct the set of reachable states in an iterative fashion using a round operator that we define, and our proof of connectivity is an inductive proof based on this iterative construction and simple properties of the round operator

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research