TACO: A Toolsuite for the Verification of Threshold Automata

Paul Eichler ✉, Tom Baumeister, Mouhammad Sakr, Mahboubeh Kalateh Dowlati, Marcus Völp, Swen Jacobs · 2026

Read TACO: A Toolsuite for the Verification of Threshold Automata by Paul Eichler ✉, Tom Baumeister, Mouhammad Sakr, Mahboubeh Kalateh Dowlati, Marcus Völp, Swen Jacobs (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06118.txt.

Introduction

Paul Eichler and five co-authors present TACO, a toolsuite for verifying threshold automata. Such automata model fault tolerant distributed algorithms whose steps depend on how many participants pass a threshold. Checking those algorithms by hand is error prone, and automated tools have covered only parts of the theory.

TACO implements three model checking approaches for known decidable fragments of the problem. It adds two semi decision procedures that reach beyond those fragments, where full guarantees are not possible. The suite is modular, extensible, and documented, aiming to serve both users and future tool builders. The authors describe its main features and the algorithms inside, then evaluate performance in experiments. The goal is a shared framework for this corner of distributed algorithm research.

Catalog record

CREATORPaul Eichler ✉, Tom Baumeister, Mouhammad Sakr, Mahboubeh Kalateh Dowlati, Marcus Völp, Swen Jacobs
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06118

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

TACO: A Toolsuite for the Verification of Threshold Automata Paul Eichler ✉, Tom Baumeister, Mouhammad Sakr, Mahboubeh Kalateh Dowlati, Marcus Völp, Swen Jacobs Abstract We present Taco , a toolsuite for the development and automatic verification of fault-tolerant and threshold-based distributed algorithms. Our toolsuite implements three approaches for model checking threshold automata in different decidable fragments known from the literature and two semi-decision procedures going beyond these decidable fragments. Moreover, Taco is a modular, extensible, and well-documented framework for developing algorithms and tools for threshold automata. We present important features, give an overview of the implemented algorithms, and evaluate their performance experimentally. 1 Introduction Ensuring the correctness of the algorithms at the heart of modern distributed systems is a challenging but important task. Many different approaches, models, and tools have been developed to tackle this challenge [ 16 , 18 , 37 , 41 , 50 , 34 , 39 ] . Real-world systems require their underlying distributed algorithms to be fault-tolerant and to scale to any number of participants. While verifying correctness with a parameterized number of processes is already challenging, fault-tolerance additionally requires to reason modulo a resilience condition that bounds the type and number of faults that can be tolerated. Without such a condition, it is impossible for many essential algorithms to achieve their desired properties [ 35 ] . In Taco , we have chosen threshold automata (TA) as the underlying system model as it supports a parametric number of processes as well as resillience conditions [ 29 , 28 , 34 , 23 ] . This model allows expressing many essential consensus algorithms [ 10 , 38 , 9 , 20 , 8 ] , as well as more advanced distributed algorithms, e.g., from modern blockchain applications [ 11 , 23 ] . Intuitively, a TA models the local state of a participant of a protocol in the automaton locations and the global state by shared integer variables. These variables essentially count how often a given event (e.g., broadcast of a certain message) has happened so far. Thresholds can be assigned as guards to transitions of the TA, such that an action can only be taken after the threshold is crossed. Moreover, different fragments of TA have been shown to support decidable parameterized verification , i.e., their correctness can be decided independent of the number of participants [ 19 , 29 , 30 , 25 , 26 , 24 , 34 , 31 , 8 , 2 , 46 , 47 ] . As the restrictions of these decidable fragments may be too strict for certain applications, such as round-based algorithms with resets of shared variables, more generalized verification approaches based on semi-decision procedures have also been considered [ 6 ] . While TA can be used to express and verify many interesting distributed algorithms, and the theory of TA is well-documented and steadily growing, the situation is not as satisfactory on the tool side: The only publicly available tool for TA is ByMC [ 19 , 29 , 28 , 30 , 25 , 26 , 31 , 23 , 32 ] , which is no longer maintained. Implementations of other decision procedures for TA and variants of TA are prototypes not well-suited for use by non-expert users and further development by third parties [ 2 , 3 , 45 , 48 , 47 , 6 ] . The only related tool that is publicly available and currently supported is PyLTA, a model checker for layered threshold automata (LTA) [ 49 ] . However, LTA are not a generalization of standard TA, and PyLTA does not support the existing TA benchmark library. Contributions. In this paper, we present Taco 1 1 1 TACO’s source code is available on GitHub https://github.com/cispa/TACO and the documentation is on the webpage https://taco-mc.dev . A reproduction package containing the source code, benchmark files and documentation at the time of submission is available on Zenodo [ 13 ] . , a toolsuite for the development and verification of threshold-based distributed algorithms. Taco provides: 1. an efficient implementation of three model checking algorithms that scale to previously unsolved TA and extensions of the standard TA model, and 2. a documented, maintained, and extensible code base, well-suited to serve as the basis of future model checkers and tools for TA, as well as 3. an intuitive user interface that supports users in modeling and debugging distributed algorithms. In this paper, we will give a high-level overview of the three algorithms, describe important features of Taco , and evaluate the performance of the algorithms on different classes of benchmarks, comparing their strengths and weaknesses. 2 System Model and Specifications We first define the underlying formal model of TA and introduce the specification language, before providing more details on the architecture of Taco . Definition 1 (Threshold Automaton [ 29 , 28 ] ) A threshold automaton (TA) is a tuple A=(L,\mathcal{I},\Gamma,\Pi,\mathcal{R},RC) where L is a finite set of locations , \mathcal{I}\subseteq L the set of initial locations , \Gamma is a finite set of shared variables over \mathbb{N}_{0} , \Pi is a finite set of parameter variables over \mathbb{N}_{0} , RC is the resilience condition , a linear integer arithmetic formula over parameter variables, and \mathcal{R} is a set of rules. A rule is a tuple r=(\textit{from},\textit{to},\varphi,\mathbf{uv}) where, \textit{from},\textit{to}\in L , \mathbf{uv}\in\mathbb{N}_{0}^{|\Gamma|} the update vector for shared variables and \varphi is a conjunction of lower guards and upper guards. A lower guard is a constraint a_{0}{+}\sum_{i=1}^{|\Pi|}a_{i}{\cdot}p_{i}\leq x , with x\in\Gamma , a_{0},\ldots,a_{|\Pi|}\in\mathbb{Q} , p_{1},\ldots,p_{|\Pi|}\in\Pi . An upper guard is a constraint a_{0}{+}\sum_{i=1}^{|\Pi|}a_{i}{\cdot}p_{i}>x . The left-hand side of a lower or upper guard is a threshold . Note that the update vector \mathbf{uv} is in \mathbb{N}_{0}^{|\Gamma|} and consequently shared variables can only increase. In the following, we will also call such an automaton a monotonic threshold automaton (MTA). MTA do not allow variable decrements or resets, which restricts their ability to model algorithms, including round-based distributed algorithms, whose execution relies on resetting or reusing rounds. To address this limitation, Taco additionally supports extended threshold automata (ETA) [ 6 ] , where \mathbf{uv}\in\mathbb{Z}_{0}^{|\Gamma|} , i.e., variables can also be decremented, and a rule contains an additional set \tau\subseteq\Gamma which contains the variables that are reset to 0. To simplify the presentation, where the distinction does not affect our results, we refer to both models simply as threshold automata (TA). Otherwise, we distinguish between ETA and MTA as required. Common parameter variables in TA are \Pi=\{n,t,f\} , where n is the number of processes, t is a bound on the number of faulty processes, and f is the actual number of faulty processes. This allows RC to express assumptions about the fraction of faulty processes in the system, e.g., RC=n>3t\,\land\,t\geq f . Algorithm 1 1: int v\leftarrow\text{input}(\{0,1\}) 2: broadcast v ; 3: R\leftarrow receive messages from all; 4: if |\{r\in R:r=1\}|>n-t 5: decide 1 ; 6: if |\{r\in R:r=0\}|>n-t 7: decide 0 ; Figure 1: A simple voting protocol. v_{0} wait v_{1} d_{0} d_{1} r_{0}:x_{0}++ r_{1}:x_{1}++ r_{2}:x_{0}\geq n-t r_{3}:x_{1}\geq n-t Figure 2: TA of the algorithm in Fig. 2 Example 1 Fig. 2 shows pseudocode for a naive voting protocol. Figure 2 sketches the corresponding TA

Read the complete text