TY - GEN

T1 - Concurrent counting is harder than queuing

AU - Tirthapura, Srikanta

AU - Busch, Costas

PY - 2006

Y1 - 2006

N2 - In both distributed counting and queuing, processors in a distributed system issue operations which are organized into a total order. In counting, each processor receives the rank of its operation in the total order, where as in queuing, a processor gets back the identity of its predecessor in the total order. Coordination applications such as totally ordered multicast can be solved using either distributed counting or queuing, and it would be very useful to definitively know which of counting or queuing is a harder problem. We conduct the first systematic study of the relative complexities of distributed counting and queuing in a concurrent setting. Our results show that concurrent counting is harder than concurrent queuing on a variety of processor interconnection topologies, including high diameter graphs such as the list and the mesh, and low diameter graphs such as the complete graph, perfect m-ary tree, and the hypercube. 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. As a consequence, we are able to definitively say that given a choice between applying counting or queuing to solve a distributed coordination problem, queuing is the better solution.

AB - In both distributed counting and queuing, processors in a distributed system issue operations which are organized into a total order. In counting, each processor receives the rank of its operation in the total order, where as in queuing, a processor gets back the identity of its predecessor in the total order. Coordination applications such as totally ordered multicast can be solved using either distributed counting or queuing, and it would be very useful to definitively know which of counting or queuing is a harder problem. We conduct the first systematic study of the relative complexities of distributed counting and queuing in a concurrent setting. Our results show that concurrent counting is harder than concurrent queuing on a variety of processor interconnection topologies, including high diameter graphs such as the list and the mesh, and low diameter graphs such as the complete graph, perfect m-ary tree, and the hypercube. 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. As a consequence, we are able to definitively say that given a choice between applying counting or queuing to solve a distributed coordination problem, queuing is the better solution.

UR - http://www.scopus.com/inward/record.url?scp=33847165352&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847165352&partnerID=8YFLogxK

U2 - 10.1109/IPDPS.2006.1639327

DO - 10.1109/IPDPS.2006.1639327

M3 - Conference contribution

AN - SCOPUS:33847165352

SN - 1424400546

SN - 9781424400546

T3 - 20th International Parallel and Distributed Processing Symposium, IPDPS 2006

BT - 20th International Parallel and Distributed Processing Symposium, IPDPS 2006

PB - IEEE Computer Society

T2 - 20th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2006

Y2 - 25 April 2006 through 29 April 2006

ER -