Article

An Architectural Style for Solving Computationally Intensive Problems on Large Networks

Authors:

Nenad MedvidovicAuthors Info & Claims

SEAMS '07: Proceedings of the 2007 International Workshop on Software Engineering for Adaptive and Self-Managing Systems

Page 2

https://doi.org/10.1109/SEAMS.2007.4

Published: 20 May 2007 Publication History

Abstract

Large networks, such as the Internet, pose an ideal medium for solving computationally intensive problems, such as NP-complete problems, yet no well-scaling architecture for computational Internet-sized systems exists. We propose a software architectural style for large networks, based on a formal mathematical study of crystal growth that will exhibit properties of (1) discreetness (nodes on the network cannot learn the algorithm or input of the computation), (2) fault-tolerance (malicious, faulty, and unstable nodes may not break the computation), and (3) scalability (communication among the nodes does not increase with network or problem size).

References

[1]

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

[2]

{2} L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, and H. Wasserman. Linear self-assemblies: Equilibria, entropy, and convergence rates. In Proceedings of the 6th International Conference on Difference Equations and Applications (ICDEA 2001), Augsburg, Germany, June 2001.

[3]

{3} L. Adleman, A. Goel, M.-D. Huang, and P. M. de Espanes. Running time and program size for selfassembled squares. In ACM Symposium on Theory of Computing (STOC02), pages 740-748, Montreal, Quebec, Canada, 2001.

Digital Library

[4]

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

Digital Library

[5]

{5} R. Barish, P. W. K. Rothemund, and E. Winfree. Two computational primitives for algorithmic self-assembly: Copying and counting. Nano Letters, 5(12):2586-2592, 2005.

[6]

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

Digital Library

[7]

{7} Y. Brun. Arithmetic computation in the tile assembly model: Addition and multiplication. Theoretical Computer Science, 10.1016/j.tcs.2006.10.025, 2006.

Digital Library

[8]

{8} 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.

[9]

{9} 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, Milan, Italy, June 2004.

Digital Library

[10]

{10} 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

[11]

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

[12]

{12} T. J. Fu and N. C. Seeman. DNA double-crossover molecules. Biochemistry, 32(13):3211-3220, 1993.

[13]

{13} M. Mikic-Rakic, N. R. Mehta, and N. Medvidovic. Architectural style requirements for self-healing systems. In Proceedings of First Workshop on Self-Healing Systems, Charleston, SC, Nov. 2002.

Digital Library

[14]

{14} 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

[15]

{15} P. W. K. Rothemund, N. Papadakis, and E. Winfree. Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology, 2(12):e424, 2004.

[16]

{16} P. W. K. Rothemund and E. Winfree. The program-size complexity of self-assembled squares. In ACM Symposium on Theory of Computing (STOC02), pages 459-468, Montreal, Quebec, Canada, 2001.

Digital Library

[17]

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

Digital Library

[18]

{18} M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Digital Library

[19]

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

Digital Library

[20]

{20} E. Winfree. Simulations of computing by self-assembly of DNA. Technical Report CS-TR:1998:22, California Insitute of Technology, Pasadena, CA, 1998.

[21]

{21} E. Winfree and R. Bekbolatov. Proofreading tile sets: Error correction for algorithmic self-assembly. In The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS02), volume 2943, pages 126-144, Madison, WI, 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

Index Terms

An Architectural Style for Solving Computationally Intensive Problems on Large Networks

Recommendations

An Architectural Style for Solving Computationally Intensive Problems on Large Networks
ICSEW '07: Proceedings of the 29th International Conference on Software Engineering Workshops

Large networks, such as the Internet, pose an ideal medium for solving computationally intensive problems, such as NP-complete problems, yet no well-scaling architecture for computational Internet-sized systems exists. We propose a software ...
A Discreet, Fault-Tolerant, and Scalable Software Architectural Style for Internet-Sized Networks
ICSE COMPANION '07: Companion to the proceedings of the 29th International Conference on Software Engineering

Large networks, such as the Internet, pose an ideal medium for solving computationally intensive problems, such as NP-complete problems, yet no well-scaling architecture for Internet-sized systems exists. I propose a software architectural style for ...
Composing style-based software architectures from architectural primitives

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SEAMS '07: Proceedings of the 2007 International Workshop on Software Engineering for Adaptive and Self-Managing Systems

May 2007

164 pages

ISBN:0769529739

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

IEEE Computer Society

United States

Publication History

Published: 20 May 2007

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 17 of 31 submissions, 55%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
238
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 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
Tziakouris GBahsoon RBabar M(2018)A Survey on Self-Adaptive Security for Large-scale Open EnvironmentsACM Computing Surveys10.1145/323414851:5(1-42)Online publication date: 9-Oct-2018
https://dl.acm.org/doi/10.1145/3234148
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
Haupt TMüller HBaresi L(2012)Towards mediation-based self-healing of data-driven business processesProceedings of the 7th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.5555/2666795.2666817(139-144)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.5555/2666795.2666817
Horikoshi HNakagawa HTahara YOhsuga AOssowski SLecca P(2012)Dynamic reconfiguration in self-adaptive systems considering non-functional propertiesProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2231956(1144-1150)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2231956
Ghezzi CPradella MSalvaneschi Gde Lemos RPezzè M(2010)Programming language support to context-aware adaptationProceedings of the 2010 ICSE Workshop on Software Engineering for Adaptive and Self-Managing Systems10.1145/1808984.1808991(59-68)Online publication date: 3-May-2010
https://dl.acm.org/doi/10.1145/1808984.1808991
Brun Yde Lemos RPezzè M(2010)Improving impact of self-adaptation and self-management research through evaluation methodologyProceedings of the 2010 ICSE Workshop on Software Engineering for Adaptive and Self-Managing Systems10.1145/1808984.1808985(1-9)Online publication date: 3-May-2010
https://dl.acm.org/doi/10.1145/1808984.1808985
Cheng BLemos RGiese HInverardi PMagee JAndersson JBecker BBencomo NBrun YCukic BMarzo Serugendo GDustdar SFinkelstein AGacek CGeihs KGrassi VKarsai GKienle HKramer JLitoiu MMalek SMirandola RMüller HPark SShaw MTichy MTivoli MWeyns DWhittle J(2009)Software Engineering for Self-Adaptive SystemsSoftware Engineering for Self-Adaptive Systems10.1007/978-3-642-02161-9_1(1-26)Online publication date: 10-Jun-2009
https://dl.acm.org/doi/10.1007/978-3-642-02161-9_1
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