登入選單

返回Google圖書搜尋

Tolerating Faults in Synchronization Networks

University of Massachusetts at Amherst. Department of Computer and Information Science

出版	University of Massachusetts at Amherst, Department of Computer and Information Science, 1992
URL	http://books.google.com.hk/books?id=d83pGwAACAAJ&hl=&source=gbs_api

註釋

In the worst-case scenario, an N-PE SN whose edges have queues of capacity O(log log N) can tolerate the failure of a positive fraction of its PEs, no matter how the failed PEs are distributed; this capacity requirement cannot be lowered by more than a small constant factor. In the expected-case scenario, with probability exceeding 1 - N[superscript - [omega](1)], an N-PE SN whose edges have queues of capacity O(log log log N) can tolerate the failure of a positive fraction of its PEs; we do not know if this capacity requirement can be lowered. In the salvaging scenario, we present an algorithm that, given an SN with queues of capacity C, salvages a maximum number of fault-free PEs; the algorithm's time grows with the queue-capacity C, but is a low-degree polynomial in N even when C is as large as log(N/log N).