Construction of the Mesh and the Torus Tolerating a Large Number of Faults
- Tamaki, Hisao
DOIAbstract
AbstractSuppose ach node (and each edge) of a network is independently faulty with probability at mostp(andq, respectively), where 0<p,q<1 are arbitrary constants independent of the size of the network. For each fixed integerd⩾2, we construct a network withO(N) nodes and with degreeO(loglogN) such that, after removing all the faulty nodes and edges, it still contains theN-noded-dimensionalN1/d×…×N1/dtorus, and hence the mesh of the same size, with probability 1−N−Ω(loglogN). This is derived as a consequence of a simple constant-degree construction which tolerates random faults, where the failure probability of each node isO(log−3d N). We also give a simple constant-degree construction withO(N) nodes that toleratesO(N(1−2−d)/d) worst case fa...
Add to ORKG