10 citations · 27 across the 16 of their papers we have counts for
5 papers · 1 filter
Lower Bounds for Structuring Unreliable Radio Networks
Calvin Newport
In this paper, we study lower bounds for randomized solutions to the maximal independent set (MIS) and connected dominating set (CDS) problems in the dual graph model of radio netw…
Radio Network Lower Bounds Made Easy
Calvin Newport
Theoreticians have studied distributed algorithms in the radio network model for close to three decades. A significant fraction of this work focuses on lower bounds for basic commu…
Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication
Christoph Lenzen, Nancy Lynch, Calvin Newport +1
We consider the ANTS problem [Feinerman et al.] in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the b…
Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links
Mohsen Ghaffari, Erez Kantor, Nancy Lynch +1
We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting…
Consensus with an Abstract MAC Layer
Calvin Newport
In this paper, we study distributed consensus in the radio network setting. We produce new upper and lower bounds for this problem in an abstract MAC layer model that captures the…