5 papers
A Classification of Weak Asynchronous Models of Distributed Computing
Javier Esparza, Fabian Reiter
We conduct a systematic study of asynchronous models of distributed computing consisting of identical finite-state devices that cooperate in a network to decide if the network sati…
Identifiers in Registers - Describing Network Algorithms with Logic
Benedikt Bollig, Patricia Bouyer, Fabian Reiter
We propose a formal model of distributed computing based on register automata that captures a broad class of synchronous network algorithms. The local memory of each process is rep…
Distributed Automata and Logic
Fabian Reiter
Distributed automata are finite-state machines that operate on finite directed graphs. Acting as synchronous distributed algorithms, they use their input graph as a network in whic…
Counter Machines and Distributed Automata: A Story about Exchanging Space and Time
Olivier Carton, Bruno Guillon, Fabian Reiter
We prove the equivalence of two classes of counter machines and one class of distributed automata. Our counter machines operate on finite words, which they read from left to right…
Alternating Set Quantifiers in Modal Logic
Fabian Reiter
We establish the strictness of several set quantifier alternation hierarchies that are based on modal logic, evaluated on various classes of finite graphs. This extends to the moda…