| Available via | http://dbpubs.stanford.edu/pub/2003-63 |
|
Submitted on |
10th of September 2003 |
|
Author |
Thomas Dilys, Motwani Rajeev |
|
Title |
Caching Queues in Memory Buffers |
|
Date of publication |
2003 |
|
Published in |
SODA 2004 |
|
Citation |
Thomas Dilys, Motwani Rajeev. Caching Queues in Memory Buffers, SODA 2004 |
|
Number of pages |
10 |
|
Language |
English |
|
Project |
STREAM |
|
Type |
Conference or Journal Paper |
|
Subject group |
Data Streams |
|
Abstract |
Maintaining queues in a small and fast memory cache with large but
slow secondary storage is an important problem that occurs in many
contexts like DataStream systems \cite{stream,aurora,eddies,gigascope,niagaracq}, Network Router
design \cite{sundar,devavrat,george} and Distributed Messaging systems
\cite{mqseries}. At any clock-tick any number of tuples may enter the various
queues, and a single tuple is consumed from the head of one of the
queues. However since the number of unconsumed tuples may exceed
the size of the memory buffer, some of the tuples in the queues will have
to be written-out to secondary storage and then later read-in back
into memory for consumption. The only constraint is that tuples
written-out and then read-in should not be written-out again to avoid
thrashing. The aim of the algorithm is to minimize the cost of the
reads and writes to secondary storage. We provide online competitive
algorithms for different cost models for reads and writes. For the cost model in which
each read/write has unit cost (as present day disks are modelled) we
provide a 2-competitive online algorithm and show a matching lower
bound for maintaining a single queue. For n queues when a single
read(write) can only access contiguous tuples from a single queue, we
provide a 2n-competitive algorithm and prove a $\sqrt n$ lower bound
if the heads of different queues are consumed in round-robin. On the
other hand for adverserial consumption, we show that it is not
possible to even have a o(M) competitive online algorithm,
where M the size of the memory is much larger than the number of
queues, n. However if the online algorithm is given extra M/2 memory
then then we show a 2n-competitive algorithm. For the
extended cost model where the cost of the read(write) depends on the
number of blocks written out we provide a 4-competitive algorithm.
These algorithms will be implemented in the Stanford Stream system |
|
Keywords |
Online Algorithms, Data Streams, Caching, Queues, Theory, Systems |
|
Contact address |
dilys@stanford.edu |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |