@inproceedings{6291e2890c4340b59d10e732f1b8c75b,
title = "Optimal online buffer scheduling for block devices",
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.",
keywords = "buffer management, online algorithms, online primal-dual, reordering buffer, sorting buffer",
author = "Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald R{\"a}cke",
year = "2012",
doi = "10.1145/2213977.2214031",
language = "English",
isbn = "9781450312455",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "589--598",
booktitle = "STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing",
note = "44th Annual ACM Symposium on Theory of Computing, STOC '12 ; Conference date: 19-05-2012 Through 22-05-2012",
}