More Web Proxy on the site http://driver.im/

Article

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

Authors:

Nenad MedvidovicAuthors Info & Claims

EFTS '07: Proceedings of the 2007 workshop on Engineering fault tolerant systems

Pages 7 - es

https://doi.org/10.1145/1316550.1316557

Published: 04 September 2007 Publication History

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]

L. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266:1021--1024, 1994.

[2]

L. Adleman, J. Kari, L. Kari, and D. D. Reishus. On the decidability of self-assembly of infinite ribbons. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS02), pages 530--537, Ottawa, Ontario, Canada, November 2002.

Digital Library

[3]

L. Bass, P. Clements, and R. Kazman. Software architecture in practice. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1998.

Digital Library

[4]

Y. Brun. Arithmetic computation in the tile assembly model: Addition and multiplication. Theoretical Computer Science, 378:17--31, June 2006.

Digital Library

[5]

Y. Brun. A discreet, fault-tolerant, and scalable software architectural style for internet-sized networks. In Proceedings of the Doctoral Symposium at the 29th International Conference on Software Engineering (ICSE07), pages 83--84, Minneapolis, MN, USA, May 2007.

Digital Library

[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]

Y. Brun and N. Medvidovic. An architectural style for solving computationally intensive problems on large networks. In Proceedings of Software Engineering for Adaptive and Self-Managing Systems (SEAMS07), Minneapolis, MN, USA, May 2007.

Digital Library

[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.

Digital Library

[11]

P. Clements, R. Kazman, and M. Klein. Evaluating Software Architectures: Methods and Case Studies. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2002.

Digital Library

[12]

P. T. Devanbu and S. Stubblebine. Software Engineering for Security: A Roadmap, pages 225--239. ACM Press, 2000.

Digital Library

[13]

F. C. Gärtner. Fundamentals of fault-tolerant distributed computing in asynchronous environments. ACM Computing Surveys, 31(1):1--26, 1999.

Digital Library

[14]

S. Malek, M. Mikic-Rakic, and N. Medvidovic. A style-aware architectural middleware for resource-constrained, distributed systems. IEEE Transactions on Software Engineering, 31(3):256--272, 2005.

Digital Library

[15]

C. A. Mattmann, D. J. Crichton, N. Medvidovic, and S. Hughes. A software architecture-based framework for highly distributed and data intensive scientific applications. In Proceedings of the 28th international conference on Software engineering (ICSE06), pages 721--730, Shanghai, China, 2006. ACM Press.

Digital Library

[16]

M. Mikic-Rakic, N. R. Mehta, and N. Medvidovic. Architectural style requirements for self-healing systems. In Proceedings of 1st Workshop on Self-Healing Systems, Charleston, SC, USA, November 2002.

Digital Library

[17]

D. E. Perry and A. L. Wolf. Foundations for the study of software architecture. ACM SIGSOFT Software Engineering Notes, 17(4):40--52, 1992.

Digital Library

[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.

Digital Library

[19]

P. W. K. Rothemund and E. Winfree. The program-size complexity of self-assembled squares. In Proceedings of the ACM Symposium on Theory of Computing (STOC00), pages 459--468, Portland, OR, USA, May 2000.

Digital Library

[20]

C. Seo, S. Malek, G. Edwards, N. Medvidovic, B. Petrus, and S. Ravula. Exploring the role of software architecture in dynamic and fault tolerant pervasive systems. In Proceedings of the Workshop on Software Engineering of Pervasive Computing Applications, Systems and Environments (SEPCASE07), Minneapolis, MN, USA, May 2007.

Digital Library

[21]

M. Shaw and D. Garlan. Software architecture: perspectives on an emerging discipline. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1996.

Digital Library

[22]

D. Soloveichik and E. Winfree. Complexity of compact proofreading for self-assembled patterns. Lecture Notes in Computer Science, 3892:305--324, 2006.

Digital Library

[23]

E. Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Insitute of Technology, Pasadena, CA, USA, June 1998.

Digital Library

[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.

Cited By

Brun YLin TSomerville JMyers EEbner N(2023)Blindspots in Python and Java APIs Result in Vulnerable CodeACM Transactions on Software Engineering and Methodology10.1145/357185032:3(1-31)Online publication date: 26-Apr-2023
https://dl.acm.org/doi/10.1145/3571850
Brun YMeliou ALeavens GGarcia APăsăreanu C(2018)Software fairnessProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3264838(754-759)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3264838
Angell RJohnson BBrun YMeliou ALeavens GGarcia APăsăreanu C(2018)Themis: automatically testing software for discriminationProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3264590(871-875)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3264590
Show More Cited By

Recommendations

Software implemented hardware fault tolerance
Fault Tolerance in Multiprocessor Systems Without Dedicated Redundancy

An algorithm called RAFT (recursive algorithm for fault tolerance) for achieving fault tolerance in multiprocessor systems is described. Through the use of a combination of dynamic space- and time- redundancy techniques, RAFT achieves fault tolerance in ...
Software-Based Hardware Fault Tolerance for Many-Core Architectures
DFT '09: Proceedings of the 2009 24th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems

Software-based hardware fault tolerance describes a class of techniques which allows software to detect and correct errors introduced by unreliable hardware. With the advent of many-core architectures, the already existing reliability issues, like ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EFTS '07: Proceedings of the 2007 workshop on Engineering fault tolerant systems

September 2007

62 pages

ISBN:9781595937254

DOI:10.1145/1316550

Program Chairs:
Nicolas Guelfi
University of Luxembourg, Luxembourg
,
Henry Muccini
University of L'Aquila, Italy
,
Patrizio Pelliccione
University of L'Aquila, Italy
,
Alexander Romanovsky
University of Newcastle upon Tyne, UK

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 September 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ESEC/FSE07

Sponsor:

SIGSOFT

ESEC/FSE07: Joint 11th European Software Engineering Conference 2007

September 4, 2007

Dubrovnik, Croatia

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
330
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brun YLin TSomerville JMyers EEbner N(2023)Blindspots in Python and Java APIs Result in Vulnerable CodeACM Transactions on Software Engineering and Methodology10.1145/357185032:3(1-31)Online publication date: 26-Apr-2023
https://dl.acm.org/doi/10.1145/3571850
Brun YMeliou ALeavens GGarcia APăsăreanu C(2018)Software fairnessProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3264838(754-759)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3264838
Angell RJohnson BBrun YMeliou ALeavens GGarcia APăsăreanu C(2018)Themis: automatically testing software for discriminationProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3264590(871-875)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3264590
Motwani MSankaranarayanan SJust RBrun Y(2018)Do automated program repair techniques repair hard and important bugs?Empirical Software Engineering10.1007/s10664-017-9550-023:5(2901-2947)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10664-017-9550-0
Schmerl BAndersson JVogel TCohen MRubira CBrun YGorla AZambonelli FBaresi L(2018)Challenges in Composing and Decomposing Assurances for Self-Adaptive SystemsSoftware Engineering for Self-Adaptive Systems III. Assurances10.1007/978-3-319-74183-3_3(64-89)Online publication date: 18-Jan-2018
https://doi.org/10.1007/978-3-319-74183-3_3
Galhotra SBrun YMeliou ABodden ESchäfer WDeursen AZisman A(2017)Fairness testing: testing software for discriminationProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106277(498-510)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3106277
Brun YBang JEdwards GMedvidovic N(2015)Self-Adapting Reliability in Distributed Software SystemsIEEE Transactions on Software Engineering10.1109/TSE.2015.241213441:8(764-780)Online publication date: 1-Aug-2015
https://doi.org/10.1109/TSE.2015.2412134
Brun YMedvidovic N(2013)Entrusting Private Computation and Data to Untrusted NetworksIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2013.1310:4(225-238)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1109/TDSC.2013.13
Macías-Escrivá FHaber Rdel Toro RHernandez V(2013)Self-adaptive systems: A survey of current approaches, research challenges and applicationsExpert Systems with Applications10.1016/j.eswa.2013.07.03340:18(7267-7279)Online publication date: Dec-2013
https://doi.org/10.1016/j.eswa.2013.07.033
Garvin BCohen MDwyer M(2013)Failure Avoidance in Configurable Systems through Feature LocalityAssurances for Self-Adaptive Systems10.1007/978-3-642-36249-1_10(266-296)Online publication date: 2013
https://doi.org/10.1007/978-3-642-36249-1_10
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents