Making Wireless Algorithm Theory More Useful: Five Ideas from the 2013 Workshop on Realistic Models for Algorithms in Wireless Networks

摘要

In summer 2013, a group of invited speakers and interested participants gathered in Montreal, Canada, for the fourth annual Workshop on Realistic Models for Algorithms in Wireless Networks (WRAWN), co-organized by the authors of this article, and co-located with the ACM Principles of Distributed Computing (PODC) conference. The motivating question for this year's workshop was blunt: Is the study of wireless algorithms useful enough? To help explore answers, the workshop featured talks that highlighted different perspectives on this question. Fabian Kuhn and Christian Scheideler discussed wireless models that include non-determinism, boosting the robustness of algorithmic results, while Seth Gilbert motivated the need to study multi-channel networks. Majid Khabbazian and Thomas Janson discussed the theory and practice of interference cancellation strategies such as analog network coding and MIMO, while Magnus Halldorsson and Martin Hoefer described efforts to identify the fundamental wireless properties needed to prove useful results. Finally, Nancy Lynch talked about new settings, such as biological systems, where wireless distributed algorithm theory can play a useful role, and Calvin Newport explored the current gap between wireless theory and practice.