Distributed computation on unreliable radio channels

An important topic in wireless networking is the development of reliable algorithms for environments suffering from adversarial interference. This term captures any type of channel disruption outside the control of the algorithm designer-from contention with unrelated devices to malicious jamming. In this thesis, we provide four contributions toward a comprehensive theoretical treatment of this topic. First, we detail a formal modeling framework. This framework is general enough to describe almost any radio network studied to date in the theory literature. It can also precisely capture the often subtle details of adversarial behavior. In addition, we prove a pair of composition results that allow a layered strategy for designing radio network algorithms The results can be used to combine an algorithm designed for a powerful channel with an implementation of this channel on a less powerful channel. Next, we formalize adversarial interference with the definition of the t-disrupted channel. We then define the more powerful (t, b, p)-feedback channel, and provide both a randomized and deterministic implementation of the latter using the former. To emphasize the utility of this layered approach, we provide solutions to the set agreement, gossip, and reliable broadcast problems using the powerful feedback channel. Combined with the implementation algorithms and composition results, this automatically generates solutions to these problems for the less powerful, but more realistic, t-disrupted channel. Finally, we define a variant of the modeling framework that captures the attributes of an ad hoc network, including asynchronous starts and the lack of advance knowledge of participating devices.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Newport, Calvin (Calvin Charles)

Advisor dc:contributor.advisor

• Nancy Lynch.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/55120

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/55120