Résumé | We consider the problems of online and stochastic packet queuing in a
distributed system of n nodes with queues, where the communication
between the nodes is done via a multiple access channel. In each
round, an arbitrary number of packets can be injected into the system,
each to an arbitrary node's queue. Two measures of performance are
considered: the total number of packets in the system, called the
total load, and the maximum queue size, called the maximum load. In
the online setting, we develop a deterministic algorithm that is
asymptotically optimal with respect to both complexity measures, in a
competitive way; more precisely, the total load of our algorithm is
bigger then the total load of any other algorithm, including
centralized onine solutions, by only O(n^2), while the maximum queue
size of our algorithm is at most O(n) plus the value which is at most
n times bigger than the maximum queue size of any other algorithm. The
optimality for both measures is justified by proving the
corresponding lower bounds. Next, we show that our algorithm is
stochastically optimal for any expected injection rate smaller or
equal to 1. To the best of our knowledge, this is the first solution
to the stochastic queuing problem on a multiple access channel that
achieves such optimality for the (highest possible) rate equal to 1.
This is joint work with Marcin Bienkowski, Tomasz Jurdzinski, and Dariusz Kowalski.
Intervenant: Miroslaw Korzeniowski |