TY - GEN
T1 - The power of multimedia
T2 - 7th Annual ACM Symposium on Principles of Distributed Computing, PODC 1988
AU - Afek, Yehuda
AU - Landau, Gad M.
AU - Schieber, Baruch
AU - Yung, Moti
N1 - Funding Information:
‘AT&T Bell Labs., 600 Mountain Ave., Murray Hill, NJ 079’74. +Courant Institute of Mathematical Sciences, 251 Mercer St., New York Univ., New York, NY 10012. The research of this author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U. S. Department of Energy, under contract number DE-AC02 76ERO3077 $IBM Research Division, T.J. Watson Research Center, P.O.Box 218, .Yorktown Heights, NY 10598.
Publisher Copyright:
© 1988 ACM.
PY - 1988/1/1
Y1 - 1988/1/1
N2 - In this paper we introduce a new network model called a multimedia network. It combines the point-to-point message passing network and the multiaccess channel. To benefit from the combination we design algorithms which consist of two stages: a local stage which utilizes the parallelism of the point-to-point network and a global stage which utilizes the broadcast capability of the multiaccess channel. As a reasonable approach, one wishes to balance the complexities of the two stages by obtaining an efficient partition of the network into O(√n) connected components each of radius O(√n). To this end we present efficient deterministic and randomized partitioning algorithms. The deterministic algorithm runs in O(√n log∗ n) time and O(m + n log n log∗ n) messages, where n and m are the number of nodes and number of point-to-point links in the network. The randomized algorithm runs in the same time, but sends only O(m+ n log∗ n) messages. The partitioning algorithms are then used to obtain: (1) O(√n log n log∗ n) time deterministic and O(√n log∗ n) time randomized algorithms for computing global sensitive functions, and (2) O(√n log n) time deterministic algorithm for computing a minimum spanning tree. An Ω(n) time lower bounds for computing global sensitive functions in both point-topoint and multiaccess networks, are given, thus showing that the multimedia network is more powerful than both its separate components. Furthermore, we prove an Ω(√n) time lower bound for multimedia networks, thus leaving a small gap between our upper and lower bounds.
AB - In this paper we introduce a new network model called a multimedia network. It combines the point-to-point message passing network and the multiaccess channel. To benefit from the combination we design algorithms which consist of two stages: a local stage which utilizes the parallelism of the point-to-point network and a global stage which utilizes the broadcast capability of the multiaccess channel. As a reasonable approach, one wishes to balance the complexities of the two stages by obtaining an efficient partition of the network into O(√n) connected components each of radius O(√n). To this end we present efficient deterministic and randomized partitioning algorithms. The deterministic algorithm runs in O(√n log∗ n) time and O(m + n log n log∗ n) messages, where n and m are the number of nodes and number of point-to-point links in the network. The randomized algorithm runs in the same time, but sends only O(m+ n log∗ n) messages. The partitioning algorithms are then used to obtain: (1) O(√n log n log∗ n) time deterministic and O(√n log∗ n) time randomized algorithms for computing global sensitive functions, and (2) O(√n log n) time deterministic algorithm for computing a minimum spanning tree. An Ω(n) time lower bounds for computing global sensitive functions in both point-topoint and multiaccess networks, are given, thus showing that the multimedia network is more powerful than both its separate components. Furthermore, we prove an Ω(√n) time lower bound for multimedia networks, thus leaving a small gap between our upper and lower bounds.
UR - http://www.scopus.com/inward/record.url?scp=5844317469&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=5844317469&partnerID=8YFLogxK
U2 - 10.1145/62546.62560
DO - 10.1145/62546.62560
M3 - Conference contribution
AN - SCOPUS:5844317469
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 90
EP - 104
BT - Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing, PODC 1988
PB - Association for Computing Machinery
Y2 - 15 August 1988 through 17 August 1988
ER -