This paper revisits a classical problem of slotted multiple access with success, idle, and collision events on each slot. First, results of a 2-user multiple access game are reported. The game was conducted at the University of Southern California over multiple semesters and involved competitions between student-designed algorithms. An algorithm called 4-State was a consistent winner. This algorithm is analyzed and shown to have an optimal expected score when competing against an independent version of itself. The structure of 4-State motivates exploration of the open question of how to minimize the expected time to capture the channel for a $n$-user situation. It is assumed that the system delivers perfect feedback on the number of users who transmitted at the end of each slot. An efficient algorithm is developed and conjectured to have an optimal expected capture time for all positive integers $n$. Optimality is proven in the special cases $n \in \{1, 2, 3, 4, 6\}$ using a novel analytical technique that introduces virtual users with enhanced capabilities.
翻译:本文重述了每个空位的多位访问时间档、成功、闲置和碰撞的典型问题。 首先,报告了2个用户多重访问游戏的结果。 该游戏在南加州大学进行了多个学期,涉及学生设计的算法之间的竞争。 名为 4 - State 的算法始终是赢家。 该算法在与独立版本的自身竞争时被分析和显示为最佳的预期分数。 4 - State 的结构激励着探索如何最大限度地缩短为1, 2, 3, 4, 6美元获取频道的预期时间的开放问题。 假设该系统对每个空位末端传输的用户数量提供完美的反馈。 高效的算法得到开发,并预示所有正数整数的预期截取时间是最佳的 $n. 2, 3, 4, 6 6美元。 最佳性在特殊案例中得到证明 $n\ inn ein, 2, 2, 3, 4, 6, 6 使用一种引入能力增强的虚拟用户的新分析技术。