Options
Concurrent distributed serving with mobile servers
Citation Link: https://doi.org/10.15480/882.2589
Publikationstyp
Conference Paper
Date Issued
2019-12-01
Sprache
English
Author(s)
Institut
TORE-DOI
TORE-URI
First published in
Number in series
149
Article Number
53
Citation
Leibniz International Proceedings in Informatics, LIPIcs (149): 53 (2019-12-01)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are k identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol Gnn that solves the DSMS problem on overlay trees. We prove that Gnn is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze Gnn for “one-shot” executions, i.e., all requests are invoked simultaneously. We prove that when running Gnn on top of a special family of tree topologies - known as hierarchically well-separated trees (HSTs) - we obtain a randomized distributed protocol with an expected competitive ratio of O(log n) on general network topologies with n processors. From a technical point of view, our main result is that Gnn optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of Ω(maxk, log n/log log n) on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.
Subjects
Amortized analysis
Asynchronous communication
Distributed directory
Distributed online resource allocation
Tree embeddings
DDC Class
004: Informatik
More Funding Information
Deutsche Forschungsgemeinschaft (DFG)
Loading...
Name
LIPIcs-ISAAC-2019-53.pdf
Size
807.09 KB
Format
Adobe PDF