# Concurrent Counting is Harder than Queuing

**View the full content.**View Full Document

0 0 10 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 receives the value of the counter after its increment operation took e ect Equivalently the operations issued by processors are arranged into a total order and each processor in return receives the rank of its operation in the total order Distributed counting is a very well studied problem and many solutions have been proposed perhaps the most prominent being Counting Networks 1 In distributed queuing similar to counting processors issue operations which are organized into a total order or a distributed queue However in contrast with counting each processor receives the identity of its predecessor operation in the total order see Figure 1 Distributed queuing has also been studied under many guises for example in distributed directories 4 or in token based mutual exclusion 10 One of the most ef cient solutions for queuing is the arrow protocol due to Raymond 10 In many situations distributed coordination can be achieved using either queuing or counting For example totally ordered multicast requires that all messages multicast to a group be delivered in the same order at all receivers The conventional solution to totally ordered multicast uses distributed counting the sender of a multicast message obtains a sequence number from a distributed counter and attaches it to the message being multicast Di erent receivers may receive the same set of messages in di erent orders but they deliver them to the application in the order of the sequence numbers attached to the messages The coordination part in this application is essentially distributed counting Herlihy et al 8 pointed out that totally ordered multicast can be solved using queuing too the sender of a multicast message obtains the id of the predecessor message using distributed queuing and attaches it to the multicast message Di erent re a a a pred none count 1 b b c b c count 2 c pred a e d Initial State e d count 3 After Counting d e pred c After Queuing Figure 1 Counting and Queuing The graph represents the processor interconnection network Solid nodes issue counting or queuing operations while the white nodes do not The total order is a c e and pred means predecessor ceivers may again receive messages in di erent orders but they deliver them to the application in a consistent order that is reconstructed by using the predecessor information that is piggybacked on the messages Herlihy et al 8 mention that the queuing based solution to ordered multicast is potentially more e cient than the counting based solution but were unable to prove such a fact Knowing that counting is inherently harder than queuing would imply that the queuing based solution is better than the counting based one It would also suggest that it is worth reexamining if counting based solutions to other problems can be replaced with queuing based ones At the heart of both queuing and counting lies the formation of a total order among operations issued by processors in a distributed system But these problems di er in the information that the nodes learn about the total order In counting each processor receives some global information about the total order in the form of the rank of the operation In contrast in queuing each processor receives the identity of its operation s predecessor in the total order which gives the processor only a local view of the total order This suggests that counting might be an inherently harder coordination problem than queuing However there are no known e cient reductions between the two problems which will help us prove such a result by an e cient reduction we mean a reduction that will not introduce much additional delay Knowing the identity of an operation s neighbors in the total order tells us little about its rank and vice versa 1 1 Our Results We show that for a large class of interconnection topologies concurrent counting has inherently greater delay than concurrent queuing Our result shows that the queuing based solution for ordered multicast is better than the counting based one for many interconnection networks and suggests that given a choice between queuing and counting to solve any coordination problem queuing is often the better solution We study the delay of concurrent queuing and counting and analyze the concurrent one shot scenario where all the operations are issued at the same time and no more operations are issued thereafter We use a synchronous model where the link delays are predictable The delay of an operation is the time till it receives its response