Kosowski, Adrian; Małafiejski, Michał; Żyliński, Paweł 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]. Cited in 6 Documents 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 \textit{A. Kosowski} et al., Lect. Notes Comput. Sci. 3911, 1002--1009 (2006; Zbl 1182.68017) Full Text: DOI