Description
Compared to a standard parallel queueing system, with requests deterministically assigned to queues, it has been observed that the high probability extremal queue length substantially drops if arriving requests are allowed some freedom to choose.
More precisely, with N servers and within polynomial time in N, the standard log N order drops to log log N if every request independently checks C>1 random queues (before joining the shortest among them), as you would do at ALDI, as shown by Luczak and McDiarmid (2006).
We now interpolate between the two dynamics, requiring the collections of queues checked to change "slowly" over time, described by dynamically evolving hyperedges of a hypergraph. We are interested in how this affects the extremal queue length.
Joint work with John Fernley.
Az előadás helyszíne: ELTE TTK Déli tömb, harmadik emelet, D 3-316 terem (1117 Budapest, Pázmány Péter sétány 1/c)