24 citations · 49 across the 7 of their papers we have counts for
9 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…
Emptiness Problems for Distributed Automata
Antti Kuusisto, Fabian Reiter
We investigate the decidability of the emptiness problem for three classes of distributed automata. These devices operate on finite directed graphs, acting as networks of identical…
Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment
Fabian Reiter
We establish the equivalence between a class of asynchronous distributed automata and a small fragment of least fixpoint logic, when restricted to finite directed graphs. More spec…
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…
Distributed Graph Automata and Verification of Distributed Algorithms
Fabian Reiter
Combining ideas from distributed algorithms and alternating automata, we introduce a new class of finite graph automata that recognize precisely the languages of finite graphs defi…
Distributed Graph Automata
Fabian Reiter
Inspired by distributed algorithms, we introduce a new class of finite graph automata that recognize precisely the graph languages definable in monadic second-order logic. For the…