Distributively-Competitive Online Paging for Arbitrary-Topology Networks (Extended Abstract)

) Baruch Awerbuch Yair Bartal y Amos Fiat y May 3, 1994 Abstract This paper gives first competitive distributed paging algorithm for the general network topology. The competitive ratios in storage and communication are poly-logarithmic in the total number of network nodes and the diameter of the network. Lab. for Computer Science, MIT. Supported by Air Force Contract TNDGAFOSR-86-0078, ARO contract DAAL03-86-K-0171, NSF contract 9114440-CCR, DARPA contract N00014-J-92-1799, and a special grant from IBM. E-mail: baruch@theory.lcs.mit.edu y Department of Computer Science, School of Mathematics, Tel-Aviv University, Tel-Aviv 69978, Israel. Supported by a grant from the Israeli Academy of Sciences. E-mail: yairb@math.tau.ac.il, fiat@math.tau.ac.il 1 INTRODUCTION 1 1 Introduction 1.1 Distributed Paging and Virtual Shared Memory Virtual addressing has the advantage that the physical address is separate from the logical address [TDMF62]: the name of a memory item is decoupled f..