Title :
Randomized Online File Allocation on Uniform Ring Networks
Author :
Matsubayashi, Akira ; Kawamura, Yasuyuki
Author_Institution :
Div. of Electr. Eng. & Comput. Sci., Kanazawa Univ., Kanazawa, Japan
Abstract :
We study the online file allocation problem on ring networks. In this paper, we present a 7-competitive randomized algorithm against an adaptive online adversary on uniform ring networks. The algorithm is deterministic if the file size is 1. Moreover, we obtain lower bounds of 4.25 and 3.833 for a deterministic algorithm and a randomized algorithm against an adaptive online adversary, respectively, on ring networks.
Keywords :
deterministic algorithms; file organisation; randomised algorithms; adaptive online adversary; deterministic algorithm; randomized algorithm; randomized online file allocation; uniform ring networks; Computer science; Concurrent computing; Distributed computing; File servers; Internet; Joining processes; Multicast algorithms; Multicast communication; Unicast; data management; file allocation; online algorithm; ring network;
Conference_Titel :
Parallel and Distributed Computing, 2008. ISPDC '08. International Symposium on
Conference_Location :
Krakow
Print_ISBN :
978-0-7695-3472-5
DOI :
10.1109/ISPDC.2008.27
