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 -