Uniform d-emulations of rings, with an application to distributed virtual ring construction

✍ Scribed by Erwin M. Bakker; Jan van Leeuwen

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 981 KB
• Volume: 23
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230230405

✦ Synopsis

Emulations are a special kind of structure-preserving mappings between processor interconnection networks (graphs). In this paper, the notion of emulation is generalized to the notion of d-emulation for any d 2 1. Several problems concerning the complexity of (uniform) d-emulations are studied. It is shown that the problem of deciding for arbitrary graphs H and G whether H can be uniformly demulated on G is NP-complete for every fixed d E N. Also, it is shown that the problem of deciding for arbitrary rings R and planar graphs G whether R can be uniformly 2-emulated on G is NPcomplete. Further, a constructive proof is given of the fact that there always exists a uniform 3emulation of a ring R o n a graph G = (V, E ) if IVR( = k. IVGl and k E N. This uniform 3-emulation of R on G is used as the basis for the Distributed Virtual Ring Construction Algorithm that only uses 21EI messages of 0(1) bits and has time complexity I 2((VI -1). A traversal of the constructed virtual ring costs 2((V( -1) messages. o 1993 John wi/ey & Sons, Inc.