Content

•  
   1 Introduction
•  
   1.1 Static networks
•  
   1.1.1 Competitive analysis
•  
   1.2 Dynamic networks
•  
   1.2.1 Our model
•  
   1.2.2 Our contribution
•  
   1.3 Related work
•  
   1.4 Bibliographical notes
•  
  2 Basics
•  
   2.1 Optimal offline solution
•  
   2.2 Reduction Lemma
•  
   2.3 Two-node networks
•  
   2.3.1 Randomized algorithm EDGE
•  
   2.3.2 Lower bound for oblivious adversary
•  
  2.4 Trivial algorithms
•  
   2.4.1 Algorithm JUMP
•  
   2.4.2 Reusing Page Migration algorithms
•  
   3 Adversarial Scenario
•  
   3.1 Randomization against adaptive adversary
•  
   3.1.1 Algorithm DIST
•  
   3.1.2 DIST in the first part of a step
•  
   3.1.3 DIST in the second part of a step
•  
   3.1.4 Combining DIST with other algorithms
•  
   3.2 Marking algorithms
•  
   3.2.1 Deterministic algorithm MARK
•  
   3.2.2 Randomization against oblivious adversary
•  
   3.2.3 Proofs of Phase Lemmas
•  
   3.3 Lower bounds
•  
   3.3.1 Lower bound against adaptive-online adversary
•  
   3.3.2 Lower bound against oblivious adversary
•  
   3.4 Concluding remarks
•  
   3.5 Proofs of technical claims
•  
   4 Brownian Motion Scenario
•  
   4.1 Majority algorithms
•  
   4.1.1 Epochs
•  
   4.1.2 Competitiveness of MAJ
•  
   4.2 Bounding cost of MAJ
•  
   4.3 Bounding cost of OPT
•  
   4.3.1 Narrow sets
•  
   4.3.2 Precondition: smooth movement
•  
   4.3.3 Precondition: scattered nodes
•  
   4.3.4 Proof of the Crucial Property
•  
   4.4 Extensions and conclusions
•  
   4.5 Proofs of technical claims
•  
   5 Stochastic Requests Scenario
•  
   5.1 Lower bound for the extended cost model
•  
   5.2 Algorithm MTFR
•  
   5.2.1 Lower bound for OPT
•  
   5.2.2 Upper bound for MTFR
•  
   5.2.3 Expected competitive ratio
•  
   5.3 Extensions and conclusions
•  
   5.4 Proofs of technical claims
•  
   5.4.1 Proof of the concentration bound
•  
   6 Summary and Outlook
•  
   Bibliography
•  
  Appendix
•  
   A.1 Notations
•  
   A.2 Mathematical tools