DocumentCode
1990839
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
fYear
2008
fDate
1-5 July 2008
Firstpage
449
Lastpage
453
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel and Distributed Computing, 2008. ISPDC '08. International Symposium on
Conference_Location
Krakow
Print_ISBN
978-0-7695-3472-5
Type
conf
DOI
10.1109/ISPDC.2008.27
Filename
4724280
Link To Document