β Scribed by Y.J. Han; Y. Igarashi; K. Kanai; K. Miura
No coin nor oath required. For personal study only.
We discuss the fault tolerance of an information disseminating scheme in a processor network called a binary jumping network. The following results are shown. Let (N) be the number of processors in the network. When (N) is a power of (2, \log _{2} N+f+1) rounds suffice for broadcasting in the binary jumping network if at most (f) processors and/or links have failed and (f \leq \log _{2} N-1). For an arbitrary (\left.N, \mid \log _{2} N\right\rceil+f+2) rounds suffice for broadcasting in the binary jumping network if at most (f) processors and/or links have failed and (f \leq\left|\log _{2} N\right|-2). For an arbitrary (N) and (f=) (\left\lceil\log _{2} N\right\rceil-1,3\left[\log _{2} N\right\rceil) rounds suffice for sending a message to a destination with a certain distance from the source processor. This result implies that for some (N) and arbitrary (f=\left|\log _{2} N\right|-1), (3 / \log _{2} N I) rounds suffice for broadcasting. For other (N) and arbitrary (f=\left\lceil\log _{2} N\right\rceil-1), the bound given in this paper is larger than (3 \mid \log _{2}) NI. 1994 Academic Press. Inc.
π SIMILAR VOLUMES
We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B
This note describes an algorithm for broadcasting a message on the \(n\)-dimensional hypercube in optimal time ( \(n\) time units) and optimal communication ( \(2^{n}-1\) messages) in the presence of up to \(n-2\) arbitrary node or edge faults, assuming the set of faults is known to all nodes of the
computing. Therefore, it is necessary to compute important primitive functions even in the presence of faults. The hypercube network is quite robust [2,20]; in fact, at least n faults are needed to disconnect Q n into two components. The symmetry and robustness of hypercube can be exploited to compu