Sense of Direction and Communication Complexity in Distributed Networks
Nicola Santoro, Jorge Urrutia, Shmuel Zaks · McGill-Queen's University Press eBooks · 1986
The connection between sense of direction and communication complexity in distributed complete networks is studied for two basic problems: finding a minimum-weight spanning tree (MST) and finding a spanning tree (SP). Several models of the complete network are defined, the difference being the amount (and type) of sense of direction available, forming a hierarchy which includes the models previously studied in the literature. It is shown that to move up in the hierarchy might require Ω(n2) messages in the worst case. It is shown that the existing O(n) bound for SP can still be achieved at a lower level in the hierarchy; and that the Ω(n2) bound for MST still holds at a higher level in the hierarchy.