Fulltext

Dynamic Analysis of the Arrow Distributed Protocol

Herlihy, Maurice ; Kuhn, Fabian ; Tirthapura, Srikanta ; Wattenhofer, Roger

In: Theory of Computing Systems, 2006, vol. 39, no. 6, p. 875-901

Add to personal list
    Title
    • Dynamic Analysis of the Arrow Distributed Protocol
    Author
    • Herlihy, Maurice. Computer Science Department, Brown University, Providence, RI 02912, USA
    • Kuhn, Fabian. Microsoft Research - Silicon Valley, Mountain View, CA 94043, USA
    • Tirthapura, Srikanta. Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50011, USA
    • Wattenhofer, Roger. Computer Engineering and Networks Laboratory, ETH Zurich, CH-8092, Zurich, Switzerland
    Document Type
    • Postprint
    Language
    • English
    Published in
    • Theory of Computing Systems, 2006, vol. 39, no. 6, p. 875-901. Springer-Verlag; www.springer-ny.com
    Other Version
    Classification
    • Computer science
    OAI-PMH Identifier
    • oai:doc.rero.ch:319995
    Summary
    Distributed queuing is a fundamental coordination problem that arises in a variety of applications, including distributed directories, totally ordered multicast, and distributed mutual exclusion. The arrow protocol is a solution to distributed queuing that is based on path reversal on a pre-selected spanning tree of the network. We present a novel and comprehensive competitive analysis of the arrow protocol. We consider the total cost of handling a finite number of queuing requests, which may or may not be issued concurrently, and show that the arrow protocol is $O(s\cdot \log D)$ -competitive to the optimal queuing protocol, where s and D are the stretch and the diameter, respectively, of the spanning tree. In addition, we show that our analysis is almost tight by proving that for every spanning tree chosen for execution, the arrow protocol is $\Omega(s \cdot \log(D/s)/{\log}\log(D/s))$ -competitive to the optimal queuing protocol. Our analysis reveals an intriguing connection between the arrow protocol and the nearest neighbor traveling salesperson tour on an appropriately defined graph