  This paper considers a natural generalization of the online list access
problem in the paid exchange model, where additionally there can be precedence
constraints ("dependencies") among the nodes in the list. For example, this
generalization is motivated by applications in the context of packet
classification. Our main contributions are constant-competitive deterministic
and randomized online algorithms, designed around a procedure
Move-Recursively-Forward, a generalization of Move-To-Front tailored to handle
node dependencies. Parts of the analysis build upon ideas of the classic online
algorithms Move-To-Front and BIT, and address the challenges of the extended
model. We further discuss the challenges related to insertions and deletions.
