𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Determination of the topology of a directed network

✍ Scribed by Darin Goldstein

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
198 KB
Volume
88
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We consider strongly-connected, directed networks of identical synchronous, finite-state processors with in-and outdegree uniformly bounded by a network constant. Via a straightforward extension of Ostrovsky and Wilkerson's Backwards Communication Algorithm [Proc. 14th Annual Symp. on Principles of Distributed Computing, 1995], we exhibit a protocol which solves the Global Topology Determination Problem, the problem of having a root processor map the global topology of a network of unknown size and topology, with running time O(ND) where N represents the number of processors and D represents the diameter of the network. A simple counting argument suffices to show that the Global Topology Determination Problem has time-complexity (N log N) which makes the protocol presented asymptotically time-optimal for many large networks.

πŸ“œ SIMILAR VOLUMES

Effect of the topology on the gaussian e
Effect of the topology on the gaussian elasticity of a network. The example of a fractal topology
✍ Jacques Bastide; FranΓ§ois BouΓ© πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 696 KB

## Abstract By considering fractal topologies of polymer networks, we show that one can obtain much smaller values of the elastic modulus than predicted by classical models for the same density of crosslinks. In a regular fractal such as the Sierpinski gasket, one can replace the segments joining t