Document Open Access Logo

Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks

Authors Abdolhamid Ghodselahi, Fabian Kuhn

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.22.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Abdolhamid Ghodselahi
Fabian Kuhn

Cite As Get BibTex

Abdolhamid Ghodselahi and Fabian Kuhn. Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.22

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.

Subject Classification

Keywords
  • Arrow protocol
  • competitive analysis
  • distributed queueing
  • shared objects
  • tree embeddings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. I. Abraham, D. Dolev, and D. Malkhi. LLS: a locality aware location service for mobile ad hoc networks. In D-POMC co-located 10th C. Mobicom, pages 75-84, 2004. Google Scholar
  2. H. Attiya, V. Gramoli, and A. Milani. A provably starvation-free distributed directory protocol. In Proc. of the 12th Symp. on Self-Stabilizing Syst. (SSS), pages 405-419, 2010. Google Scholar
  3. B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st Symp. Foundations of Computer Science (FOCS), pages 503-513, 1990. Google Scholar
  4. Baruch Awerbuch and David Peleg. Online tracking of mobile users. Journal of the ACM (JACM), 42(5):1021-1058, 1995. Google Scholar
  5. Y. Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proc. 37th Symp. on Foundations of Computer Science (FOCS), pages 184-193, 1996. Google Scholar
  6. D. Chaiken, C. Fields, K. Kurihara, and A. Agarwal. Directory-based cache coherence in large-scale multiprocessors. Computer, 23(6):49-58, 1990. Google Scholar
  7. M. Demirbas et al. A hierarchy-based fault-local stabilizing algorithm for tracking in sensor networks. In P. 8th I. C. on Princ. of Dist. Syst. (OPODIS), pages 299-315, 2004. Google Scholar
  8. Michael J Demmer and Maurice P Herlihy. The arrow distributed directory protocol. In Proc. of the 12th Symp. on Dist. Comp. (DISC), pages 119-133, 1998. Google Scholar
  9. J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proc. 35th S. on Th. of Comp. (STOC), pages 448-455, 2003. Google Scholar
  10. Mohsen Ghaffari and Christoph Lenzen. Near-optimal distributed tree embedding. In International Symposium on Dist. Comp., pages 197-211, 2014. Google Scholar
  11. Abdolhamid Ghodselahi and Fabian Kuhn. Dynamic analysis of the arrow distributed directory protocol in general networks. arXiv preprint arXiv:1705.07327, 2017. Google Scholar
  12. David Ginat, Daniel D Sleator, and Robert E Tarjan. A tight amortized bound for path reversal. Information Processing Letters, 31(1):3-5, 1989. Google Scholar
  13. A. Gupta. Steiner poi,nts in tree metrics don't (really) help. In Proc. 12th Symp. on Discrete Algorithms (SODA), pages 220-227, 2001. Google Scholar
  14. M. Herlihy, F. Kuhn, S. Tirthapura, and R. Wattenhofer. Dynamic analysis of the arrow distributed protocol. Theory of Comp. Syst. (TCS), 39(6):875-901, 2006. Google Scholar
  15. M. Herlihy, S. Tirthapura, and R. Wattenhofer. Competitive concurrent distributed queuing. In Proc. of the 20th Symp. on Princ. of Dist. Comp. (PODC), pages 127-133, 2001. Google Scholar
  16. Maurice Herlihy. The Aleph toolkit: Support for scalable distributed shared objects. In Proc. 3rd Workshop on Comm. Arch. and Appl. for Network-Based Parallel Comp. (CANPC), pages 137-149, 1999. Google Scholar
  17. Maurice Herlihy and Ye Sun. Distributed transactional memory for metric-space networks. Distributed Computing, 20(3):195-208, 2007. Google Scholar
  18. Maurice Herlihy, Srikanta Tirthapura, and Rogert Wattenhofer. Ordered multicast and distributed swap. ACM SIGOPS Operating Syst. Rev. (OSR), 35(1):85-96, 2001. Google Scholar
  19. Maurice Herlihy and Michael P Warres. A tale of two directories: implementing distributed shared objects in java. In Proc. of the ACM Conf. on Java Grande, pages 99-108, 1999. Google Scholar
  20. Kai Li and Paul Hudak. Memory coherence in shared virtual memory systems. ACM Trans. on Computer Syst. (TOCS), 7(4):321-359, 1989. Google Scholar
  21. Mohamed Naimi and Michel Trehel. An improvement of the log n distributed algorithm for mutual exclusion. In Proc. 7th Conf. on Distr. Comp. Sys. (ICDCS), pages 371-377, 1987. Google Scholar
  22. D. Peleg and E. Reshef. A variant of the arrow distributed directory with low average complexity. In Proc. of the 26th Int. Coll. on A. L. and P. (ICALP), pages 615-624, 1999. Google Scholar
  23. Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete and Computational Geometry, (19), 1998. Google Scholar
  24. Kerry Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Trans. on Computer Syst. (TOCS), 7(1):61-77, 1989. Google Scholar
  25. R. Rosenkrantz, R. Stearns, and P. Lewis. An analysis of several heuristics for the traveling salesman problem. SIAM J. on Computing, 6(3):563-581, 1977. Google Scholar
  26. Gokarna Sharma and Costas Busch. Distributed transactional memory for general networks. Distributed Computing, 27(5):329-362, 2014. Google Scholar
  27. Gokarna Sharma and Costas Busch. An analysis framework for distributed hierarchical directories. Algorithmica, 71(2):377-408, 2015. Google Scholar
  28. Srikanta Tirthapura and Maurice Herlihy. Self-stabilizing distributed queuing. IEEE Trans. on Parallel and Dist. Syst. (PDS), 17(7):646-655, 2006. Google Scholar
  29. Jan L. A. van de Snepscheut. Fair mutual exclusion on a graph of processes. Distributed Computing, 2(2):113-115, 1987. Google Scholar
  30. B. Zhang and B. Ravindran. Dynamic analysis of the relay cache-coherence protocol for distributed transactional memory. In Proc. of the 24th IPDPS, pages 1-11, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact