The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms

The authors consider the k-server problem in a distributed setting. Given a network of n processors, and k identical mobile servers, requests for service appear at the processors and a server must reach the request point. Besides modeling problems in computer networks where k identical mobile resources are shared by the processors of the network, this models a realistic situation where the transfer of information is costly and there is no central control that governs the behavior of servers that move around to satisfy requests for service. The problem is that of devising algorithms that minimize not only the travel of the server but also the communication cost incurred for the transmission of control messages. The main contribution is a general translator to transform any deterministic global-control competitive k-server algorithm into a distributed competitive one. As consequences they get poly(k)-competitive distributed algorithms for the line, trees and the ring. >

Authors

• Yair Bartal
• Adi Rosén

Keywords

• Network servers
• Costs
• Mobile computing
• Centralized control
• Communication system control
• Computer networks
• Distributed algorithms
• Computer science
• Polynomials
• Space exploration
• Server Problem
• Lower Bound
• Cardinality
• Network Topology
• End Of Phase
• Total Distance
• Information Transfer
• Digital Networks
• Correction Algorithm
• Head And Tail
• Beginning Of Phase
• Mobile Users
• Simulation Run
• Online Server
• Distributed Algorithm
• First Move
• Disjoint Sets
• Simulated Sequences
• Service Requests
• Online Algorithm