DOC PREVIEW
Concurrent Counting is Harder than Queuing

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Concurrent Counting is Harder than QueuingSrikanta Tirthapura1,CostasBusch21Iowa State University2Rensselaer Polytechnic Inst.Dept. of Elec. and Computer Engg. Computer Science DepartmentAmes, IA 50010 Troy, NY [email protected] [email protected] both distributed counting and queuing, processorsin a distributed system issue oper ations which are orga-nized into a total order. In counting, each processor re-ceives the rank of its operation in the total order, whereas in queuing, a processor gets back the identity of itspredecessor in the total order. Coordination applica-tions such as totally ordered multicast can be solved us-ing either distributed counting or queuing, and it wouldbe very useful to definitively know which of counting orqueuing is a harder problem.We conduct the first systematic study of the relativecomplexities of distributed counting and queuing in aconcurrent setting. Our results show that concurrentcounting is harder than c oncurrent queuing on a va-riety of processor inter connection topologies, includinghigh diameter graphs such as the list and the mesh,and low diameter graphs such as the c omplete graph,perfect m-ary tree, and the hypercube. For all thesetopologies, we show that the concurrent delay complex-ity of a particular solution to queuing, the arrow pro-tocol, is asymptotically smal ler than a lower bound onthe complexity of any solution to counting. As a con-sequence, we are able to definitively say that given achoice between applying counting or queuing to solve adistributed c oordination pr oblem, queuing is the bettersolution.1. IntroductionThis paper compares the complexities of two funda-mental distributed coordination problems, distributedqueuing and distributed counting. In distributedThe work of the authors was supported in part through NSFgrants CNS 0520102 and CNS 0520009.counting, processors in a network increment (perhapsconcurrently) a globally unique shared counter. Eachprocessor in return receives the value of the counterafter its increment operation took effect. Equivalently,the operations issued by processors are arranged intoa total order, and each processor in return receives therank of its operation in the total order. Distributedcounting is a very well studied problem, and many solu-tions have been proposed, perhaps the most prominentbeing Counting Networks [1].In distributed queuing, similar to counting, proces-sors issue operations which are organized into a totalorder (or a “distributed queue”). However, in contrastwith counting, each processor receives the identity of itspredecessor operation in the total order (see Figure 1).Distributed queuing has also been studied under manyguises, for example in distributed directories [4], or intoken based mutual exclusion [10]. One of the most ef-ficient solutions for queuing is the arrow protocol, dueto Raymond [10].In many situations, distributed coordination can beachieved using either queuing or counting. For exam-ple, total ly ordered multicast requires that all messagesmulticast to a group be delivered in the same order atall receivers. The conventional solution to totally or-dered multicast uses distributed counting: the senderof a multicast message obtains a sequence number froma distributed counter, and attaches it to the messagebeing multicast. Different receivers may receive thesame set of messages in different orders, but they de-liver them to the application in the order of the se-quence numbers attached to the messages. The co-ordination part in this application is essentially dis-tributed counting. Herlihy et al. [8] pointed out thattotally ordered multicast can be solved using queuingtoo: the sender of a multicast message obtains the idof the predecessor message using distributed queuing,and attaches it to the multicast message. Different re-1-4244-0054-6/06/$20.00 ©2006 IEEEbdeccount=2count=1acount=3bdecpred = cpred = apred = noneaAfter Counting After QueuingInitial StateabcdeFigure 1. Counting and Queuing. The graph represents the processor interconnection network. Solidnodes issue counting (or queuing) operations, while the white nodes do not. The total order is a,c,eand “pred” means predecessor.ceivers may again receive messages in different orders,but they deliver them to the application in a consistentorder that is reconstructed by using the predecessor in-formation that is piggybacked on the messages. Her-lihy et al. [8] mention that the queuing based solutionto ordered multicast is potentially more efficient thanthe counting based solution, but were unable to provesuch a fact. Knowing that counting is inherently harderthan queuing would imply that the queuing based so-lution is better than the counting based one. It wouldalso suggest that it is worth reexamining if countingbased solutions to other problems can be replaced withqueuing based ones.At the heart of both queuing and counting lies theformation of a total order among operations issued byprocessors in a distributed system. But these problemsdiffer in the information that the nodes learn about thetotal order. In counting, each processor receives someglobal information about the total order, in the formof the rank of the operation. In contrast, in queuing,each processor receives the identity of its operation’spredecessor in the total order, which gives the proces-sor only a local view of the total order. This suggeststhat counting might be an inherently “harder” coordi-nation problem than queuing. However, there are noknown efficient reductions between the two problems,which will help us prove such a result (by an ”efficient”reduction we mean a reduction that will not introducemuch additional delay). Knowing the identity of anoperation’s neighbors in the total order tells us littleabout its rank, and vice versa.1.1. Our ResultsWe show that for a large class of interconnectiontopologies, concurrent counting has inherently greaterdelay than concurrent queuing. Our result shows thatthe queuing based solution for ordered multicast is bet-ter than the counting based one for many interconnec-tion networks, and suggests that given a choice betweenqueuing and counting to solve any coordination prob-lem, queuing is often the better solution.We study the delay of concurrent queuing andcounting, and analyze the concurrent one-shot sce-nario, where all the operations are issued at the sametime, and no more operations are issued thereafter. Weuse a synchronous model,


Concurrent Counting is Harder than Queuing

Download Concurrent Counting is Harder than Queuing
Our administrator received your request to download this document. We will send you the file to your email shortly.
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 2 2 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?