A PARALLEL LIST UPDATE PROBLEM

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.