✦ LIBER ✦

On the impact of sense of direction on message complexity

✍ Scribed by Paola Flocchini; Bernard Mans; Nicola Santoro

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 859 KB
Volume: 63
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00091-4

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we prove a general result on the impact of sense of direction. 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 communication links, the solution for the Depth First Traversal and the Broadcast problems require fI( e) messages with arbitrary labelings; we show that, with any sense of direction, they can be solved exchanging only 0 (n) messages, even if the system is anonymous. The problems of Election and of Spanning Tree Construction require a( e + n log n) messages with arbitrary labelings; on the other hand, we show that they can be solved with 0 (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. @ 1997 Elsevier Science B.V.

📜 SIMILAR VOLUMES

Computing on anonymous networks with sen

Computing on anonymous networks with sense of direction

✍ Paola Flocchini; Alessandro Roncato; Nicola Santoro 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 358 KB

Sense of direction refers to a set of global consistency constraints of the local labeling of the edges of a network. Sense of direction has a large impact on the communication complexity of many distributed problems. In this paper, we study the impact that sense of direction has on computability an

The impact of immigrants on the sense of

The impact of immigrants on the sense of community

✍ Isabel Hombrados-Mendieta; Luis Gomez-Jacinto; Juan Manuel Dominguez-Fuentes 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract This study investigated the sense of community among residents in the Spanish city of Malaga and the relationship between the components of the sense of community and the quality of life. Given that the phenomenon of immigration is a fact of city life, the authors examine how such coexi

Minimizing message complexity of partial

Minimizing message complexity of partially replicated data on hypercubes

✍ Humenik, Keith; Matthews, Peter; Stephens, A. B.; Yesha, Yelena 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 663 KB

Within the framework of distributed and parallel computing, we consider partially replicated data on a hypercube. We address the problem of placing copies on the hypercube in order to minimize message complexity. With realistic restrictions on the read/write ratio and the number of copies, we find t

The impact of programming methodology on

The impact of programming methodology on program complexity

✍ D.L. Carver; D.B. Simmons 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 1014 KB

Impact of message compression on the sca

Impact of message compression on the scalability of an atmospheric modeling application on clusters

✍ V. Santhosh Kumar; R. Nanjundiah; M.J. Thazhuthaveetil; R. Govindarajan 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 211 KB

Impact of communications on the complexi

Impact of communications on the complexity of the Parallel Gaussian Elimination

✍ E. Bampis; J.C. Konig; D. Trystram 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 275 KB

This paper presents an extension to the complexity analysis of parallel algorithms on MIMD computers with a shared-memory system which takes into account communications. This analysis shows that the well-known asymptotically optimal results are insufficient because we show that the overhead is in O(