# Learning Broadcast Protocols

arXiv: https://arxiv.org/abs/2306.14284 · HTML: https://mlsanity.com/paper/2306.14284/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 44 references that are in the map.
- First posted on arXiv 25 Jun 2023.

## Builds on (most cited first, 7 of 7)

- [Parameterized Synthesis](https://mlsanity.com/paper/1401.3588/) (2014)
- [Tight Cutoffs for Guarded Protocols with Fairness](https://mlsanity.com/paper/1505.03273/) (2015)
- [Analyzing Guarded Protocols: Better Cutoffs, More Systems, More Expressivity](https://mlsanity.com/paper/1707.01369/) (2017)
- [Parameterized Verification of Systems with Global Synchronization and Guards](https://mlsanity.com/paper/2004.04896/) (2020)
- [Active Learning for Sound Negotiations](https://mlsanity.com/paper/2110.02783/) (2021)
- [Learning of Structurally Unambiguous Probabilistic Grammars](https://mlsanity.com/paper/2203.09441/) (2022)
- [Synthesis of Distributed Agreement-Based Systems with Efficiently-Decidable Verification (Extended Version)](https://mlsanity.com/paper/2208.12400/) (2022)

## Abstract (arXiv)

The problem of learning a computational model from examples has been receiving growing attention. For the particularly challenging problem of learning models of distributed systems, existing results are restricted to models with a fixed number of interacting processes. In this work we look for the first time (to the best of our knowledge) at the problem of learning a distributed system with an arbitrary number of processes, assuming only that there exists a cutoff, i.e., a number of processes that is sufficient to produce all observable behaviors. Specifically, we consider fine broadcast protocols, these are broadcast protocols (BPs) with a finite cutoff and no hidden states. We provide a learning algorithm that can infer a correct BP from a sample that is consistent with a fine BP, and a minimal equivalent BP if the sample is sufficiently complete. On the negative side we show that (a) characteristic sets of exponential size are unavoidable, (b) the consistency problem for fine BPs is NP hard, and (c) that fine BPs are not polynomially predictable.