Article

Dynamic analysis of the arrow distributed protocol

Authors:

Fabian Kuhn,

Rogert WattenhoferAuthors Info & Claims

SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures

Pages 294 - 301

https://doi.org/10.1145/1007912.1007962

Published: 27 June 2004 Publication History

Get Access

Abstract

Arrow is a prominent distributed protocol which globally orders requests initiated by the nodes in a distributed system. In this paper we present a dynamic analysis of the Arrow protocol. We prove that Arrow is O(log D)-competitive, where D is the diameter of the spanning tree on which Arrow operates. In addition, we show that our analysis is almost tight by proving that for all trees the competitive ratio of Arrow is Ω(log D/log log D).

References

[1]

M. J. Demmer and M. Herlihy. The arrow distributed directory protocol. In International Symposium on Distributed Computing (DISC), pages 119--133, 1998.]]

Digital Library

Google Scholar

[2]

Y. Emek and D. Peleg. Approximating minimum max-stretch spanning trees on unweighted graphs. In Proceedings of 15th ACM-SIAM Sympos. Discrete Algorithms (SODA), 2004.]]

Digital Library

Google Scholar

[3]

D. Ginat, D. Sleator, and R. Tarjan. A tight amortized bound for path reversal. Information Processing Letters, 31(1):3--5, 1989.]]

Digital Library

Google Scholar

[4]

M. Herlihy. The aleph toolkit: Support for scalable distributed shared objects. In Workshop on Communication, Architecture, and Applications for Network-based Parallel Computing, Jan. 1999.]]

Digital Library

Google Scholar

[5]

M. Herlihy and S. Tirthapura. Self-stabilizing distributed queueing. In Proceedings of 15th International Symposium on Distributed Computing, Oct. 2001.]]

Digital Library

Google Scholar

[6]

M. Herlihy, S. Tirthapura, and R. Wattenhofer. Competitive Concurrent Distributed Queueing. In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pages 127--133, 2001.]]

Digital Library

Google Scholar

[7]

M. Herlihy, S. Tirthapura, and R. Wattenhofer. Ordered multicast and distributed swap. Operating Systems Review, 35(1):85--95, 2001. Also in the Proceedings of the PODC Middleware Symposium, Portland, Oregon, July 2000.]]

Digital Library

Google Scholar

[8]

M. Herlihy and M. P. Warres. A tale of two directories: implementing distributed shared objects in Java. Concurrency: Practice and Experience, 12(7):555--572, 2000.]]

Crossref

Google Scholar

[9]

K. Li and P. Hudak. Memory coherence in shared virtual memory systems. ACM Transactions on Computer Systems, 7(4), 1989.]]

Digital Library

Google Scholar

[10]

D. Peleg and E. Reshef. A Variant of the Arrow Distributed Directory Protocol With Low Average Complexity. In Proc. of the 26th Int. Colloquium on Automata Languages and Programming (ICALP), pages 615--624, 1999.]]

Digital Library

Google Scholar

[11]

K. Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1), 1989.]]

Digital Library

Google Scholar

[12]

R. Rosenkrantz, R. Stearns, and P. Lewis. An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM Journal on Computing, 6(3):563--581, 1977.]]

Crossref

Google Scholar

Cited By

View all

Batista ECoelho PAlchieri EDotti FPedone F(2023)FlexCastProceedings of the 24th International Middleware Conference10.1145/3590140.3629122(288-300)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629122
Khanchandani PRichter ORusch LWattenhofer R(2021)Learning Algorithms with Self-Play: A New Approach to the Distributed Directory Problem2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI52525.2021.00081(501-505)Online publication date: Nov-2021
https://doi.org/10.1109/ICTAI52525.2021.00081
Khanchandani PWattenhofer RScheideler CBerenbrink P(2019)The Arvy Distributed Directory ProtocolProceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323181(225-235)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323181
Show More Cited By

Index Terms

Dynamic analysis of the arrow distributed protocol
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

An Analysis Framework for Distributed Hierarchical Directories

We provide a novel analysis framework for distributed hierarchical directories for an arbitrary set of dynamic (online) requests. We first present a generic algorithm for implementing a distributed directory that can support dynamic requests and prove ...
Dynamic Analysis of the Arrow Distributed Protocol

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 ...
An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures

June 2004

332 pages

ISBN:1581138407

DOI:10.1145/1007912

General Chair:
Phil Gibbons
Intel Research
,
Program Chair:
Micah Adler
University of Massachusetts

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA04

Sponsor:

SPAA04: 16th ACM Symposium on Parallelism in Algorithms and Architectures 2004

June 27 - 30, 2004

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
299
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Batista ECoelho PAlchieri EDotti FPedone F(2023)FlexCastProceedings of the 24th International Middleware Conference10.1145/3590140.3629122(288-300)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629122
Khanchandani PRichter ORusch LWattenhofer R(2021)Learning Algorithms with Self-Play: A New Approach to the Distributed Directory Problem2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI52525.2021.00081(501-505)Online publication date: Nov-2021
https://doi.org/10.1109/ICTAI52525.2021.00081
Khanchandani PWattenhofer RScheideler CBerenbrink P(2019)The Arvy Distributed Directory ProtocolProceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323181(225-235)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323181
Busch CTirthapura S(2019)Concurrent counting is harder than queuingTheoretical Computer Science10.1016/j.tcs.2010.07.002411:43(3823-3833)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2010.07.002
Sharma GBusch C(2018)Distributed transactional memory for general networksDistributed Computing10.1007/s00446-014-0214-727:5(329-362)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00446-014-0214-7
Sharma GBusch C(2015)An Analysis Framework for Distributed Hierarchical DirectoriesAlgorithmica10.1007/s00453-013-9803-271:2(377-408)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s00453-013-9803-2
Attiya HGramoli VMilani A(2015)Directory Protocols for Distributed Transactional MemoryTransactional Memory. Foundations, Algorithms, Tools, and Applications10.1007/978-3-319-14720-8_17(367-391)Online publication date: 2015
https://doi.org/10.1007/978-3-319-14720-8_17
Sharma GBusch C(2014)Transactional memoryACM SIGACT News10.1145/2636805.263682445:2(74-103)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2636805.2636824
Sharma GBusch C(2013)An Analysis Framework for Distributed Hierarchical DirectoriesDistributed Computing and Networking10.1007/978-3-642-35668-1_26(378-392)Online publication date: 2013
https://doi.org/10.1007/978-3-642-35668-1_26
Welch JWalter J(2011)Link Reversal AlgorithmsSynthesis Lectures on Distributed Computing Theory10.2200/S00389ED1V01Y201111DCT0082:3(1-103)Online publication date: 31-Oct-2011
https://doi.org/10.2200/S00389ED1V01Y201111DCT008
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An Analysis Framework for Distributed Hierarchical Directories

Dynamic Analysis of the Arrow Distributed Protocol

An optimal distributed (Δ+1)-coloring algorithm?