License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.53
URN: urn:nbn:de:0030-drops-115497
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11549/
Go to the corresponding LIPIcs Volume Portal

Ghodselahi, Abdolhamid ; Kuhn, Fabian ; Turau, Volker

Concurrent Distributed Serving with Mobile Servers

pdf-format:
LIPIcs-ISAAC-2019-53.pdf (0.8 MB)

Abstract

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 Omega(max {k, 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.

BibTeX - Entry

@InProceedings{ghodselahi_et_al:LIPIcs:2019:11549,
  author =	{Abdolhamid Ghodselahi and Fabian Kuhn and Volker Turau},
  title =	{{Concurrent Distributed Serving with Mobile Servers}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{53:1--53:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11549},
  URN =		{urn:nbn:de:0030-drops-115497},
  doi =		{10.4230/LIPIcs.ISAAC.2019.53},
  annote =	{Keywords: Distributed online resource allocation, Distributed directory, Asynchronous communication, Amortized analysis, Tree embeddings}
}

Keywords: Distributed online resource allocation, Distributed directory, Asynchronous communication, Amortized analysis, Tree embeddings
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI