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.

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.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier B.V.

Language

en

File Format

application/pdf

Published Version

Share

COinS