Heat & Dump: Competitive Distributed Paging

This paper gives a randomized competitive distributed paging algorithm called Heat and Dump, The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to within a constant factor. This is in contrast to the linear optimal deterministic competitive ratio. >

Authors

• Baruch Awerbuch
• Yair Bartal
• Amos Fiat

Keywords

• Contracts
• File servers
• Computer science
• Cost function
• Memory management
• Runtime
• Programming profession
• Phase change random access memory
• Algorithm design and analysis
• Electronic mail
• Constant Factor
• Network Capacity
• Distributed Algorithm
• Competitive Ratio
• End Of Phase
• Hallucinations
• Global Strategy
• Local Strategies
• Head And Tail
• Local Algorithm
• Beginning Of Phase
• Previous Phase
• Local Issues
• Phase Sequence
• Local Memory
• Online Algorithm
• Parallel Machines
• Virtual Memory