Abstract
在本論文中, 我們研究了分散式挑選問題 (distributed selection problem), 分散式凸殼問題(distributed convex hull problem),及分散式環網路分割問題(distri-buted ring network partition problem)o我們研究了這些問題之特性, 并提出解決這些問題之有效的分散式演算法(distributed algorithms)。給定一個通訊網路G=(V,E),其中V 是由節點(nodes) 所組成之集合, 而E 是由鍊結(links) 所組成之集合o 在此通訊網路上, 我們假設已經有一個有根延展樹(rootedspanning tree)o 另外給定一個由元素(elements)所組成之集合N,其元素分散地儲存在各個節點中o 分散式挑選問題就是要找出N 中的第K 小元素(the k-th smallestelement)o在分散式凸殼問題中, N 是由平面點(planar points) 所組成之集合, 且各點分散地儲存在各個節點中o 而分散式凸殼問題就是要找出這些點中的凸殼o在分散式環網路分割問題中, 一個環網路被分割成次鍊條(subchains)o對于每一個分割, 我們有一個通訊成本(communication cost)o 分散式環網路分割問題就是要找出一個分割, 使得其相對應的通訊成本最小o