Thesis
Resource-competitive consensus and leader election tolerating jamming
Master of Science (M.S.), Drexel University
01 Jun 2015
DOI:
https://doi.org/10.17918/etd-6513
Abstract
In this paper, we present randomized, distributed algorithms that allow n >- 1 nodes to solve agreement problems in a single-hop, time-slotted wireless sensor network (WSN). In particular, we consider the problem of consensus - where all nodes must come to agreement on any single value - and the problem of leader election - where all nodes must agree on a single node to act as a leader. Both consensus and leader election are well-studied challenges whose solutions provide critical building blocks for protocols in distributed systems. Our results extend this study to the domain of WSNs in the presence of (possible malicious) communication failures. Our algorithms are provably robust and scalable in the face of an adversary who interferes with (or jams) communications between the network devices (nodes). In WSNs, the communication costs incurred by nodes is a major concern because such devices are typically powered by on-board batteries with limited resources, and the actions of sending and listening on the communication channel dominates operational costs. These costs are modeled as a unit cost for sending or listening to a message in a single time slot, while the cost for staying silent in a time slot is zero. Similarly, the adversary incurs unit cost to jam a single slot as this equates to sending on the channel. Consider an adversary that incurs a cost of T by pursuing an arbitrary, worst-case jamming strategy. We demonstrate an algorithm that solves consensus, and another algorithm that solves leader election, with a per-node expected cost of O( p T=n lg2:5 n+ lg5 n). This implies that the adversary must incur a substantially large asymptotic cost in pursuing any jamming strategy. In the energy-constrained domain of WSNs, this result is particularly valuable as the adversary will rapidly deplete her resources in attempting to thwart consensus or leader election.
Metrics
35 File views/ downloads
24 Record Views
Details
- Title
- Resource-competitive consensus and leader election tolerating jamming
- Creators
- Jianyu Wang - DU
- Contributors
- Maxwell Young (Advisor) - Drexel University (1970-)
- Awarding Institution
- Drexel University
- Degree Awarded
- Master of Science (M.S.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Number of pages
- vi, 62 pages
- Resource Type
- Thesis
- Language
- English
- Academic Unit
- Computer Science (Computing) (2013-2026); College of Computing and Informatics (2013-2026); Drexel University
- Other Identifier
- 6513; 991014632182704721