View article

A major topic investigated by my research is realistic wireless network models. My collaborators and I observed that most theoretical work on algorithms in this setting simplify communication into a series of deterministic rules. The correctness of algorithms proved in these models often depends on the inviolable nature of these rules. 1 In practice, of course, wireless communication is anything but predictable. This

1A classic example is the problem of broadcasting a message through a constant-diameter network. If you assume it is possible for a process to sometimes receive one message from among several during a collision, Ω (n) steps are required to solve the problem [3, 4]. If you assume that all colliding messages are always lost, however, you can solve the problem in Ø (log n) steps [30].