๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Computing on anonymous networks with sense of direction

โœ Scribed by Paola Flocchini; Alessandro Roncato; Nicola Santoro

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
358 KB
Volume
301
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

Distributed Computing on Anonymous Hyper
Distributed Computing on Anonymous Hypercube Networks
โœ Evangelos Kranakis; Danny Krizanc ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 245 KB

We consider the bit-complexity i.e.a, total number of bits transmitted of computing boolean functions on an anonymous canonically labeled n-dimensional hypercube network and give a characterization of the boolean functions computable on such a network as exactly those boolean functions which are inv

Minimal sense of direction in regular ne
Minimal sense of direction in regular networks
โœ Paola Flocchini ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 683 KB

A network is said to have Sense of Direction when the port labeling satisfies a particular set of global consistency constraints. In this paper we study the link between the topology of a system and the number of labels that are necessary to have a Sense of Direction in that system. We consider syst

Computing with Snakes in Directed Networ
Computing with Snakes in Directed Networks of Automata
โœ Shimon Even; Ami Litman; Peter Winkler ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 146 KB

We consider unidirectional, strongly connected networks of identical finite-state automata, of bounded in-and out-degree but unknown topology and unbounded size n. Protocols which are quadratic or linear in n are provided which accomplish the following tasks: wake up and report when done; construct

On the impact of sense of direction on m
On the impact of sense of direction on message complexity
โœ Paola Flocchini; Bernard Mans; Nicola Santoro ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 859 KB

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 Const

Adaptive parallel computing on heterogen
Adaptive parallel computing on heterogeneous networks with mpC
โœ Alexey Lastovetsky ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 290 KB

The paper presents a new advanced version of the mpC parallel language. The language was designed specially for programming high-performance parallel computations on heterogeneous networks of computers. The advanced version allows the programmer to define at runtime all the main features of the und