文章基本信息

标题：Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
本地全文：下载
作者：Abdolhamid Ghodselahi ; Fabian Kuhn
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：91
页码：22:1-22:16
DOI：10.4230/LIPIcs.DISC.2017.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Arrow protocol; competitive analysis; distributed queueing; shared objects; tree embeddings