Physical Sciences and Mathematics Commons^™

Routing In The Dark: Pitch Black, Nathan S. Evans

Electronic Theses and Dissertations

In many networks, such as mobile ad-hoc networks and friend-to-friend overlay networks, direct communication between nodes is limited to specific neighbors. Friendto-friend “darknet” networks have been shown to commonly have a small-world topology; while short paths exist between any pair of nodes in small-world networks, it is non-trivial to determine such paths with a distributed algorithm. Recently, Clarke and Sandberg proposed the first decentralized routing algorithm that achieves efficient routing in such small-world networks.

Herein this thesis we discuss the first independent security analysis of Clarke and Sandberg’s routing algorithm. We show that a relatively weak participating adversary can render …