TY - JOUR
T1 - Concurrent counting is harder than queuing
AU - Busch, Costas
AU - Tirthapura, Srikanta
N1 - Funding Information:
We thank Eric Ruppert and Maurice Herlihy for helpful discussions. The first author is supported in part through NSF grant CNS 0520009. The second author is supported in part through NSF grant CNS 0520102.
PY - 2010/10/9
Y1 - 2010/10/9
N2 - 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.
AB - 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.
KW - Distributed algorithms
KW - Distributed counting
KW - Distributed data structures
KW - Distributed queuing
UR - http://www.scopus.com/inward/record.url?scp=77957302046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77957302046&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2010.07.002
DO - 10.1016/j.tcs.2010.07.002
M3 - Article
AN - SCOPUS:77957302046
SN - 0304-3975
VL - 411
SP - 3823
EP - 3833
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 43
ER -