Given a set of n.m elements arranged in n lists of m elements L1...L(n
), and a sequence of requests R = R(1)R(2)..., where R(i) is a set of
n elements to be retrieved in the lists, we discuss how to execute eac
h R(i) in parallel. L(1)...L(n) are stored in the shared memory of an
n-processor EREW-PRAM. After R(i) has been executed; the lists are upd
ated with a move to front (MTF) strategy; then R(i+1) can be processed
. An amortized analysis shows that the proposed algorithm is (n(2)+1)-
competitive against a static optimal algorithm, while a lower bound 2n
is proved. The use of randomization allows to decrease the competitiv
ity factor to 9/2 n, versus a lower bound 3/2 n.