Optimal online buffer scheduling for block devices

Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

7 Zitate (Scopus)

Abstract

We introduce a buffer scheduling problem for block operation devices in an online setting. We consider a stream of items of different types to be processed by a block device. The block device can process all items of the same type in a single step. To improve the performance of the system a buffer of size k is used to store items in order to reduce the number of operations required. Whenever the buffer becomes full a buffer scheduling strategy has to select one type and then a block operation on all elements with this type that are currently in the buffer is performed. The goal is to design a scheduling strategy that minimizes the number of block operations required. In this paper we consider the online version of this problem, where the buffer scheduling strategy must make decisions without knowing the future items that appear in the input stream. Our main result is the design of an O(log log k)-competitive online randomized buffer scheduling strategy. The bound is asymptotically tight. As a byproduct of our LP-based techniques, we obtain a randomized offline algorithm that approximates the optimal number of block operations to within a constant factor.

OriginalspracheEnglisch
TitelSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Seiten589-598
Seitenumfang10
DOIs
PublikationsstatusVeröffentlicht - 2012
Veranstaltung44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, USA/Vereinigte Staaten
Dauer: 19 Mai 201222 Mai 2012

Publikationsreihe

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Konferenz

Konferenz44th Annual ACM Symposium on Theory of Computing, STOC '12
Land/GebietUSA/Vereinigte Staaten
OrtNew York, NY
Zeitraum19/05/1222/05/12

Fingerprint

Untersuchen Sie die Forschungsthemen von „Optimal online buffer scheduling for block devices“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren