ON THE IMPACT OF SENSE OF DIRECTION ON MESSAGE COMPLEXITY

In this paper, we prove a general result on the impact of sense of dir ection, We show that, in arbitrary graphs, any sense of direction has a dramatic effect on the communication complexity of several important distributed problems: Broadcast, Depth First Traversal, Election, and Spanning Tree Construction. In systems with n nodes and e communicati on links, the solution for the Depth First Traversal and the Broadcast problems require Omega(e) messages with arbitrary labelings; we show that, with any sense of direction, they can be solved exchanging only Theta(n) messages, even if the system is anonymous. The problems of El ection and of Spanning Tree Construction require Omega(e + n log n) me ssages with arbitrary labelings; on the other hand, we show that they can be solved with Theta(n) messages with any sense of direction. The results presented here completely explain and generalize the existing results which now follow as corollaries for specific labelings. (C) 19 97 Elsevier Science B.V.