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.DISC.2017.22
URN: urn:nbn:de:0030-drops-79857
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7985/
Go to the corresponding LIPIcs Volume Portal

Ghodselahi, Abdolhamid ; Kuhn, Fabian

Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks

pdf-format:
LIPIcs-DISC-2017-22.pdf (0.5 MB)

Abstract

The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem by using path reversal on a pre-computed spanning tree (or any other tree topology simulated on top of the given network).

It is known that the Arrow protocol solves the problem with a competitive ratio of O(log D) on trees of diameter D. This implies a distributed queueing algorithm with competitive ratio O(s log D) for general networks with a spanning tree of diameter D and stretch s. In this work we show that when running the Arrow protocol on top of the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC'03], we obtain a randomized distributed online queueing algorithm with expected competitive ratio O(log n) against an oblivious adversary even on general n-node network topologies. The result holds even if the queueing requests occur in an arbitrarily dynamic and concurrent fashion and even if communication is asynchronous. The main technical result of the paper shows that the competitive ratio of the Arrow protocol is constant on a special family of tree topologies, known as hierarchically well separated trees.

BibTeX - Entry

@InProceedings{ghodselahi_et_al:LIPIcs:2017:7985,
  author =	{Abdolhamid Ghodselahi and Fabian Kuhn},
  title =	{{Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7985},
  URN =		{urn:nbn:de:0030-drops-79857},
  doi =		{10.4230/LIPIcs.DISC.2017.22},
  annote =	{Keywords: Arrow protocol, competitive analysis, distributed queueing, shared objects, tree embeddings}
}

Keywords: Arrow protocol, competitive analysis, distributed queueing, shared objects, tree embeddings
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

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