Calvin Newport: Distributed Algorithsm in a Wireless World

This talk is about the role of distributed algorithm theory in the increasingly important wireless network setting. It presents three big ideas refined from my ten years of experience working on this topic.

The first idea is that distributed algorithms will almost certainly play a big role in the future of wireless technology. As wireless hardware becomes increasingly affordable and high-performance, we can expect to see an increasing number of complex network types replacing wires with radio links. I will argue that the distributed systems running on these networks will need provable guarantees, and distributed algorithm theory is uniquely suited to provide these guarantees.

The second idea is that wireless models require non-determinism. The vast majority of existing theory results in this setting assume wireless models that follow predictable (i.e., deterministic) rules. Real wireless networks, however, are anything but predictable. Results proved in the predictable models are therefore unlikely to hold in real deployments. The solution is to introduce non-determinism into our wireless models. I will discuss the efforts of myself and other researchers to introduce and explore these models. I will then identify the most promising open problems and lay out a concrete vision for how these results can be useful to real networks.

The third idea is that theoreticians studying wireless networks need to move up the network stack. Most existing theory results in this setting model the network from a link-layer perspective. I will argue that we should also model the network above the link-layer. By doing so, we will produce algorithms that can be easily deployed in existing wireless systems, and that offer provable guarantees that do not depend on assumptions about low-level network behavior. I will discuss recent efforts by myself and others to make this shift in perspective, highlighting new results and arguing for their immediate applicability to real wireless systems.