Lingering issues in distributed scheduling

Speaker : Florian Simatos
(Eindhoven University of Technology
Date: 19/03/2013
Time: 3:00 pm - 4:00 pm
Location: LINCS Meeting Room 40


Le prochain séminaire DYOGEN

Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the “cautious” activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-r), with r the load of the system, in contrast to the usual linear growth.
Motivated by that issue, I will discuss in this talk the extent to which more “aggressive” schemes can improve the delay performance. In the simplest possible scenario, I will show how aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, it can be proved that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-r) at a quadratic rate.