Principles of Robust Medium Access and an Application to Leader Election

B. Awerbuch, A.W. Richa, C. Scheideler, S. Schmid, J. Zhang, Transactions on Algorithms (2014).

Download
Restricted 387-a24-awerbuch_2_.pdf 521.45 KB
Journal Article
Author
Awerbuch, Baruch; Richa, Andrea W.; Scheideler, ChristianLibreCat; Schmid, Stefan; Zhang, Jin
Abstract
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 of n honest 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.
Publishing Year
Journal Title
Transactions on Algorithms
Issue
4
LibreCat-ID
387

Cite this

Awerbuch B, Richa AW, Scheideler C, Schmid S, Zhang J. Principles of Robust Medium Access and an Application to Leader Election. Transactions on Algorithms. 2014;(4). doi:10.1145/2635818
Awerbuch, B., Richa, A. W., Scheideler, C., Schmid, S., & Zhang, J. (2014). Principles of Robust Medium Access and an Application to Leader Election. Transactions on Algorithms, (4). https://doi.org/10.1145/2635818
@article{Awerbuch_Richa_Scheideler_Schmid_Zhang_2014, title={Principles of Robust Medium Access and an Application to Leader Election}, DOI={10.1145/2635818}, number={4}, journal={Transactions on Algorithms}, publisher={ACM}, author={Awerbuch, Baruch and Richa, Andrea W. and Scheideler, Christian and Schmid, Stefan and Zhang, Jin}, year={2014} }
Awerbuch, Baruch, Andrea W. Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. “Principles of Robust Medium Access and an Application to Leader Election.” Transactions on Algorithms, no. 4 (2014). https://doi.org/10.1145/2635818.
B. Awerbuch, A. W. Richa, C. Scheideler, S. Schmid, and J. Zhang, “Principles of Robust Medium Access and an Application to Leader Election,” Transactions on Algorithms, no. 4, 2014.
Awerbuch, Baruch, et al. “Principles of Robust Medium Access and an Application to Leader Election.” Transactions on Algorithms, no. 4, ACM, 2014, doi:10.1145/2635818.
Main File(s)
File Name
387-a24-awerbuch_2_.pdf 521.45 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-20T07:02:33Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar