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 -