以分散式方法偵測N─CUBE系統之錯誤節點

Abstract

本論文是探討如何偵測多維立方體（n-cube）系統中之錯誤節點，首先我們先研究多 維立方體錯誤節點偵測的一些基本性質，再來討論我們提出的方法及一些實驗數值。 由於在錯誤節點個沒有限制的情形下，該系統錯誤節點的偵測是一個NP-Complete 的 問題。在本論文中，我們是探討其錯誤節點個數有一上限時，如何找到一個方法能正 確地找到所有錯誤節點。對於多維立方體而言，它最多可以容許有n 個節點是壞的， 在這個前提之下，我們找到了一些特性，且根據這些特性提出了兩個解決方法。 第一個方法，我們利用兩兩之間的等位關係（equivalence relation），將多維立方 體之節點分開成一些等位集合（equivalence classes） 。由於此系統錯誤節點之上 限是n 個，所以只要節點數超過n 個等位集合，那麼這些節點均是好的。而且根據多 維立方體架構之特性我們證得僅有一個且恰有一個等位集合之節點數超過n ，所以我 們很明顯地將多維立方體上錯誤節點的偵測轉換成在多維立方體中找其最大等位集合 （maximum equivalence class）。而且亦證明當此最大等位集合之節點數超過（2-n -1） 時，其餘之節點均是壞的。這方法簡單又易懂。 第二個方法，我們採用階層我的偵測方法，逐步地去找錯誤的節點，並以實驗結果證 明，在平均狀況下，這個方法可以節省不少的測試次數。 對於我們所提出的兩個方法，我們均附上例子以便於了解程式運作之過程，而且也對 兩者所需之測試次數做了一些比較，並附上一些實驗數值以供參考。