Многоуровневые очереди с обратными связями: различия между версиями

Хотя алгоритмы без предвидения активно изучались в теории очередей в течение многих десятилетий, само это понятие было рассмотрено Мотвани, Филлипсом и Торнгом [5] относительно недавно в контексте конкурентного анализа. Как и в традиционном конкурентном анализе, без предвидения алгоритм называется c-конкурентным, если для каждого входного экземпляра его производительность не более чем в c раз ниже, чем у оптимального оффлайнового решения для этого экземпляра. Мотвани, Филлипс и Торнг показали следующее.

Не слишком удивительно, что любой детерминированный алгоритм должен иметь плохой коэффициент конкурентоспособности. Например, рассмотрим алгоритм MLF, у которого пороги являются степенями 2, то есть 1, 2, 4, ... Предположим, что <math>n = 2^k</math> заданий размера <math>2^k + 1</math> поступают в моменты времени <math>0, 2^k, 2 \cdot 2^k, ..., (2^k - 1)2^k</math>, соответственно. Тогда легко проверить, что средняя продолжительность потока для MLF равна <math>\Omega(n^2)</math>, тогда как у оптимального алгоритма она равна <math>\Omega(n)</math>.

Заметим, что MLF плохо работает на приведенном выше примере, поскольку все задания застревают в очереди до конца, когда у них остается всего одна единица работы. Любопытно, что Калянасундарам и Прухс [3] разработали рандомизированный вариант MLF (названный ими RMLF) и доказали, что его коэффициент конкурентоспособности почти оптимален. Для каждого задания <math>j</math> и для каждой очереди <math>Q_j</math> алгоритм RMLF устанавливает порог <math>t_{i, j}</math> случайно и независимо в соответствии с усеченным экспоненциальным распределением. Грубо говоря, задание случайного порога гарантирует, что если задание застряло в очереди, то оставшееся время его обработки будет составлять разумную долю от первоначального времени обработки.

'''Теорема 2 [3]. Алгоритм RMLF является O (log n log log n)-конкурентным относительно рассеянного соперника. Более того, алгоритм RMLF является O(log n log log n)-конкурентным даже относительно адаптивного соперника при условии, что соперник заранее выбирает все размеры заданий.'''

Позже Беккетти и Леонарди [1] показали, что на самом деле RMLF оптимально конкурентоспособен с точностью до постоянного коэффициента. Они также проанализировали RMLF на одинаковых параллельных машинах.

'''Теорема 3 [1]. Алгоритм RMLF является O(log n)-конкурентным для одной машины. Для нескольких одинаковых машин RMLF достигает коэффициента конкурентоспособности <math>O(log \; n \; log \Big( \frac{m}{n} \Big) )</math>, где m – количество машин.'''