Principles of Robust Medium Access and an Application to Leader Election
Principles of Robust Medium Access and an Application to Leader Election
复制标题
鲁棒媒介访问原理及其在领导者选举中的应用
DOI：
10.1145/2635818
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Jin Zhang
中科院分区：
文献类型：
--
作者：
Baruch Awerbuch;Andrea W. Richa;Christian Scheideler;Stefan Schmid;Jin Zhang
本文研究了无线网络的介质访问控制（MAC）协议的设计，这些协议可证明对任意和不可预测的中断（例如，由于来自共存网络的无意外部干扰或由于干扰）。我们考虑由一组在彼此传输（和干扰）范围内的不诚实且可靠的节点组成的无线网络，并且我们用强大的自适应对手来模拟外部中断。这个对手可能知道该协议及其整个历史，并可以使用这些知识在任何时候随意干扰无线信道。对于节点未知的任意常数ε > 0，允许干扰时间步长的（1-ε）分数。节点无法区分同时发送的两个或更多消息的对抗性干扰或冲突。我们证明，第一次，有一个本地控制MAC协议，只需要非常有限的知识的对手和网络，实现一个恒定的（渐近最优）的吞吐量为nonjamming的时间段下的任何上述对抗策略。派生的原则也是有用的MAC层上建立强大的应用程序，我们提出了一个示例性的研究领导人选举，在分布式计算中最基本的任务之一。
This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or due to jamming). We consider a wireless network consisting of a set ofnhonest and reliable nodes within transmission (and interference) range of each other, and we model the external disruptions with a powerful adaptive adversary. This adversary may know the protocol and its entire history and can use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-ε)-fraction of the timesteps, for an arbitrary constant ε > 0 unknown to the nodes. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant (asymptotically optimal) throughput for the nonjammed time periods under any of the aforementioned adversarial strategies. The derived principles are also useful to build robust applications on top of the MAC layer, and we present an exemplary study for leader election, one of the most fundamental tasks in distributed computing.
登录
查看更多内容
DOI：
10.1109/icpp.2001.952068
发表时间：
2001
期刊：
--
影响因子：
--
作者：
K. Nakano;S. Olariu
通讯作者：
K. Nakano;S. Olariu
被动移动匿名代理自稳定领导者选举的空间复杂度
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
S. Cai;T. Izumi;K. Wada
通讯作者：
K. Wada
遏制错误的练习：自我稳定的领导人选举
影响因子：
0.5
作者：
Sukumar Ghosh;Arobinda Gupta
通讯作者：
Arobinda Gupta
尽管采用分布式控制仍具有自稳定性
DOI：
--
发表时间：
1974
期刊：
影响因子：
--
作者：
E. Dijkstra
通讯作者：
E. Dijkstra
DOI：
--
发表时间：
1996
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
G. Antonoiu;P. Srimani
通讯作者：
P. Srimani