The Library
An Omega(root log log n) lower bound for routing in optical networks
Tools
UNSPECIFIED (1998) An Omega(root log log n) lower bound for routing in optical networks. In: 1994 ACM Symposium on Parallel Algorithms and Architectures, CAPE MAY, NEW JERSEY, JUN 27-29, 1994. Published in: SIAM JOURNAL ON COMPUTING, 27 (4). pp. 1083-1098. ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
Optical communication is likely to significantly speed up parallel computation because the vast bandwidth of the optical medium can be divided to produce communication networks of very high degree. However, the problem of contention in high-degree networks makes the routing problem in these networks theoretically (and practically) difficult. In this paper we examine Valiant's h-relation routing problem, which is a fundamental problem in the theory of parallel computing. The h-relation routing problem arises both in the direct implementation of specific parallel algorithms on distributed-memory machines and in the general simulation of shared-memory models such as the PRAM on distributed-memory machines. In an h-relation routing problem each processor has up to h messages that it wishes to send to other processors and each processor is the destination of at most h messages. We present a lower bound for routing an h-relation (for any h > 1) on a complete optical network of size n. Our lower bound applies to any randomized distributed algorithm for this task. Specifically, we show that the expected number of communication steps required to route an arbitrary h-relation is Omega(h+ root log log n). This is the first known lower bound for this problem which does not restrict the class of algorithms under consideration.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | SIAM JOURNAL ON COMPUTING | ||||
Publisher: | SIAM PUBLICATIONS | ||||
ISSN: | 0097-5397 | ||||
Official Date: | August 1998 | ||||
Dates: |
|
||||
Volume: | 27 | ||||
Number: | 4 | ||||
Number of Pages: | 16 | ||||
Page Range: | pp. 1083-1098 | ||||
Publication Status: | Published | ||||
Title of Event: | 1994 ACM Symposium on Parallel Algorithms and Architectures | ||||
Location of Event: | CAPE MAY, NEW JERSEY | ||||
Date(s) of Event: | JUN 27-29, 1994 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |