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