(3.236.175.108) 您好!臺灣時間:2021/02/27 06:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:傳金泉
研究生(外文):FU,JIN-QUAN
論文名稱:一個非集中控制之分散式排序演算法的設計
指導教授:許健平許健平引用關係
指導教授(外文):XU,JIAN-PING
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊及電子工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1990
畢業學年度:78
語文別:中文
論文頁數:41
中文關鍵詞:非集中控制分散式排序演算法容錯能力擴充性高維立方體呼叫回應環狀網路
相關次數:
  • 被引用被引用:0
  • 點閱點閱:178
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由於分散式系統具有較佳的容錯能力及擴充性使得此系統越來越受到重視。在分散式
系統中,為了提高系統的使用效率一個檔案時常被分成多個部份分別分佈在多個不同
的節點上。
在這種情形之下,由於在每個節點只有部份的檔案可使用,有時候我們必須藉著多個
甚至所有節點的合作才能解決使用者對此分散檔所發出的質問。如果此分散檔案是任
意分佈的,解決這類質問的資訊傳遞量就需較多,但是如果這個檔案是按照其鍵值的
某一順序排序的,我們就可以用較少的資訊傳遞來解決對此檔案所發出的質問。
在本論文中,我們將討論將一個原先任意分佈之分散檔案根據一個給定的排列在網路
上排序。我們的目標是在不使用過多額外記憶體的限制下,降低由排序過程所產生的
交通荷。我們提出了一個非集中式控制分散式排序演算法。我們的策略是基於分散式
第K 小選擇演算法和分制分割及征服策略。我們的演算法的優點是在排序過程,不使
用過多額外記憶體而且交通負擔是平均分佈在整個網路上。除此之外,我們的演算法
亦具有高度的平行性,此特性亦可降低排序過程所需之時間。對於一個分佈於d 個節
點由N 個記錄構成的大型檔案,在呼叫回應(Shout-edho)網路上,最差的狀況下,我
們的演算法的交通複雜度是O(N+ log( ))。當我們考慮點對點(Point-to-point)
網路,最差的狀況下,在環狀網路(ring)加構下,我們的演算法所需要的交通複雜度
為O( N+ d (logd) long ( )+ );在高維立方體(hypercube) 架構下,則需要O
(Nlogd+ logdlog( ))。
50006196
50006196

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔