View Full Document

Concurrent Counting is Harder than Queuing



View the full content.
View Full Document
View Full Document

1 views

Unformatted text preview:

Concurrent Counting is Harder than Queuing Srikanta Tirthapura1 Costas Busch2 1 Iowa State University Dept of Elec and Computer Engg Ames IA 50010 snt iastate edu Abstract 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 de nitively know which of counting or queuing is a harder problem We conduct the rst 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 de nitively say that given a choice between applying counting or queuing to solve a distributed coordination problem queuing is the better solution 1 Introduction This paper compares the complexities of two fundamental distributed coordination problems distributed queuing and distributed counting In distributed The work of the authors was supported in part through NSF grants CNS 0520102 and CNS 0520009 1 4244 0054 6 06 20 00 2006 IEEE 2 Rensselaer Polytechnic Inst Computer Science Department Troy NY 12180 buschc cs rpi edu counting processors in a network increment perhaps concurrently a globally unique shared counter Each processor in return



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Concurrent Counting is Harder than Queuing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Concurrent Counting is Harder than Queuing and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?