在這篇論文中，我們討論了在分散式網路系統下，如何解決選第ｋ大值的問題（Dis-
tributed ｋ th-selection problem），由於這個問題在一般網路架構下並不容易解
，所以我們有興趣的是在三個不同的架構下：環狀（Ring）、匯流排（Bus ）以及s-
hout-echo 。以下針對這三種架構，提出不同的解法，同時也分析了其複雜性（Com-
plexity ）以及說明解法的正確性。最後並且歸納了一些共同的特性。
首先定義所謂在分散式網路系統下的選第ｋ大值的問題：假設在網路下，給予ｄ個節
（node），而每一個節點分別包含了不同個數的值，我們想求的是在這樣的網路下，
第ｋ大的值究竟是什麼？在單一的計算機下，這個問題己經有了不錯的解法，但在分
散式系統下，較少有研究。
這篇論文共分五章，第一章給予問題的定義；第二章提出在環狀結構網路下的解決方
法，一共有七種方法提出來，並且在最後一章做模擬測試（Simulation），發現一些
有趣的現象；第三章提出在shout-echo架構下的解決方法，除了已有的一些有趣方法
外，我們還發現一個定理，可以做很好的前置作業（preprocessing ），並且運用第
二章的想法，也得到一個最佳計算方法；第囡章中對匯流排網路，提出兩個方法去求
第ｋ大值，同時也比較它們之間的複雜性；在最後一章中，我們歸納前面三章所提出
的方法，發現了兩個有用的觀點：巨觀（Macroscopic）與微觀（Microscopic ）。
在巨觀法下可發現在這個問題所提出的解法，若不是分散性（Distributed ）的控制
方式，便是有一個主管計算方法過程的節點去控制的方式（Centralized ）。而在微
觀法下，我們歸納出四種有用的訊息形態（Message Type），可以做為解決第ｋ大值
問題的一種工具。
結論是希望對這個問題所歸納的巨觀與微觀法，能夠給以後想要在分散式系統上提出
解決問題方法的人，一個入門得導引。
|