ICE TCS seminar Friday - Pradipta Mitra

  • 4.1.2013, 14:00 - 15:00

WHEN: Friday, January 4th, 2pm

WHERE: M108 (note different location), Reykjavik University, Menntavegur 1

WHO: Pradipta Mitra (RU)

WHAT: Wireless Connectivity from Scratch


Abstract: Starting from basic physical properties of a wireless channel, we consider the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes. This means a) finding a set of links that form a strongly connected spanning graph on a set of $n$ points in the plane, and b) scheduling it efficiently in the SINR model of interference.

We prove that any set of nodes can be connected in O(\log n) time slots, improving upon a long-standing previous bound of O(\log^2 n).

We achieve this bound using both centralized and distributed algorithms. The distributed algorithm deploys a two step mechanism: first, a very simple algorithm is used to construct an initial connected tree, this tree is then used a distributed platform to improve itself to come up with a solution matching the centralized bound.

Talk is based on:
Wireless Connectivity and Capacity, Magnus M. Halldorsson and Pradipta Mitra, SODA '12
Distributed Connectivity of Wireless Networks, <
http://arxiv.org/abs/1205.5164> Magnus M. Halldorsson and Pradipta Mitra, PODC '12