Learning Broadcast Protocols
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Safety Verification of Wait-Only Non-Blocking Broadcast Protocols
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 sen…
Communication Bounds for the Distributed Experts Problem
In this work, we study the experts problem in the distributed setting where an expert's cost needs to be aggregated across multiple servers. Our study considers various communication models such as the message-passing mo…
Novel Maximum Likelihood Estimation of Clock Skew in One-Way Broadcast Time Synchronization
Clock skew compensation is essential for accurate time synchronization in wireless networks. However, contemporary clock skew estimation is based on inaccurate transmission time measurement, which makes credible estimati…
TacSIm: A Dataset and Benchmark for Football Tactical Style Imitation
Current football imitation research primarily aims to opti mize reward-based objectives, such as goals scored or win rate proxies, paying less attention to accurately replicat ing real-world team tactical behaviors. We i…
Communication-Optimal Distributed Clustering
Clustering large datasets is a fundamental problem with a number of applications in machine learning. Data is often collected on different sites and clustering needs to be performed in a distributed manner with low commu…
Clustering