Seminár z teoretickej informatiky - Stefan Dobrev (17.3.2017)
v piatok 17.3.2017 o 11:00 hod. v miestnosti M/213
Od: Rastislav Královič
Prednášajúci: Stefan Dobrev
Názov: Optimal Local Buffer Management for Information Gathering with Adversarial Traffic
Termín: 17.3.2017, 11:00 hod., M/213
We consider a well studied problem in adversarial queuing theory, namely routing on directed paths and trees with a single destination, with rate-limited adversarial traffic. In particular, we focus on local buffer management algorithms that ensure no packet loss, while minimizing the size of the required buffers.
While a centralized algorithm for the problem that uses constant-sized buffers has been recently shown, there is no known local algorithm that achieves a sub-linear buffer size. In fact, greedy algorithms, which have been extensively studied in this setting, have been shown to require buffers of size Theta(n).
In this paper we show tight bounds for the maximum buffer size needed by local algorithms for information gathering on directed paths and trees.
We show three main results:
- a lower bound of O(log n/l) for all l-local algorithms on both directed and undirected paths.
- a surprisingly simple 1-local algorithm for directed paths that uses buffers of size O(log n)
- a natural extension of this algorithm to directed trees, achieving the same asymptotic bound. Here, our algorithm is 2-local in order to avoid the simultaneous sending of packets by siblings to a common successor.
Our Omega(log n) lower bound is signiffcantly lower than the Omega(n) lower bound for greedy algorithms; what is perhaps the most surprising is that there is a matching upper bound.
Stefan Dobrev, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny Submitted to SPAA 2017