×

Parallel processing subsystems with redundancy in a distributed environment. (English) Zbl 1182.68017

Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 6th international conference, PPAM 2005, Poznań, Poland, September 11–14, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-34141-2/pbk). Lecture Notes in Computer Science 3911, 1002-1009 (2006).
Summary: We consider the problem of dividing a distributed system into subsystems for parallel processing with redundancy for fault tolerance, where every subsystem has to consist of at least three units. We prove that the problem of determining the maximum number of subsystems with redundancy for fault tolerance is NP-hard even in cubic planar 2-connected system topologies. We point out that this problem is APX-hard on cubic bipartite graphs. At last, for subcubic topologies without units connected to only one other unit, we give a linear time 4/3-approximation algorithm.
For the entire collection see [Zbl 1103.68013].

MSC:

68M14 Distributed systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI