Campus Units
Electrical and Computer Engineering, Computer Science
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
10-9-2010
Journal or Book Title
Theoretical Computer Science
Volume
411
Issue
43
First Page
3823
Last Page
3833
DOI
10.1016/j.tcs.2010.07.002
Abstract
We compare the complexities of two fundamental distributed coordination problems, distributed counting and distributed queuing, in a concurrent setting. In both distributed counting and queuing, processors in a distributed system issue operations which are organized into a total order. In counting, each participating processor receives the rank of its operation in the total order, where as in queuing, a processor receives the identity of its predecessor in the total order. Many coordination applications can be solved using either distributed counting or queuing, and it is useful to know which of counting or queuing is the easier problem.
Our results show that concurrent counting is harder than concurrent queuing on a variety of processor interconnection topologies, including high and low diameter graphs. For all these topologies, we show that the concurrent delay complexity of a particular solution to queuing, the arrow protocol, is asymptotically smaller than a lower bound on the complexity of any solution to counting.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Copyright Owner
Elsevier B.V.
Copyright Date
2010
Language
en
File Format
application/pdf
Recommended Citation
Busch, Costas and Tirthapura, Srikanta, "Concurrent counting is harder than queuing" (2010). Electrical and Computer Engineering Publications. 178.
https://lib.dr.iastate.edu/ece_pubs/178
Comments
This is a manuscript of an article published as Busch, Costas, and Srikanta Tirthapura. "Concurrent counting is harder than queuing." Theoretical Computer Science 411, no. 43 (2010): 3823-3833. DOI: 10.1016/j.tcs.2010.07.002. Posted with permission.