The power of multimedia: Combining point-to-point and multiaccess networks

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.