In a distributed shared memory consisting of multiple processors, each of which
has its own local memories, each read-only page needs to be located at appropriate
processors by replication so as to make the total cost lower. The purpose of the page
replication problem is to implement this low-cost locating. This paper considers on-
line algorithms for this problem in terms of competitiveness, the ratio of the cost of
on-line algorithms to that of the off-line optimal algorithms.
Especially we apply randomized techniques developed for the page migration al-
gorithms to the page replication problem. As a result, we find randomized algo-
rithms for trees which break the deterministic lower bound. Moreover, memoryless
coin-flipping algorithms are investigated. We prove that a coin-flipping algorithm
is 2-competitive for trees. For circles, we develop a new generalized coin-flipping
algorithm that is 4-competitive. This new algorithm for circles has the lowest com-
petitive ratio among already known algorithms.