Fault and adversary tolerance as an emergent property of distributed systems' software architectures

ABSTRACT

Fault and adversary tolerance have become not only desirable but required properties of software systems because mission-critical systems are commonly distributed on large networks of insecure nodes. In this paper, we describe how the tile style, an architectural style designed to distribute computation, can inject fault and adversary tolerance. The result is a notion of tolerance that is entirely abstracted away from the functional properties of the software system. The client may specify what fraction of the network is faulty or malicious (e.g., 25%) and the acceptable system failure rate (e.g., 2^-10), and the system's architecture adjusts automatically to ensure a failure rate no higher than the one specified. The technique is entirely automated and consists of a "smart redundancy" mechanism that brings the failure rate exponentially close to 0 by slowing down the execution speed linearly.

REFERENCES

• 1: Leonard M. Adleman, Molecular computation of solutions to combinatorial problems, Science, v.266 n.11, p.1021-1024, Nov. 1994
• 2: Leonard M. Adleman , Jarkko Kari , Lila Kari , Dustin Reishus, On the Decidability of Self-Assembly of Infinite Ribbons, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.530-537, November 16-19, 2002
• 3: Len Bass , Paul Clements , Rick Kazman, Software architecture in practice, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 4: Yuriy Brun, Arithmetic computation in the tile assembly model: Addition and multiplication, Theoretical Computer Science, v.378 n.1, p.17-31, June, 2007 [doi>10.1016/j.tcs.2006.10.025]
• 5: Yuriy Brun, A Discreet, Fault-Tolerant, and Scalable Software Architectural Style for Internet-Sized Networks, Companion to the proceedings of the 29th International Conference on Software Engineering, p.83-84, May 20-26, 2007 [doi>10.1109/ICSECOMPANION.2007.12]
• 6: Y. Brun. Nondeterministic polynomial time factoring in the tile assembly model. Technical Report USC-CSSE-2007-707, Center for Software Engineering, University of Southern California, 2007.
• 7: Y. Brun. Solving NP-complete problems in the tile assembly model. Technical Report USC-CSSE-2007-703, Center for Software Engineering, University of Southern California, 2007.
• 8: Yuriy Brun , Nenad Medvidovic, An Architectural Style for Solving Computationally Intensive Problems on Large Networks, Proceedings of the 2007 International Workshop on Software Engineering for Adaptive and Self-Managing Systems, p.2, May 20-26, 2007 [doi>10.1109/SEAMS.2007.4]
• 9: Y. Brun and N. Medvidovic. Discreetly distributing computation via self-assembly. Technical Report USC-CSSE-2007-714, Center for Software Engineering, University of Southern California, 2007.
• 10: H.-L. Chen and A. Goel. Error free self-assembly with error prone tiles. In Proceedings of the 10th International Meeting on DNA Based Computers (DNA04), Milan, Italy, June 2004.
• 11: Evaluating software architectures: methods and case studies, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 12: Premkumar T. Devanbu , Stuart Stubblebine, Software engineering for security: a roadmap, Proceedings of the Conference on The Future of Software Engineering, p.227-239, June 04-11, 2000, Limerick, Ireland [doi>10.1145/336512.336559]
• 13: Felix C. Gärtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Computing Surveys (CSUR), v.31 n.1, p.1-26, March 1999 [doi>10.1145/311531.311532]
• 14: Sam Malek , Marija Mikic-Rakic , Nenad Medvidovic, A Style-Aware Architectural Middleware for Resource-Constrained, Distributed Systems, IEEE Transactions on Software Engineering, v.31 n.3, p.256-272, March 2005 [doi>10.1109/TSE.2005.29]
• 15: Chris A. Mattmann , Daniel J. Crichton , Nenad Medvidovic , Steve Hughes, A software architecture-based framework for highly distributed and data intensive scientific applications, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134400]
• 16: Marija Mikic-Rakic , Nikunj Mehta , Nenad Medvidovic, Architectural style requirements for self-healing systems, Proceedings of the first workshop on Self-healing systems, November 18-19, 2002, Charleston, South Carolina [doi>10.1145/582128.582138]
• 17: Dewayne E. Perry , Alexander L. Wolf, Foundations for the study of software architecture, ACM SIGSOFT Software Engineering Notes, v.17 n.4, p.40-52, Oct. 1992 [doi>10.1145/141874.141884]
• 18: J. H. Reif, S. Sahu, and P. Yin. Compact error-resilient computational DNA tiling assemblies. In Proceedings of the 10th International Meeting on DNA Based Computers (DNA04), Milan, Italy, June 2004.
• 19: Paul W. K. Rothemund , Erik Winfree, The program-size complexity of self-assembled squares (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.459-468, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335358]
• 20: Chiyoung Seo , Sam Malek , George Edwards , Daniel Popescu , Nenad Medvidovic , Brad Petrus , Sharmila Ravula, Exploring the Role of Software Architecture in Dynamic and Fault Tolerant Pervasive Systems, Proceedings of the 1st International Workshop on Software Engineering for Pervasive Computing Applications, Systems, and Environments, p.9, May 20-26, 2007 [doi>10.1109/SEPCASE.2007.6]
• 21: Mary Shaw , David Garlan, Software architecture: perspectives on an emerging discipline, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 22: D. Soloveichik and E. Winfree. Complexity of compact proofreading for self-assembled patterns. Lecture Notes in Computer Science, 3892:305--324, 2006.
• 23: Erik Winfree , John J. Hopfield, Algorithmic self-assembly of dna, California Institute of Technology, Pasadena, CA, 1998
• 24: E. Winfree. Self-healing tile sets. Nanotechnology: Science and Computation, pages 55--78, 2006.
• 25: E. Winfree and R. Bekbolatov. Proofreading tile sets: Error correction for algorithmic self-assembly. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS02), volume 2943, pages 126--144, Madison, WI, USA, June 2003.