← 研踪 PaperTrailarXiv:2611.09466 · v1
Symmetry Breaking over Multiway Channels
首次提交 2026-11-06 21:44
版本更新 2026-11-06 21:44
雷达观测 2026-11-09 11:19
摘要
Identical users running the same algorithm must often break their symmetry and agree on distinct roles, as in leader election, naming, and resource allocation. We study anonymous symmetry breaking over a discrete memoryless multiway channel invariant under permutations of its $J$ users: each user observes only a private output and must choose a number in $\{1,\dots,J\}$, and the symmetry is broken if the $J$ numbers are distinct. Using a Rényi change of measure, we derive a finite-blocklength converse on the error probability of every symmetric causal protocol, including adaptive and randomized ones. For achievability, block coding with random names reduces the problem to all-source multicast, for which we derive a Gallager random-coding exponent for every fixed $J$, and a cut-set bound that limits the exponent of the probability that two names coincide or are decoded wrongly. Interactive role controllers instead let the users contend for identifiers directly: we give their exact error probability, an achievable exponent given by a spectral radius when some outputs certify a role, and a floor for finite-state controllers when every output has positive probability, and we introduce generalized musical chairs. On a noisy bandit channel motivated by multiplayer multi-armed bandits, with noiseless collisions and arms of a common mean below one, interactive schemes provably exceed the limit of name decoding, and numerical estimates suggest the same with noisy collisions. For two users, noiseless collisions, one informative arm and a silent arm, the optimal error probability is determined up to a factor of two.
作者备注：Submitted to TIT
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 21:44 · 最新观测版本
Symmetry Breaking over Multiway Channels
Identical users running the same algorithm must often break their symmetry and agree on distinct roles, as in leader election, naming, and resource allocation. We study anonymous symmetry breaking over a discrete memoryless multiway channel invariant under permutations of its $J$ users: each user observes only a private output and must choose a number in $\{1,\dots,J\}$, and the symmetry is broken if the $J$ numbers are distinct. Using a Rényi change of measure, we derive a finite-blocklength converse on the error probability of every symmetric causal protocol, including adaptive and randomized ones. For achievability, block coding with random names reduces the problem to all-source multicast, for which we derive a Gallager random-coding exponent for every fixed $J$, and a cut-set bound that limits the exponent of the probability that two names coincide or are decoded wrongly. Interactive role controllers instead let the users contend for identifiers directly: we give their exact error probability, an achievable exponent given by a spectral radius when some outputs certify a role, and a floor for finite-state controllers when every output has positive probability, and we introduce generalized musical chairs. On a noisy bandit channel motivated by multiplayer multi-armed bandits, with noiseless collisions and arms of a common mean below one, interactive schemes provably exceed the limit of name decoding, and numerical estimates suggest the same with noisy collisions. For two users, noiseless collisions, one informative arm and a silent arm, the optimal error probability is determined up to a factor of two.
查看此版本解读 →查看此版本原文 ↗