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 - 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 -