The Distributedk-Server Problem—A Competitive Distributed Translator fork-Server Algorithms

✍ Scribed by Yair Bartal; Adi Rosén

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 243 KB
• Volume: 23
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0826

✦ Synopsis

Algorithms Ž .

x 11 1990 , 208᎐230 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. In addition to 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. We give a general translator to transform any deterministic global-control competitive k-server algorithm into a distributed com-Ž . petitive one. As consequences we get poly k -competitive distributed algorithms for the line, trees, and the ring. In contrast to the global-control case where there are k-server algorithms with competitive ratio that depends solely on k, we have Ž Ä Ž . Ž .4. a lower bound of ⍀ max k, 1rD и log nrlog log n on the competitive ratio of any distributed k-server algorithm, where 1rD is the ratio between the cost to transmit a message and the cost to move a server over the same distance. We also give a distributed version of the Harmonic randomized k-server algorithm.