Keeping Wireless Network Theory Useful Nancy Lynch, MIT EECS, CSAIL WRAWN workshop Montreal, July, 2013 Wireless Network Models • Purely graph-based models – Radio Broadcast (protocol) model – Dual Graph model = (, ) = (, , ) Wireless Network Models • Purely graph-based models – Radio Broadcast (protocol) model – Dual Graph model • Geometry-based models – Unit Disk Graph (UDG) – Quasi-Unit-Disk Graph – Signal-to-Noise Ratio (SiNR) • Q: Are these models “realistic”? • In many ways, they are quite strong: – – – – Graphs derived from geometry in stylized ways. Mostly reliable. Mostly static. Known graphs and geometry (sometimes). So Are These Models Realistic? • It depends on the settings and applications we want to consider. • Potential wireless network applications: – – – – – – Hazardous waste cleanup Search and rescue Military operations Exploring an unknown terrain Cooperative construction Flash mob dancing So Are These Models Realistic? • It depends on the settings and applications we want to consider. • Potential wireless network applications: – – – – – – Hazardous waste cleanup Search and rescue Military operations Exploring an unknown terrain Cooperative construction Flash mob dancing • Biological systems: – Insect colonies – Cells during development – Brains Algorithm Characteristics • Algorithms should be efficient (in terms of time, storage, and communication). • Algorithms should be flexible: – They should work in many different settings,. – Participating nodes should not need to know very much about the setting. • Algorithms should be robust to limited amounts of failure and recovery. • More generally, algorithms should be adaptive to changes during execution, e.g.: – The set of participating nodes may change (join, leave, fail, recover) during execution. – Communication is subject to uncertainty, success may vary during execution. – Nodes may move, connectivity may change. Algorithm Characteristics • Efficient. • Flexible, Robust, Adaptive • Q: Why should we focus on these kinds of algorithms? • A: They correspond to many (most) real wireless settings. • A: They also correspond to biological systems (insect colonies, cells during development, brains), which might provide inspiration for new wireless algorithms. • We need new theory for these algorithms: New Theory • New models that can describe the new platforms and algorithms. • New kinds of problem statements. • • • • New complexity measures that take change into account. New kinds of algorithms, new analysis methods. New lower bounds that depend on the additional requirements. New concurrency theory foundations. • Problem guarantees will typically be approximate and probabilistic, not exact and absolute. • Costs of solving the problems will be inherently higher if we include requirements of flexibility and robustness. New Theory • New models that can describe the new platforms and algorithms. • New kinds of problem statements. • • • • New complexity measures that take change into account. New kinds of algorithms, new analysis methods. New lower bounds that depend on the additional requirements. New concurrency theory foundations. • Algorithms may be simpler, more “self-organizing” than usual. • Foundations based on Probabilistic Timed I/O Automata. Examples Examples 1. Low-level wireless communication 2. High-level wireless communication and computation. 3. Social insect colonies 4. Developing organisms 1. Low-Level Wireless Communication • Dual Graph model [Kuhn, Lynch, Newport DISC 09] – Collisions result in message loss. – Unreliable and reliable edges. – Dynamic: Message reach varies over time. • Example algorithms using Dual Graphs: – Building Dominating Sets, MISs [K,L,N, Oshman, Richa PODC 10] – Local and global broadcast [Ghaffari, Haeupler, L,N DISC 12] – Reasonably efficient algorithms for local and global broadcast, provided message reach is determined by an oblivious adversary, and some geographical constraints are satisfied [Ghaffari, Lynch, Newport PODC 13] Low-Level Wireless Communication • Algorithms are more costly than for the radio broadcast model. • Adaptive to dynamic uncertainty of message reach. • Partially flexible: Nodes use partial knowledge of the networks. • Not robust. • Questions: – Consider more dynamic behavior: Failures. Mobility. – Can we get good bounds for local/global broadcast in such highly dynamic settings? – What are the limits of flexibility? That is, what knowledge of the networks is actually required to solve problems using this model? 2. High-Level Wireless Communication and Computation • Some work on higher-level algorithms in wireless networks assumes completely reliable local broadcast (RLB) communication. • Examples: – – – – Global broadcast in static graph networks Building network structures Computing in dynamic graph networks Robot coordination • Abstract MAC layers [Kuhn, Lynch, Newport 09], mask low-level wireless communication, yield RLB guarantees. • But low-level wireless protocols do not guarantee completely reliable local broadcast. – They involve probabilistic transmission, random backoff, random coding,… – Yield high-probability guarantees only. • So we defined a probabilistic abstract MAC layer [Khabbazian, Kowalski, Kuhn, Lynch DIALM-POMC 10]. – Fast delivery of each message to all neighbors whp. – Each receiver receives some message quickly whp. High-Level Wireless Communication and Computation • Questions: – Design algorithms above a local bcast layer that tolerate occasional exceptions (lost messages). – Which currently-existing high-level algorithms, written over a RLB layer, already tolerate such exceptions, or can easily be modified to do so? Which do not? – What are inherent limitations? – How do we model/verify compositions of high-level probabilistic algorithms and probabilistic implementations of local broadcast? • Problems to consider: – Communication, building network structures. – Robot problems: task allocation, forming geometric patterns, exploration/routing/navigating. • Also consider other kinds of failures, mobility. • Combine these considerations with Dual Graph issues. 3. Social Insect Colonies • Social insects (ants and bees) live in colonies, cooperate to solve complex problems, including: – Division of labor (foraging for food, feeding larvae, cleanup, defense,…) – Searching/routing/navigating. – Agreeing on the site of a new nest. – Constructing nests. • They use distributed algorithms, based on direct chemical or physical communication, or on leaving chemical signals in the environment (stigmergy). • Algorithms are highly flexible, robust, and adaptive. • Efficient: Colonies perform their work quickly, with low energy usage. Social Insect Colonies • Flexible: – Insects don’t know the exact size of the colony, though they may have a rough idea. – Insects don’t know all the details of their physical environment. – But colonies may have evolved to do better in certain kinds of settings than others. • Robust: – Death of some insects doesn’t affect the colony much. – Destroying the nest leads the insects to find/build another nest. – Homeostasis? • Adaptive to changes to the colony, to the environment. Proposed Research Project • Dornhaus (insect colony bio), Lynch (dist. algs.), Nagpal (robotics) • Distributed Problem Solving in Dynamic Collectives: Theory, Insects, and Robots • Identify/analyze distributed algorithms that may be used by insect colonies. • Define platform models, problems, algorithms. • Examples: Division of labor, foraging, nest construction. • Contributions to insect colony research: – Discover what algorithms insects actually use, and why. – Analyze the algorithms based on performance plus adaptivity. • Contributions to (wireless) distributed algorithms: – New adaptive algorithms, inspired by insect colony behavior. – New measures and analysis methods, for adaptive algorithms. – New concurrency theory. • Contributions to robotics: – Adapt insect algorithms for robot swarms. 4. Developing organisms • Cells in a developing embryo cooperate to solve problems of patterning. • Sometimes involves scaling. • They use distributed algorithms, based on: – Local chemical signaling between cells. • Like “beep” communication, as studied in our community. – Global morphogen gradients [Turing]. • Simple local rules. • Flexible: Not dependent on exact number of cells, size of organism. • Robust: Death of some cells doesn’t matter much; homeostasis. Developing organisms • Questions: Identify/analyze distributed algorithms that may be used by cells in developing organisms. • Define platform models, problems, algorithms. • Contributions to developmental biology: – Discover what algorithms developing organisms actually use, and why. – Analyze algorithms based on performance, robustness to failures • Contributions to (wireless) distributed algorithms: – New algorithms, inspired by developmental behavior. – New measures and analysis methods – New concurrency theory. • In general, understanding biological algorithms could help us understand how to build simple, efficient, flexible, robust, adaptive wireless network algorithms. Summary: Needed Work • Research on algorithms for wireless networks that are flexible, robust, and adaptive to changes. • New kinds of models, cost metrics • New kinds of algorithms • New kinds of analysis Concurrency theory foundations • General models based on interacting automata. • Must include time, discrete + continuous behavior, motion, probability. • Composition, abstraction. • Tailor for wireless systems. Thank you!