Abstract
在這篇論文□，我們提出以虛耗訊息來評估分散式演算法。以往，人們在分析分散式演算法時，通常只以全部訊（mdssage ）的總合多寡，亦即訊息複雜度（communica-tion complexity ）來評估。然而一般情況下，訊息複可分成二種，一是必要訊息，另一為虛耗訊息。所謂必要訊息，乃是完成工作任務所必需的訊息，反之其他訊息就是虛耗訊息。因此任何一個分散式演算法所能做的只是儘量降低虛耗訊息的數量。所以我們認為以虛耗訊息複雜度來評估分散式演算法是一個相當合理的方式。此外，我們也提出了兩個演算法來解決在有d 個處理機的串聯區域網路上（seriallyconnected local area network ）的排序問題。第一個演算法為分散式奇偶變位排序演算法，這是一個以奇偶變位排序（odd even transposition sort ）為基礎的演算法，它不只達到了最佳訊息複雜度和時間複雜度，而且只有０（d ）的虛耗訊息，這項結困遠較以往其他演算法為佳。此外，當虛耗訊息最重要的考慮因素時，那麼第二個演算法－－分散式循環排序演算法，也就更適合了。因為在時間複雜度增加的情況下，只有０（d ）虛耗訊息，這是最佳的虛耗訊息複雜度。