  This work is a continuation of efforts to define and understand competitive
analysis of algorithms in a distributed shared memory setting, which is
surprisingly different from the classical online setting. In fact, in a
distributed shared memory setting, we find a counter-example to the theorem
concerning classical randomized online algorithms which shows that, if there is
a $c$-competitive randomized algorithm against an adaptive offline adversary,
then there is a $c$-competitive deterministic algorithm [Ben-David, Borodin,
Karp, Tardos, Wigderson, 1994]. In a distributed setting, there is additional
lack of knowledge concerning what the other processes have done. There is also
additional power for the adversary, having control of the scheduler which
decides when each process is allowed to take steps.
  We consider the list accessing problem, which is a benchmark problem for
sequential online algorithms. In the distributed version of this problem, each
process has its own finite sequence of requests to a shared list. The scheduler
arises as a major issue in its competitive analysis. We introduce two different
adversaries, which differ in how they are allowed to schedule processes, and
use them to perform competitive analysis of distributed list accessing. We
prove tight upper and lower bounds on combinatorial properties of merges of the
request sequences, which we use in the analysis. Our analysis shows that the
effects of the adversarial scheduler can be quite significant, dominating the
usual quality loss due to lack of information about the future.
