Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.2589
Publisher DOI: 10.4230/LIPIcs.ISAAC.2019.53
Title: Concurrent distributed serving with mobile servers
Language: English
Authors: Ghodselahi, Abdolhamid 
Kuhn, Fabian 
Turau, Volker 
Keywords: Amortized analysis;Asynchronous communication;Distributed directory;Distributed online resource allocation;Tree embeddings
Issue Date: 1-Dec-2019
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
Source: Leibniz International Proceedings in Informatics, LIPIcs (149): 53 (2019-12-01)
Part of Series: Leibniz International Proceedings in Informatics (LIPIcs) 
Volume number: 149
Abstract (english): 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.
Conference: 30th International Symposium on Algorithms and Computation, ISAAC 2019 
URI: http://hdl.handle.net/11420/4437
DOI: 10.15480/882.2589
ISBN: 978-3-95977-130-6
ISSN: 1868-8969
Institute: Telematik E-17 
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
Funded by: Deutsche Forschungsgemeinschaft (DFG)
Project: Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken 
Fehlertolerante verteilte Algorithmen 
License: CC BY 3.0 (Attribution) CC BY 3.0 (Attribution)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
LIPIcs-ISAAC-2019-53.pdf807,09 kBAdobe PDFThumbnail
View/Open
Show full item record

Google ScholarTM

Check

Note about this record

Export

This item is licensed under a Creative Commons License Creative Commons