網路上的訊息傳輸問題

Abstract

這篇論文的目的是在研究點不相交或線不相交路徑模式下的連接網路傳輸訊息的問題。在這個傳輸的模式下,一個步驟中一個或二個點經由一條路徑把他們的訊息傳給其他的點。如果有幾個點在點不相交或線不相交的路徑上,則他們可同步傳送。一個演算法的複雜度可用步驟的次數來衡量。 在這篇論文中,我們分別為一點傳送-點不相交模式跟一點傳送-線不相交模式設計線性時間的演算法來解決樹狀圖上的傳送問題。在二點傳送-點不相交的模式下,我們也設計最佳的方法來解決完全k樹狀圖和n維度格子圖上的傳送、聚集、散布問題。

The purpose of this thesis is to investigate the problem of dissemination of information among processors of interconnection networks under the communication mode in which communications are via vertex-disjoint or edge-disjoint paths. In this communication mode, in one communication step, one or two processors send their information to all other processors via a path. Several processors can send information at a same step if the paths used one vertex/edge-disjoint. The complexity of a communication algorithm is measured by the number of communication steps. In this thesis we design linear-time broadcast algorithms for trees in one-way listen-in vertex-disjoint mode and one-way listen-in edge-disjoint mode. We also design optimal broadcast, accumulation and gossip algorithms for complete k-ary trees and n-dimensional grid in two-way listen-in vertex-disjoint mode.