2024/03/27 by Lucie Guillou, Guillou, Lucie, Arnaud Sangnier +3 · 1 citation
Computer Science · Engineering · #Computation and Language (cs.CL) #Embedded Systems Design Techniques #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Multiagent Systems (cs.MA) #Real-Time Systems Scheduling #Wireless Body Area Networks #cs.CL #cs.LO #cs.MA
paper · pdf · doi:10.48550/arxiv.2403.18591
submitted to Fundamenta Informaticae
openalex publication_date 2024/03/27 · openalex created_date 2025/10/10 · arxiv created 2026/07/30 · arxiv updated 2026/07/31 · openalex updated_date 2026/08/02
Broadcast protocols are programs designed to be executed by networks of processes. Each process runs the same protocol, and communication between them occurs in synchronously in two ways: broadcast, where one process sends a message to all others, and rendez-vous, where one process sends a message to at most one other process. In both cases, communication is non-blocking, meaning the message is sent even if no process is able to receive it. We consider two coverability problems: the state coverability problem asks whether there exists a number of processes that allows reaching a given state of the protocol, and the configuration coverability problem asks whether there exists a number of processes that allows covering a given configuration. These two problems are known to be decidable and Ackermann-hard. We show that when the protocol is Wait-Only (i.e., it has no state from which a process can both send and receive messages), these problems become P-complete and PSPACE-complete, respectively.