CISPA
Browse

Learning Broadcast Protocols

Download (168.62 kB)
conference contribution
posted on 2024-10-30, 10:01 authored by Dana Fisman, Noa Izsak, Swen JacobsSwen Jacobs
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.

History

Name of Conference

National Conference of the American Association for Artificial Intelligence (AAAI)

Journal

Proceedings of the AAAI Conference on Artificial Intelligence

Volume

38

Page Range

12016-12023

Publisher

Association for the Advancement of Artificial Intelligence (AAAI)

Open Access Type

  • Gold

BibTeX

@inproceedings{Fisman:Izsak:Jacobs:2024, title = "Learning Broadcast Protocols", author = "Fisman, Dana" AND "Izsak, Noa" AND "Jacobs, Swen", year = 2024, month = 2, journal = "Proceedings of the AAAI Conference on Artificial Intelligence", number = "11", pages = "12016--12023", publisher = "Association for the Advancement of Artificial Intelligence (AAAI)", issn = "2159-5399", doi = "10.1609/aaai.v38i11.29089" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC