Name
Abstract | ||
|---|---|---|
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 and we focus on anonymous networks. We establish several results. In particular, we prove that with weak sense of direction, the intuitive knowledge-computability hierarchy between levels of a priori structural knowledge collapses. A powerful implication is the formal proof that shortest path routing is possible in anonymous networks with sense of direction. We prove that weak sense of direction is computationally stronger than topological awareness. We also consider several fundamental problems; for each, we provide a complete characterization of the anonymous networks on which it is computable with sense of direction. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(02)00592-3 | Theoretical Computer Science |
Keywords | DocType | Volume |
powerful implication,complete characterization,weak sense,fundamental problem,communication complexity,large impact,formal proof,global consistency constraint,anonymous network,intuitive knowledge-computability hierarchy | Journal | 301 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 15 |
PageRank | References | Authors |
0.85 | 32 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paola Flocchini | 1 | 2421 | 157.13 |
| Alessandro Roncato | 2 | 320 | 20.21 |
| Nicola Santoro | 3 | 1145 | 55.49 |