Die Dozenten der Informatik-Institute der Technischen Universität Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem Vortrag ein:
Dr. Mariusz Rokicki, Paris Sud University: Lower bounds on leader election and gossiping in radio networks
Beginn: 13.08.2007, 11:00 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 1. OG, Hörsaal M 160 Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2007-08-13-rokicki.html Kontakt: Prof. Dr. Sándor P. Fekete
We present a number of lower bounds on distributed gossiping and leader election problem in synchronous ad-hoc radio networks.
The lower bounds are considered for two classes of protocols: oblivious and adaptive. The best previously known lower bounds on these problems were linear due to an $n$-node star.
In the model of large labels we show a lower bound of $\Omega(n \log n)$ on leader election protocol and adaptive deterministic gossiping. In case of leader election problems our lower bound almost matches the best known upper bound $\cO(n \log^3 n)$.
In case of adaptive deterministic gossiping in the model of large labels the best known upper bound for symmetric networks is $\cO(n \log^3 n)$ and for directed networks is $\cO(n^{4/3} \log^4 n)$.
We also show a lower bound of $\Omega(n^2)$ on randomized oblivious gossiping.
This result holds for both Las Vegas and Monte Carlo protocols. Our lower bound is tight due to the "Round-Robin" protocol, whose complexity is $\cO(n^2)$ and is a special case of randomized oblivious gossiping.
Our last result is a lower bound of $\Omega(n^2)$ on deterministic oblivious gossiping for symmetric networks in the model of separate messages.
This matches the best known upper bound $\cO (n^2)$.