Seminár z teoretickej informatiky - Stefan Dobrev (17.3.2017)

v piatok 17.3.2017 o 11:00 hod. v miestnosti M/213

---

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 

Abstrakt:
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:

1. a lower bound of O(log n/l) for all l-local algorithms on both directed and undirected paths.
2. a surprisingly simple 1-local algorithm for directed paths that uses buffers of size O(log n)
3. 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

web:  http://kedrigern.dcs.fmph.uniba.sk/STI2
rss:  http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php

---