TY - JOUR

T1 - The power of multimedia

T2 - Combining point-to-point and multiaccess networks

AU - Afek, Yehuda

AU - Landau, Gad M.

AU - Schieber, Baruch

AU - Yung, Moti

N1 - Funding Information:
* A preliminary version of this work appeared in Afek et al. (1988). ’ Present address: Dept. of Computer Science, Tel Aviv Univ., Tel Aviv, Israel 69978. r The research of this author is supported by NSF grant NSF-CCR-8908286, and by NY State Sciences & Technology Foundation-Center for Advanced Technology in Telecommunications, Polytechnic Univ. ’ Part of the work of this author was done at IBM Almaden Research Center.

PY - 1990/1

Y1 - 1990/1

N2 - This paper introduces 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, the designed algorithms 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. To balance the complexities of the two stages a partition of the network into O( n) connected components each of radius O( n) is required. We present efficient deterministic and randomized partitioning algorithms that run in ( n log* n) time. The deterministic algorithm sends O(m + n log n log* n) messages, while the randomized algorithm sends only O(m + n log* n) messages. (n and m are the number of nodes and point-to-point links in the network.) 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) An O( n log n) time deterministic algorithm for computing a minimum spanning tree. We give Ω(n) time lower bounds for computing global sensitive functions in both point-to-point and multiaccess networks, thus showing that the multimedia network is more powerful than both its separate components. Furthermore, we prove and Ω( n) time lower bound for computing global sensitive functions in multimedia networks, thus leaving a small gap between our upper and lower bounds.

AB - This paper introduces 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, the designed algorithms 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. To balance the complexities of the two stages a partition of the network into O( n) connected components each of radius O( n) is required. We present efficient deterministic and randomized partitioning algorithms that run in ( n log* n) time. The deterministic algorithm sends O(m + n log n log* n) messages, while the randomized algorithm sends only O(m + n log* n) messages. (n and m are the number of nodes and point-to-point links in the network.) 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) An O( n log n) time deterministic algorithm for computing a minimum spanning tree. We give Ω(n) time lower bounds for computing global sensitive functions in both point-to-point and multiaccess networks, thus showing that the multimedia network is more powerful than both its separate components. Furthermore, we prove and Ω( n) time lower bound for computing global sensitive functions in multimedia networks, thus leaving a small gap between our upper and lower bounds.

UR - http://www.scopus.com/inward/record.url?scp=0025257644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025257644&partnerID=8YFLogxK

U2 - 10.1016/0890-5401(90)90035-G

DO - 10.1016/0890-5401(90)90035-G

M3 - Article

AN - SCOPUS:0025257644

VL - 84

SP - 97

EP - 118

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 1

ER -