Yuriy Brun's Publications

Author	Title	Year	Journal/Proceedings	DOI/URL
Yuriy Brun and Nenad Medvidovic	Preserving Privacy in Distributed Systems [Abstract] [Citation] [BibTeX]	2012	in submission to IEEE Transactions on Parallel and Distributed Systems
Abstract: We present sTile, a technique for distributing trust-needing computation onto insecure networks, while providing probabilistic guarantees that malicious agents that compromise parts of the network cannot learn private data. With sTile, we explore the fundamental cost of achieving privacy through data distribution and bound how much less efficient a privacy-preserving system is than a comparable non-private one. While the efficiency cost is non-trivial, we find that sTile-based systems execute orders of magnitude faster than homomorphic encryption systems, the alternative promising approach to preserving privacy. This paper focuses specifically on NP-complete problems and demonstrates how sTile-based systems can solve important real-world problems, such as protein folding, image recognition, and resource allocation. We present the algorithms involved in sTile and formally prove that sTile-based systems preserve privacy. We develop a reference sTile-based implementation and empirically evaluate it on several physical and simulated networks of varying sizes, including the globally distributed PlanetLab testbed.
Citation: Y. Brun and N. Medvidovic (2012), "Preserving Privacy in Distributed Systems", in submission to IEEE Transactions on Parallel and Distributed Systems.
BibTeX: @article{Brun11tpds, author = {Yuriy Brun and Nenad Medvidovic}, title = {Preserving Privacy in Distributed Systems}, journal = {(in submission) IEEE Transactions on Parallel and Distributed Systems}, year = {2012}, pages = {}, doi = {} }
George Edwards, Yuriy Brun, and Nenad Medvidovic	Automated Analysis and Code Generation for Domain-Specific Models [Abstract] [Citation] [BibTeX]	2012	in submission to the 34th International Conference on Software Engineering (ICSE12)
Abstract: Domain-specific languages (DSLs) concisely express the essential features of system designs. However, using a DSL for automated analysis and code generation requires developing specialized tools. We describe how to create model analysis and code generation tools that can be applied to a large family of DSLs, and show how we created the LIGHT platform, a suite of such tools for the family of software architecture-based DSLs. These tools can be easily reused off-the-shelf with new DSLs, freeing engineers from having to custom-develop them. The key innovation underlying our strategy is to enhance DSL metamodels with additional semantics, and then automatically synthesize configurations and plug-ins for flexible analysis and code generation frameworks. Our evaluation shows that, for a DSL of typical size, using our strategy relieves software engineers of developing approximately 17,500 lines of code, which amounts to several person-months of programming work.
Citation: G. Edwards, Y. Brun, and N. Medvidovic (2012), "Automated Analysis and Code Generation for Domain-Specific Models", in submission to the 34th International Conference on Software Engineering (ICSE12). Zurich, Switzerland.
BibTeX: @inproceedings{Edwards12icse, author = {George Edwards and Yuriy Brun and Nenad Medvidovic}, title = {Automated Analysis and Code Generation for Domain-Specific Models}, booktitle = {(in submission) the 34th International Conference on Software Engineering ({ICSE}12)}, year = {2012}, pages = {}, doi = {} }
Yuriy Brun, Ron Desmarais, Kurt Geihs, Marin Litoiu, Antonia Lopes, Mary Shaw, and Mike Smit	A Design Space for Adaptive Systems [Abstract] [Citation] [BibTeX]	2012	in submission to Software Engineering for Self-Adaptive Systems II
Abstract: Adaptive systems research is expanding as systems professionals recognize the importance of automated assistance in managing the growing complexity, scale, and scope of software systems. In the absence of best practices for designing such systems, the current approach to designing such systems is ad hoc, varied, and fractured, often resulting in systems with parts of multiple, sometimes poorly compatible designs. In addition to the challenges inherent to ill-designed software, this makes evaluating, understanding, comparing, maintaining, and even using such systems more difficult. This paper discusses the importance of systematic design and identifies the dimensions of the adaptive system design space. It identifies key design decisions, questions, and possible answers relevant to the design space, and organizes these into five clusters: observation, representation, control, identification, and adaptation mechanisms. Additionally, this characterization can serve as a standard lexicon, that, in turn, can aid in describing the behavior of existing adaptive systems and evaluating adaptive systems. The paper also outlines the future challenges for improving the design of adaptive systems.
Citation: Y. Brun, R. Desmarais, K. Geihs, M. Litoiu, A. Lopes, M. Shaw, and M. Smit (2012), "A Design Space for Adaptive Systems", in submission to Software Engineering for Self-Adaptive Systems II.
BibTeX: @inproceedings{Brun12SEfSAS, author = {Yuriy Brun and Ron Desmarais and Kurt Geihs and Marin Litoiu and Antonia Lopes and Mary Shaw and Mike Smit}, title = {A Design Space for Adaptive Systems}, booktitle = {Software Engineering for Self-Adaptive Systems II (in submission)}, year = {2012}, pages = {}, doi = {} }
Rogério de Lemos, Holger Giese, Hausi A. Müller, Mary Shaw, Jesper Andersson, Luciano Baresi, Basil Becker, Nelly Bencomo, Yuriy Brun, Bojan Cukic, Ron Desmarais, Schahram Dustdar, Gregor Engels, Kurt Geihs, Karl M. Goeschka, Alessandra Gorla, Vincenzo Grassi, Paola Inverardi, Gabor Karsai, Jeff Kramer, Marin Litoiu, Antonia Lopes, Jeff Magee, Sam Malek, Serge Mankovskii, Raffaela Mirandola, John Mylopoulos, Oscar Nierstrasz, Mauro Pezzè, Christian Prehofer, Wilhelm Schäfer, Rick Schlichting, Bradley Schmerl, Dennis B. Smith, João P. Sousa, Gabriel Tamura, Ladan Tahvildari, Norha M. Villegas, Thomas Vogel, Danny Weyns, Kenny Wong, and Jochen Wuttke	Software Engineering for Self-Adaptive Systems: A Second Research Roadmap [Abstract] [Citation] [BibTeX]	2012	in submission to Software Engineering for Self-Adaptive Systems II
Abstract: The goal of this roadmap paper is to summarize the state-of-the-art and identify research challenges when developing, deploying and managing self-adaptive software systems. Instead of dealing with a wide range of topics associated with the field, we focus on four essential topics of self-adaptation: design space for adaptive solutions, processes, from centralized to decentralized control, and practical run-time verification and validation. For each topic, we present an overview, suggest future directions, and focus on selected challenges. This paper complements and extends a previous roadmap on software engineering for self-adaptive systems published in 2009 covering a different set of topics, and reflecting in part on the previous paper. This roadmap is one of the many results of the Dagstuhl Seminar 10431 on Software Engineering for Self-Adaptive Systems, which took place in October 2010.
Citation: R. de Lemos, H. Giese, H. A. Müller, M. Shaw, J. Andersson, L. Baresi, B. Becker, N. Bencomo, Y. Brun, B. Cukic, R. Desmarais, S. Dustdar, G. Engels, K. Geihs, K. M. Goeschka, A. Gorla, V. Grassi, P. Inverardi, G. Karsai, J. Kramer, M. Litoiu, A. Lopes, J. Magee, S. Malek, S. Mankovskii, R. Mirandola, J. Mylopoulos, O. Nierstrasz, M. Pezzè, C. Prehofer, W. Schäfer, R. Schlichting, B. Schmerl, D. B. Smith, J. P. Sousa, G. Tamura, L. Tahvildari, N. M. Villegas, T. Vogel, D. Weyns, K. Wong, and J. Wuttke (2012), "Software Engineering for Self-Adaptive Systems: A Second Research Roadmap", in submission to Software Engineering for Self-Adaptive Systems II.
BibTeX: @inproceedings{Lemos12, author = {Rog{\'{e}}rio de Lemos and Holger Giese and Hausi A. M{\"{u}}ller and Mary Shaw and Jesper Andersson and Luciano Baresi and Basil Becker and Nelly Bencomo and Yuriy Brun and Bojan Cukic and Ron Desmarais and Schahram Dustdar and Gregor Engels and Kurt Geihs and Karl M. Goeschka and Alessandra Gorla and Vincenzo Grassi and Paola Inverardi and Gabor Karsai and Jeff Kramer and Marin Litoiu and Antonia Lopes and Jeff Magee and Sam Malek and Serge Mankovskii and Raffaela Mirandola and John Mylopoulos and Oscar Nierstrasz and Mauro Pezz{\`{e}} and Christian Prehofer and Wilhelm Sch{\"{a}}fer and Rick Schlichting and Bradley Schmerl and Dennis B. Smith and Jo{\~{a}}o P. Sousa and Gabriel Tamura and Ladan Tahvildari and Norha M. Villegas and Thomas Vogel and Danny Weyns and Kenny Wong and Jochen Wuttke}, title = {Software Engineering for Self-Adaptive Systems: {A} Second Research Roadmap}, booktitle = {Software Engineering for Self-Adaptive Systems II (in submission)}, year = {2012}, pages = {}, doi = {} }
Yuriy Brun	Efficient 3-SAT Algorithms in the Tile Assembly Model [Abstract] [Citation] [BibTeX]	2012	in press in Natural Computing	DOI
Abstract: Self-assembly is a powerful process found in nature that guides simple objects assembling, on their own, into complex structures. Self-assembly is of interest to computer scientists because self-assembling systems can compute functions, assemble shapes, and guide distributed robotics systems. The tile assembly model is a formal mathematical model of self-assembly that allows the study of time and space complexities of self-assembling systems that lie at the heart of several molecular computer implementations and distributed computational software systems. These implementations and systems require efficient tile systems with small tilesets and fast execution times. The state of the art, however, requires vastly complex tile systems with large tilesets to implement fast algorithms. In this paper, I present a tile system that decides 3-SAT by creating 0*(1.8393^n) nondeterministic assemblies in parallel, improving on the previous best known solution that requires O(2^n) such assemblies. This solution directly improves the feasibility of building molecular 3-SAT solvers and efficiency of distributed software. I formally prove the correctness of the system, the number of required parallel assemblies, that the size of the system's tileset is 147 = O(1), and that the assembly time is nondeterministic linear in the size of the input.
Citation: Y. Brun (2012), "Efficient 3-SAT Algorithms in the Tile Assembly Model", in press in Natural Computing.
BibTeX: @article{Brun12natcomp, author = {Yuriy Brun}, title = {Efficient 3-{SAT} Algorithms in the Tile Assembly Model}, journal = {(in press) Natural Computing}, year = {2012}, pages = {}, doi = {10.1007/s11047-011-9299-0} }
Yuriy Brun, Kivanc Muslu, Reid Holmes, Michael D. Ernst, David Notkin	Predicting Development Trajectories to Prevent Collaboration Conflicts [Abstract] [Citation] [BibTeX]	2012	Proceedings of the Future of Collaborative Software Development (FCSD12)
Abstract: The benefits of collaborative development are reduced by the cost of resolving conflicts. We posit that reducing the time between when developers introduce and learn about conflicts reduces this cost. We outline the state-of-the-practice of managing and resolving conflicts and describe how it can be improved by available state-of-the-art tools. Then, we describe our vision for future tools that can predict likely conflicts before they are even created, warning developers and allowing them to avoid potentially costly situations.
Citation: Y. Brun, K. Muslu, R. Holmes, and M.D. Ernst, and D. Notkin (2012), "Predicting Development Trajectories to Prevent Collaboration Conflicts", in Proceedings of the Future of Collaborative Software Development (FCSD12).
BibTeX: @inproceedings{Brun12fcsd, author = {Yuriy Brun and K{\i}van{\c{c}} Mu{\c{s}}lu and Reid Holmes and Michael D. Ernst and David Notkin}, title = {Predicting Development Trajectories to Prevent Collaboration Conflicts}, boktitle = {the Future of Collaborative Software Development (FCSD12), address = {Seattle, WA, USA}, year = {2012}, pages = {}, doi = {} }
George Edwards, Yuriy Brun, and Nenad Medvidovic	Isomorphism in Model Tools and Editors [Abstract] [Citation] [BibTeX]	2011	Proceedings of the 26th IEEE ACM International Conference On Automated Software Engineering (ASE11).	DOI
Abstract: Domain-specific languages (DSLs) are modeling languages that are customized for a specific context or project. DSLs allow for fast and precise modeling because the language features and constructs can be precisely tailored based on the needs of the modeling effort. There exist highly customizable model-editing tools that can be easily configured to support DSLs defined by end-users (e.g., system architects, engineers, and analysts). However, to leverage models created using these tools for automated analysis, simulation, and code generation, end-users must build custom analysis tools and code generators. In contrast to model editors, the implementation and maintenance of these analysis and code generation tools can be tedious and hampers the utility of DSLs. In this paper, we posit that analysis and code generation tools for DSLs are, in fact, isomorphic to model editing tools. The implication of this insight is that model editors, analysis tools, and code generators can be treated as analogs conceptually and architecturally, and highly customizable analysis and code generation tools for DSLs can be built using the same approach that has already proven successful for the construction of DSL model editors.
Citation: G. Edwards, Y. Brun, and N. Medvidovic (2011), "Isomorphism in Model Tools and Editors", In Proceedings of the 26th IEEE ACM International Conference On Automated Software Engineering (ASE11). Lawrence, KS, USA, November, 2011. pp. 458-461
BibTeX: @inproceedings{Edwards11ase, author = {George Edwards and Yuriy Brun and Nenad Medvidovic}, title = {Isomorphism in Model Tools and Editors}, booktitle = {Proceedings of the 26th IEEE ACM International Conference On Automated Software Engineering ({ASE}11)}, year = {2011}, pages = {458--461}, doi = {10.1109/ASE.2011.6100099} }
Ivan Beschastnikh, Yuriy Brun, Michael D. Ernst, Arvind Krishnamurthy, and Thomas E. Anderson	Mining Temporal Invariants from Partially Ordered Logs [Abstract] [Citation] [BibTeX]	2011	Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques (SLAML11).	DOI
Abstract: A common assumption made in log analysis research is that the underlying log is totally ordered. For concurrent systems, this assumption constrains the generated log to either exclude concurrency altogether, or to capture a particular interleaving of concurrent events. This paper argues that capturing concurrency as a partial order is useful and often indispensable for answering important questions about concurrent systems. To this end, we motivate a family of event ordering invariants over partially ordered event traces, give three algorithms for mining these invariants from logs, and evaluate their scalability on simulated distributed system logs.
Citation: I. Beschastnikh, Y. Brun, M. D. Ernst, A. Krishnamurthy, and T. E. Anderson (2011), "Mining Temporal Invariants from Partially Ordered Logs", In Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques (SLAML11). Cascais, Portugal, October, 2011.
BibTeX: @inproceedings{Beschastnikh11slaml, author = {Ivan Beschastnikh and Yuriy Brun and Michael D. Ernst and Arvind Krishnamurthy and Thomas E. Anderson}, title = {Mining Temporal Invariants from Partially Ordered Logs}, booktitle = {Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques ({SLAML}11)}, year = {2011}, pages = {}, doi = {10.1145/2038633.2038636} }
Yuriy Brun, Reid Holmes, Michael D. Ernst, and David Notkin	Proactive Detection of Collaboration Conflicts [Abstract] [Citation] [BibTeX]	2011	Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE11). (presentation video) (presentation slides)	DOI
Abstract: Collaborative development can be hampered when conflicts arise because developers have inconsistent copies of a shared project. We present an approach to help developers identify and resolve conflicts early, before those conflicts become severe and before relevant changes fade away in the developers’ memories. This paper presents three results. First, a study of open-source systems establishes that conflicts are frequent, persistent, and appear not only as overlapping textual edits but also as subsequent build and test failures. The study spans nine open-source systems totaling 3.4 million lines of code; our conflict data is derived from 550,000 development versions of the systems. Second, using previously-unexploited information, we precisely diagnose important classes of conflicts using the novel technique of speculative analysis over version control operations. Third, we describe the design of Crystal, a publicly-available tool that uses speculative analysis to make concrete advice unobtrusively available to developers, helping them identify, manage, and prevent conflicts.
Citation: Y. Brun, R. Holmes, M. D. Ernst, and D. Notkin (2011), "Proactive Detection of Collaboration Conflicts", In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE11). Szeged, Hungary, September, 2011. pp 168-178
BibTeX: @inproceedings{Brun11fse, author = {Yuriy Brun and Reid Holmes and Michael D. Ernst and David Notkin}, title = {Proactive Detection of Collaboration Conflicts}, booktitle = {Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering ({ESEC/FSE}11)}, year = {2011}, pages = {168--178}, doi = {10.1145/2025113.2025139} }
Ivan Beschastnikh, Yuriy Brun, Sigurd Schneider, Michael Sloan, and Michael D. Ernst	Leveraging Existing Instrumentation to Automatically Infer Invariant-Constrained Models [Abstract] [Citation] [BibTeX]	2011	Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE11).	DOI
Abstract: Computer systems are often difficult to debug and understand. A common way of gaining insight into system behavior is to inspect execution logs and documentation. Unfortunately, manual inspection of logs is an arduous process and documentation is often incomplete and out of sync with the implementation. This paper presents Synoptic, a tool that helps developers by inferring a concise and accurate system model. Unlike most related work, Synoptic does not require developer-written scenarios, specifications, negative execution examples, or other complex user input. Synoptic processes the logs most systems already produce and requires developers only to specify a set of regular expressions for parsing the logs. Synoptic has two unique features. First, the model it produces satisfies three kinds of temporal invariants mined from the logs, improving accuracy over related approaches. Second, Synoptic uses refinement and coarsening to explore the space of models. This improves model efficiency and precision, compared to using just one approach. In this paper, we formally prove that Synoptic always produces a model that satisfies exactly the temporal invariants mined from the log, and we argue that it does so efficiently. We empirically evaluate Synoptic through two user experience studies, one with a developer of a large, real-world system and another with 45 students in a distributed systems course. Developers used Synoptic-generated models to verify known bugs, diagnose new bugs, and increase their confidence in the correctness of their systems. None of the developers in our evaluation had a background in formal methods but were able to easily use Synoptic and detect implementation bugs in as little as a few minutes.
Citation: I. Beschastnikh, Y. Brun, S. Schneider, M. Sloan, and M. D. Ernst (2011), "Leveraging Existing Instrumentation to Automatically Infer Invariant-Constrained Models", In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE11). Szeged, Hungary, September, 2011. pp 267-277
BibTeX: @inproceedings{Beschastnikh11fse, author = {Ivan Beschastnikh and Yuriy Brun and Sigurd Schneider and Michael Sloan and Michael D. Ernst}, title = {Leveraging Existing Instrumentation to Automatically Infer Invariant-Constrained Models}, booktitle = {Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering ({ESEC/FSE}11)}, year = {2011}, pages = {267--277}, doi = {10.1145/2025113.2025151} }
Yuriy Brun, Reid Holmes, Michael D. Ernst, and David Notkin	Crystal: Precise and Unobtrusive Conflict Warnings [Abstract] [Citation] [BibTeX]	2011	Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track (ESEC/FSE11).	DOI
Abstract: During collaborative development, individual developers can create conflicts in their copies of the code. Such conflicting edits are frequent in practice, and resolving them can be costly. We present Crystal, a tool that proactively examines developers’ code and precisely identifies and reports on textual, compilation, and behavioral conflicts. When conflicts are present, Crystal enables developers to resolve them more quickly, and therefore at a lesser cost. When conflicts are absent, Crystal increases the developers’ confidence that it is safe to merge their code. Crystal uses an unobtrusive interface to deliver pertinent information about conflicts. It informs developers about actions that would address the conflicts and about people with whom they should communicate.
Citation: Y. Brun, R. Holmes, M. D. Ernst, and D. Notkin (2011), "Crystal: Precise and Unobtrusive Conflict Warnings", In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track (ESEC/FSE11). Szeged, Hungary, September, 2011. pp. 444-447
BibTeX: @inproceedings{Brun11fse-tool-demo, author = {Yuriy Brun and Reid Holmes and Michael D. Ernst and David Notkin}, title = {Proactive Detection of Collaboration Conflicts}, booktitle = {Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track ({ESEC/FSE}11)}, year = {2011}, pages = {444--447}, doi = {10.1145/2025113.2025187} }
Ivan Beschastnikh, Jenny Abrahamson, Yuriy Brun, and Michael D. Ernst	Synoptic: Studying Logged Behavior with Inferred Models [Abstract] [Citation] [BibTeX]	2011	Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track (ESEC/FSE11).	DOI
Abstract: Logging is a powerful method for capturing program activity and state during an execution. However, log inspection remains a tedious activity, with developers often piecing together what went on from multiple log lines and across many files. This paper describes Synoptic, a tool that takes logs as input and outputs a finite state machine that models the process generating the logs. The paper overviews the model inference algorithms. Then, it describes the Synoptic tool, which is designed to support a rich log exploration workflow.
Citation: I. Beschastnikh and J. Abrahamson and Y. Brun and M. D. Ernst (2011), "Synoptic: Studying Logged Behavior with Inferred Models", In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track (ESEC/FSE11). Szeged, Hungary, September, 2011. pp. 448-451
BibTeX: @inproceedings{Beschastnikh11fse-tool-demo, author = {Ivan Beschastnikh and Jenny Abrahamson and Yuriy Brun and Michael D. Ernst}, title = {Synoptic: {S}tudying Logged Behavior with Inferred Models}, booktitle = {Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track ({ESEC/FSE}11)}, year = {2011}, pages = {448--451}, doi = {10.1145/2025113.2025188} }
Chloé Kiddon and Yuriy Brun	That's What She Said: Double Entendre Identification [Abstract] [Citation] [BibTeX]	2011	Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT 2011)	URL
Abstract: Humor identification is a hard natural language understanding problem. We identify a subproblem — the "that's what she said" problem — with two distinguishing characteristics: (1) use of nouns that are euphemisms for sexually explicit nouns and (2) structure common in the erotic domain. We address this problem in a classification approach that includes features that model those two characteristics. Experiments on web data demonstrate that our approach improves precision by 12% over baseline techniques that use only word-based features.
Citation: Chloé Kiddon and Yuriy Brun (2011), "That's What She Said: Double Entendre Identification", In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT11). Portland, OR, USA, June, 2011.
BibTeX: @inproceedings{Kiddon11, author = {Chlo{\'{e}} Kiddon and Yuriy Brun}, title = {That's What She Said: Double Entendre Identification}, booktitle = {Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies ({ACL-HLT}11)}, year = {2011}, pages = {}, doi = {} }
Yuriy Brun, George Edwards, Jae young Bang, and Nenad Medvidovic	Smart Redundancy for Distributed Computation [Abstract] [Citation] [BibTeX]	2011	Proceedings of the 31st International Conference on Distributed Computing Systems (ICDCS11). A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2009-510	DOI
Abstract: Many distributed software systems allow participation by large numbers of untrusted, potentially faulty components on an open network. As faults are inevitable in this setting, these systems utilize redundancy and replication to achieve fault tolerance. In this paper, we present a novel smart redundancy technique called iterative redundancy, which ensures efficient replication of computation and data given finite processing and storage resources, even when facing Byzantine faults. Iterative redundancy is more efficient and more adaptive than comparable state-of-the-art techniques that operate in environments with unknown system resource reliability. We show how systems that solve computational problems using a network of independent nodes can benefit from iterative redundancy. We present a formal analytical analysis and an empirical analysis, demonstrate iterative redundancy on a real-world volunteer-computing system, and compare it to existing methods.
Citation: Y. Brun, G. Edwards, J. Bang, and N. Medvidovic (2011), "Smart Redundancy for Distributed Computation", In Proceedings of the 31st International Conference on Distributed Computing Systems (ICDCS11). Minneapolis, MN, USA, June, 2011. pp. 665--676.
BibTeX: @inproceedings{Brun11icdcs, author = {Yuriy Brun and George Edwards and Jae young Bang and Nenad Medvidovic}, title = {Smart Redundancy for Distributed Computation}, booktitle = {Proceedings of the 31st International Conference on Distributed Computing Systems ({ICDCS}11)}, year = {2011}, pages = {665-676}, doi = {10.1109/ICDCS.2011.25} }
Nenad Medvidovic, Hossein Tajalli, Joshua Garcia, Yuriy Brun, Ivo Krka, and George Edwards	Engineering heterogeneous robotics systems: A software architecture-based approach [Abstract] [Citation] [BibTeX]	2011	IEEE Computer	DOI
Abstract: This paper describes an approach to engineering distributed, adaptive, software-intensive systems deployed on mobile robots accompanied with sensor-based, handheld, and desktop platforms. The foundation of this approach is software architecture — a set of principal design decisions about a software-intensive system — that enables (1) guided exploration of design alternatives, (2) rigorous system modeling and analysis, (3) implementation and deployment in heterogeneous settings, and (4) powerful new system behaviors — dynamic and autonomous adaptation. Our experience in the context of two different scenarios indicates that this work can help to make the development of robotic systems more accessible to non-experts, improve the exchange of design solutions among robotics engineers, deal effectively with heterogeneity inherent in mobile robotics systems, and develop adaptive systems that can be deployed into complex and changing environments.
Citation: N. Medvidovic, H. Tajalli, J. Garcia, Y. Brun, I. Krka, and G. Edwards. (2011), "Engineering heterogeneous robotics systems: A software architecture-based approach ", IEEE Computer. Vol. 44(5), pp. 61-71.
BibTeX: @article{Medvidovic11, author = {Nenad Medvidovic and Hossein Tajalli and Joshua Garcia and Yuriy Brun and Ivo Krka and George Edwards}, title = {Engineering heterogeneous robotics systems: A software architecture-based approach}, journal = {IEEE Computer}, volume = {44}, number = {5}, month = {May}, year = {2011}, doi = {10.1109/MC.2010.368}, }
Yuriy Brun	Improving Efficiency of 3-SAT-Solving Tile Systems [Abstract] [Citation] [BibTeX]	2011	Lecture Notes on Computer Science: DNA Computing. A previous version appeared in the proceedings of the 16th International Conference on DNA Computing and Molecular Programming, (DNA11)	DOI
Abstract: The tile assembly model has allowed the study of the nature's process of self-assembly and the development of self-assembling systems for solving complex computational problems. Research into this model has led to progress in two distinct classes of computational systems: Internet-sized distributed computation, such as software architectures for computational grids, and molecular computation, such as DNA computing. The design of large complex tile systems that emulate Turing machines has shown that the tile assembly model is Turing universal, while the design of small tile systems that implement simple algorithms has shown that tile assembly can be used to build private, fault-tolerant, and scalable distributed software systems and robust molecular machines. However, in order for these types of systems to compete with traditional computing devices, we must demonstrate that fairly simple tile systems can implement complex and intricate algorithms for important problems. The state of the art, however, requires vastly complex tile systems with large tile sets to implement such algorithms. In this paper, I present a tile system that decides 3-SAT by creating O(1.8393ⁿ) nondeterministic assemblies in parallel, while the previous best known solution requires O(2ⁿ) such assemblies. In some sense, this tile system follows the most complex algorithm implemented using tiles to date. I analyze that the number of required parallel assemblies is O(1.8393ⁿ), that the size of the system’s tileset is 147 = O(1), and that the assembly time is nondeterministic linear in the size of the input. This work directly improves the time and space complexities of tile-inspired computational-grid architectures and bridges theory and today’s experimental limitations of DNA computing.
Citation: Y. Brun (2011), "Improving Efficiency of 3-SAT-Solving Tile Systems", Lecture Notes on Computer Science: DNA Computing. Vol. 6518/2011, pp. 1-12.
BibTeX: @inproceedings{Brun11dna-lncs, author = {Yuriy Brun}, title = {Improving Efficiency of 3-{SAT}-Solving Tile Systems}, booktitle = {Lecture Notes on Computer Science: DNA Computing}, year = {2011}, pages = {1--12}, volume = {6518/2011}, doi = {10.1007/978-3-642-18305-8_1}, }
Yuriy Brun, Reid Holmes, Michael D. Ernst, and David Notkin	Speculative Analysis: Exploring Future States of Software [Abstract] [Citation] [BibTeX]	2010	Proceedings of the 2010 Foundations of Software Engineering Working Conference on the Future of Software Engineering Research (FoSER10)	DOI
Abstract: Most software tools and environments help developers analyze the present and past development states of their software systems. Few approaches have investigated the potential consequences of future actions the developers may perform. The commoditization of hardware, multi-core architectures, and cloud computing provide new potential for delivering apparently-instantaneous feedback to developers, informing them of the effects of changes that they may be considering to the software. For example, modern IDEs often provide quick fix suggestions for resolving compilation errors. Developers must scan this list and select the option they think will resolve the problem. Instead, we propose that the IDE should speculatively perform each of the suggestions in the background and provide information that helps developers select the best option for the given context. We believe the feedback enabled by speculative operations can improve developer productivity and software quality.
Citation: Y. Brun, R. Holmes, M. D. Ernst, and D. Notkin (2010), "Speculative Analysis: Exploring Future States of Software", In Proceedings of the 2010 Foundations of Software Engineering Working Conference on the Future of Software Engineering Research (FoSER10), pp. 59-63. Santa Fe, NM, USA, November, 2010.
BibTeX: @inproceedings{Brun10foser, author = {Yuriy Brun and Reid Holmes and Michael D. Ernst and David Notkin}, title = {Speculative Analysis: Exploring Future States of Software}, booktitle = {Proceedings of the 2010 Foundations of Software Engineering Working Conference on the Future of Software Engineering Research ({FoSER}10)}, year = {2010}, page = {59--63}, }
Sigurd Schneider, Ivan Beschastnikh, Slava Chernyak, Michael D. Ernst, and Yuriy Brun	Synoptic: Summarizing System Logs with Refinement [Abstract] [Citation] [BibTeX]	2010	Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques (SLAML10)	DOI
Abstract: Distributed systems are often difficult to debug and understand. A typical way of gaining insight into system behavior is by inspecting its execution logs. Manual inspection of logs is arduous, and few tools can analyze an arbitrary system log out of the box. To support this task we developed \emph{Synoptic}. Synoptic outputs a concise graph representation of logged events that captures important temporal event invariants mined from the log. We applied Synoptic to synthetic and real distributed system logs, and found that it augmented a distributed system designer's understanding of system behavior with reasonable overhead for an offline analysis tool. Synoptic makes no assumptions about the system, and requires no system modifications. In contrast to prior approaches, Synoptic uses a combination of refinement and coarsening instead of just coarsening to explore the space of representations. Additionally, it infers temporal event invariants to capture distributed system semantics that are often present in system logs. These invariants drive the exploration process and are preserved in the final representation.
Citation: S. Schneider, I. Beschastnikh, S. Chernyak, M. D. Ernst, and Y. Brun (2010), "Synoptic: Summarizing System Logs with Refinement", In Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques (SLAML10). Vancouver, Canada, October, 2010.
BibTeX: @inproceedings{Schneider10, author = {Sigurd Schneider and Ivan Beschastnikh and Slava Chernyak and Michael D. Ernst and Yuriy Brun}, title = {Synoptic: Summarizing System Logs with Refinement}, booktitle = {Proceedings of the Workshop on Managing Systems via Log Analysis and Machine Learning Techniques ({SLAML}10)}, year = {2010}, doi = {10.1145/1928991.1928995}, }
Ivo Krka, Yuriy Brun, Daniel Popescu, Joshua Garcia, and Nenad Medvidovic	Using Dynamic Execution Traces and Program Invariants to Enhance Behavioral Model Inference [Abstract] [Citation] [BibTeX]	2010	Proceedings of the New Ideas and Emerging Results Track at the 32nd International Conference on Software Engineering (ICSE10)	DOI
Abstract: Software behavioral models have proven useful for design, validation, verification, and maintenance. However, existing approaches for deriving such models sometimes overgeneralize what behavior is legal. We outline a novel approach that utilizes inferred program invariants and method invocation sequences to obtain an object-level model to describe legal execution sequences. The key insight is using program invariants to identify similar states in the sequences. We exemplify how our approach improves upon certain aspects of the state-of-the-art FSA-inference techniques.
Citation: I. Krka, Y. Brun, D. Popescu, J. Garcia, and N. Medvidovic (2010), "Using Dynamic Execution Traces and Program Invariants to Enhance Behavioral Model Inference", In Proceedings of the New Ideas and Emerging Results Track at the 32ns International Conference on Software Engineering (ICSE10), pp. 179-182. Cape Town, South Africa, May, 2010.
BibTeX: @inproceedings{Krka10icse-nier, author = {Ivo Krka and Yuriy Brun and Daniel Popescu and Joshua Garcia and Nenad Medvidovic}, title = {Using Dynamic Execution Traces and Program Invariants to Enhance Behavioral Model Inference}, booktitle = {Proceedings of the New Ideas and Emerging Results Track at the 32nd International Conference on Software Engineering ({ICSE}10)}, year = {2010}, pages = {179--182}, doi = {10.1145/1810295.1810324}, }
Yuriy Brun	Improving Impact of Self-Adaptation and Self-Management Research through Evaluation Methodology [Abstract] [Citation] [BibTeX]	2010	Proceedings of Software Engineering for Adaptive and Self-Managing Systems (SEAMS10)	DOI
Abstract: Today, self-adaptation and self-management approaches to software engineering are viewed as specialized techniques and reach a somewhat limited community. In this paper, I overview the current state and expectation of self-adaptation and self-management impact in industry and in premier publication venues and identify what we, as a community, may do to improve such impact. In particular, I find that common evaluation methodologies make it relatively simple for self-adaptation and self-management research to be compared to other such research, but not to more-traditional software engineering research. I argue that extending the evaluation to include comparisons to traditional software engineering techniques may improve a reader's ability to judge the contribution of the research and increase its impact. Finally, I propose a set of evaluation guidelines that may ease the promotion of self-adaptation and self-management as mainstream software engineering techniques.
Citation: Y. Brun (2010), "Improving Impact of Self-Adaptation and Self-Management Research through Evaluation Methodology", In Proceedings of Software Engineering for Adaptive and Self-Managing Systems (SEAMS10), pp. 1-9. Cape Town, South Africa, May, 2010.
BibTeX: @inproceedings{Brun10seams, author = {Yuriy Brun}, title = {Improving Impact of Self-Adaptation and Self-Management Research through Evaluation Methodology}, booktitle = {Proceedings of Software Engineering for Adaptive and Self-Managing Systems ({SEAMS}10)}, year = {2010}, pages = {1--9}, doi = {10.1145/1808984.1808985}, }
Sam Malek, George Edwards, Yuriy Brun, Hossein Tajalli, Joshua Garcia, Ivo Krka, Nenad Medvidovic, Marija Mikic-Rakic, and Gaurav Sukhatme	An Architecture-Driven Software Mobility Framework [Abstract] [Citation] [BibTeX]	2010	Journal of Systems and Software	DOI
Abstract: Software architecture has been shown to provide an appropriate level of granularity for assessing a software system's quality attributes (e.g., performance and dependability). Similarly, previous research has adopted an architecture-centric approach to reasoning about and managing the run-time adaptation of software systems. For mobile and pervasive software systems, which are known to be innately dynamic and unpredictable, the ability to assess a system's quality attributes and manage its dynamic run-time behavior is especially important. In the past, researchers have argued that a software architecture-based approach can be instrumental in facilitating mobile computing. In this paper, we present an integrated architecture-driven framework for modeling, analysis, implementation, deployment, and run-time migration of software systems executing on distributed, mobile, heterogeneous computing platforms. In particular, we describe the framework's support for dealing with the challenges posed by both logical and physical mobility. We also provide an overview of our experience with applying the framework to a family of distributed mobile robotics systems. This experience has verified our envisioned benefits of the approach, and has helped us to identify several avenues of future work.
Citation: S. Malek, G. Edwards, Y. Brun, H. Tajalli, J. Garcia, I. Krka, N. Medvidovic, M. Mikic-Rakic, and G. Sukhatme (2010), "An Architecture-Driven Software Mobility Framework", Journal of Systems and Software. Vol. 83(6), pp. 972-989.
BibTeX: @article{Malek10, author = {Sam Malek and George Edwards and Yuriy Brun and Hossein Tajalli and Joshua Garcia and Ivo Krka and Nenad Medvidovic and Marija Mikic-Rakic and Gaurav Sukhatme}, title = {An Architecture-Driven Software Mobility Framework}, journal = {Journal of Systems and Software}, year = {2010}, volume = {83}, number = {6}, pages = {972--989}, doi = {10.1016/j.jss.2009.11.003} }
Ivo Krka, Yuriy Brun, George Edwards, and Nenad Medvidovic	Synthesizing Partial Component-Level Behavior Models from System Specifications [Abstract] [Citation] [BibTeX]	2009	Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE09)	DOI
Abstract: Initial system specifications, such as use-case scenarios and properties, only partially specify the future system. We posit that synthesizing partial component-level behavior models from these early specifications can improve software development practices. In this paper, we provide a novel algorithm for deriving a Modal Transition System (MTS) for individual system components from system-level scenario and property specifications. These generated MTSs capture the possible component implementations that (1) necessarily provide the behavior required by the scenarios, (2) restrict behavior forbidden by the properties, and (3) leave the behavior that is neither explicitly required nor forbidden as undefined. We also show how our algorithm helps discover potential design flaws.
Citation: I. Krka, Y. Brun, G. Edwards, and N. Medvidovic (2009), "Synthesizing Partial Component-Level Behavior Models from System Specifications", In Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE09). Amsterdam, The Netherlands, August, 2009. , pp. 305-314.
BibTeX: @inproceedings{Krka09fse, author = {Ivo Krka and Yuriy Brun and George Edwards and Nenad Medvidovic}, title = {Synthesizing Partial Component-Level Behavior Models from System Specifications}, booktitle = {Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering ({ESEC/FSE}09)}, year = {2009}, pages = {305--314}, doi = {10.1145/1595696.1595756} }
Yuriy Brun and Nenad Medvidovic	Crystal-Growth-Inspired Algorithms for Computational Grids [Abstract] [Citation] [BibTeX]	2009	Proceedings of the Workshop on Bio-Inspired Algorithms for Distributed Systems (BADS09)	DOI
Abstract: Biological systems surpass man-made systems in many important ways. Most notably, systems found in nature are typically self-adaptive and self-managing, capable of surviving drastic changes in their environments, such as internal failures and malicious attacks on their components. Large distributed software systems have requirements common to those of some biological systems, particularly in the number and power of individual components and in the qualities of service of the system. However, it is not immediately clear how engineers can extract useful properties from natural systems and inject them into software systems. In this paper, we explore the nature's process of crystal growth and develop mechanisms inspired by that process for designing large distributed computational grid systems. The result is the tile architectural style, a set of design principles for building distributed software systems that solve complex computational problems. Systems developed using the tile style scale well to large computations, tolerate faults and malicious attacks, and preserve the privacy of the data.
Citation: Y. Brun and N. Medvidovic (2009), "Crystal-Growth-Inspired Algorithms for Computational Grids", In Proceedings of the Workshop on Bio-Inspired Algorithms for Distributed Systems (BADS09). Barcelona, Spain, June, 2009. , pp. 19-26.
BibTeX: @inproceedings{Brun09bads, author = {Yuriy Brun and Nenad Medvidovic}, title = {Crystal-Growth-Inspired Algorithms for Computational Grids}, booktitle = {Proceedings of the Workshop on Bio-Inspired Algorithms for Distributed Systems ({BADS}09)}, year = {2009}, pages = {19--26}, doi = {10.1145/1555284.1555288} }
Ivo Krka, George Edwards, Yuriy Brun, and Nenad Medvidovic	From System Specifications to Component Behavioral Models [Abstract] [Citation] [BibTeX]	2009	Proceedings of the New Ideas and Emerging Results Track at the 31st International Conference on Software Engineering (ICSE09). A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2008-821	DOI
Abstract: Early system specifications, such as use-case scenarios and properties, are rarely complete. Partial models of system-level behavior, derived from these specifications, have proven useful in early system analysis. We believe that the scope of possible analyses can be enhanced by component-level partial models. In this paper, we outline an algorithm for deriving a component-level Modal Transition System (MTS) from system-level scenario and property specifications. The generated MTSs capture the possible component implementations that (1) necessarily provide the behavior required by the scenarios, (2) restrict behavior forbidden by the properties, and (3) leave the behavior that is neither explicitly required nor forbidden as undefined. We discuss how these generated models can help discover system design flaws, support requirements elicitation, and help select off-the-shelf components.
Citation: I. Krka, G. Edwards, Y. Brun, and N. Medvidovic (2009), "From System Specifications to Component Behavioral Models", In Proceedings of the New Ideas and Emerging Results Track at the 31st International Conference on Software Engineering (ICSE09). Vancouver, Canada, May, 2009. pp. 315-318.
BibTeX: @inproceedings{Krka09icse-nier, author = {Ivo Krka and George Edwards and Yuriy Brun and Nenad Medvidovic}, title = {From System Specifications to Component Behavioral Models}, booktitle = {Proceedings of the New Ideas and Emerging Results Track at the 31st International Conference on Software Engineering ({ICSE}09)}, year = {2009}, pages = {315--318}, note = {A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2008-821} }
Yuriy Brun, Giovanna Di Marzo Serugendo, Cristina Gacek, Holger Giese, Holger Kienle, Marin Litoiu, Hausi Müller, Mauro Pezzè, and Mary Shaw	Engineering Self-Adaptive Systems through Feedback Loops [Abstract] [Citation] [BibTeX]	2009	Software Engineering for Self-Adaptive Systems	DOI
Abstract: To deal with the increasing complexity of software systems and uncertainty of their environments, software engineers have turned to self-adaptivity. Self-adaptive systems are capable of dealing with a continuously changing environment and emerging requirements that may be unknown at design-time. However, building such systems cost-effectively and in a predictable manner is a major engineering challenge. In this paper, we explore the state-of-the-art in engineering self-adaptive systems and identify potential improvements in the design process. Our most important finding is that in designing self-adaptive systems, the feedback loops that control self-adaptation must become first-class entities. We explore feedback loops from the perspective of control engineering and within existing self-adaptive systems in nature and biology. Finally, we identify the critical challenges our community must address to enable systematic and well-organized engineering of self-adaptive and self-managing software systems.
Citation: Y. Brun, G. Di Marzo Serugendo, C. Gacek, H. Giese, H. Kienle, M. Litoiu, H. Müller, M. Pezzè, and M. Shaw (2009), "Engineering Self-Adaptive Systems through Feedback Loops", In Software Engineering for Self-Adaptive Systems. Vol. 5525, pp. 48-70. Lecture Notes in Computer Science Hot Topics.
BibTeX: @incollection{Brun09SEfSAS, author = {Yuriy Brun and Giovanna {Di Marzo Serugendo} and Cristina Gacek and Holger Giese and Holger Kienle and Marin Litoiu and Hausi M{\"{u}}ller and Mauro Pezz{\`{e}} and Mary Shaw}, title = {Engineering Self-Adaptive Systems through Feedback Loops}, booktitle = {Software Engineering for Self-Adaptive Systems}, publisher = {Lecture Notes in Computer Science Hot Topics}, year = {2009}, volume = {5525}, pages = {48--70}, doi = {10.1007/978-3-642-02161-9_3} }
Betty H.C. Cheng, Rogério de Lemos, Holger Giese, Paola Inverardi, Jeff Magee, Jesper Andersson, Basil Becker, Nelly Bencomo, Yuriy Brun, Bojan Cukic, Giovanna Di Marzo Serugendo, Schahram Dustdar, Anthony Finkelstein, Cristina Gacek, Kurt Geihs, Vincenzo Grassi, Gabor Karsai, Holger M. Kienle, Jeff Kramer, Marin Litoiu, Sam Malek, Raffaela Mirandola, Hausi A. Müller, Sooyong Park, Mary Shaw, Matthias Tichy, Massimo Tivoli, Danny Weyns, and Jon Whittle	Software Engineering for Self-Adaptive Systems: A Research Roadmap [Abstract] [Citation] [BibTeX]	2009	Software Engineering for Self-Adaptive Systems	DOI
Abstract: The goal of this roadmap paper is to summarize the state-of-the-art and to identify critical challenges for the systematic software engineering of self-adaptive systems. The paper is partitioned into four parts, one for each of the identified essential views of self-adaptation: modelling dimensions, requirements, engineering, and assurances. For each view, we present the state-of-the-art and the challenges that our community must address. This roadmap paper is a result of the Dagstuhl Seminar 08031 on ``Software Engineering for Self-Adaptive Systems,'' which took place in January 2008.
Citation: B.H. Cheng, R. de Lemos, H. Giese, P. Inverardi, J. Magee, J. Andersson, B. Becker, N. Bencomo, Y. Brun, B. Cukic, G. Di Marzo Serugendo, S. Dustdar, A. Finkelstein, C. Gacek, K. Geihs, V. Grassi, G. Karsai, H.M. Kienle, J. Kramer, M. Litoiu, S. Malek, R. Mirandola, H.A. Müller, S. Park, M. Shaw, M. Tichy, M. Tivoli, D. Weyns, and J. Whittle (2009), "Software Engineering for Self-Adaptive Systems: A Research Roadmap", In Software Engineering for Self-Adaptive Systems. Vol. 5525, pp. 1-26. Lecture Notes in Computer Science Hot Topics
BibTeX: @incollection{Cheng09, author = {Betty H.C. Cheng and Rog\'{e}rio de Lemos and Holger Giese and Paola Inverardi and Jeff Magee and Jesper Andersson and Basil Becker and Nelly Bencomo and Yuriy Brun and Bojan Cukic and Giovanna {Di Marzo Serugendo} and Schahram Dustdar and Anthony Finkelstein and Cristina Gacek and Kurt Geihs and Vincenzo Grassi and Gabor Karsai and Holger M. Kienle and Jeff Kramer and Marin Litoiu and Sam Malek and Raffaela Mirandola and Hausi A. M\"{u}ller and Sooyong Park and Mary Shaw and Matthias Tichy and Massimo Tivoli and Danny Weyns and Jon Whittle}, title = {Software Engineering for Self-Adaptive Systems: A Research Roadmap}, booktitle = {Software Engineering for Self-Adaptive Systems}, publisher = {Lecture Notes in Computer Science Hot Topics}, year = {2009}, volume = {5525}, pages = {1--26}, doi = {10.1007/978-3-642-02161-9_1} }
Yuriy Brun and Dustin Reishus	Path Finding in the Tile Assembly Model [Abstract] [Citation] [BibTeX]	2009	Theoretical Computer Science. A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2008-802	DOI
Abstract: Swarm robotics, active self-assembly, and amorphous computing are fields that focus on designing systems of large numbers of small, simple components that can cooperate to complete complex tasks. Many of these systems are inspired by biological systems, and all attempt to use the simplest components and environments possible, while still being capable of achieving their goals. The canonical problems for such biologically-inspired systems are shape assembly and path finding. In this paper, we demonstrate path finding in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. As in related work, our systems function in the presence of obstacles and can be made fault-tolerant. The path-finding systems use O(1) distinct components and find minimal-length paths in time linear in the length of the path.
Citation: Y. Brun and D. Reishus (2009), "Path Finding in the Tile Assembly Model", Theoretical Computer Science. Essex, UK, April, 2009. Vol. 410(15), pp. 1461-1472. Elsevier.
BibTeX: @article{Brun09path-finding, author = {Yuriy Brun and Dustin Reishus}, title = {Path Finding in the Tile Assembly Model}, journal = {Theoretical Computer Science}, publisher = {Elsevier}, year = {2009}, volume = {410}, number = {15}, pages = {1461--1472}, note = {A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2008-802}, doi = {10.1016/j.tcs.2008.12.008} }
Yuriy Brun and Dustin Reishus	Connecting the Dots: Molecular Machinery for Distributed Robotics [Abstract] [Citation] [BibTeX]	2009	Lecture Notes on Computer Science: DNA Computing. A previous version appeared in the Proceedings of the 14th International Meeting on DNA Computing (DNA08), pages 27-35, 2008	DOI
Abstract: Nature is considered one promising area to search for inspiration in designing robotic systems. Some work in swarm robotics has tried to build systems that resemble distributed biological systems and inherit biology's fault tolerance, scalability, dependability, and robustness. Such systems, as well as ones in the areas of active self-assembly and amorphous computing, typically use relatively simple components with limited computation, memory, and computational power to accomplish complex tasks such as forming paths in the presence of obstacles. We demonstrate that such tasks can be accomplished in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. Our systems use a small number of distinct components to find minimal-length paths in time linear in the length of the path while inheriting scalability and fault tolerance of the underlying natural process of self-assembly.
Citation: Y. Brun and D. Reishus (2009), "Connecting the Dots: Molecular Machinery for Distributed Robotics", Lecture Notes on Computer Science: DNA Computing. Vol. 5347/2009, pp. 102-111.
BibTeX: @article{Brun09dna-lncs, author = {Yuriy Brun and Dustin Reishus}, title = {Connecting the Dots: Molecular Machinery for Distributed Robotics}, booktitle = {{DNA} Computing}, journal = {Lecture Notes on Computer Science}, year = {2009}, volume = {5347/2009}, pages = {102--111}, doi = {10.1007/978-3-642-03076-5_9}, note = {A previous version appeared in the Proceedings of the 14th International Meeting on {DNA} Computing ({DNA}08), pages 27--35, 2008} }
Yuriy Brun	Solving Satisfiability in the Tile Assembly Model with a Constant-Size Tileset [Abstract] [Citation] [BibTeX]	2008	Journal of Algorithms	DOI
Abstract: Biological systems are far more complex and robust than systems we can engineer today. One way to increase the complexity and robustness of our engineered systems is to study how biological systems function. The tile assembly model is a highly distributed parallel model of nature's self-assembly. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply, factor, and solve SubsetSum. Here, I present a system that decides satisfiability, a well-known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in the input. The system requires only a constant number of different tile types: 64, an improvement over previously best known system that uses O(n²) tile types. I describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to 1.
Citation: Y. Brun (2008), "Solving Satisfiability in the Tile Assembly Model with a Constant-Size Tileset", Journal of Algorithms. Duluth, MN, USA Vol. 63(4), pp. 151-166. Academic Press, Inc.
BibTeX: @article{Brun08sat, author = {Yuriy Brun}, title = {Solving Satisfiability in the Tile Assembly Model with a Constant-Size Tileset}, journal = {Journal of Algorithms}, publisher = {Academic Press, Inc.}, year = {2008}, volume = {63}, number = {4}, pages = {151--166}, note = {A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2008-801}, doi = {10.1016/j.jalgor.2008.07.002} }
Yuriy Brun	Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time [Abstract] [Citation] [BibTeX]	2008	Lecture Notes on Computer Science: DNA Computing. A previous version appeared as "Asymptotically Optimal Program Size Complexity for Solving NP-Complete Problems in the Tile Assembly Model" in the Proceedings of the 13th International Meeting on DNA Computing (DNA07), pages 231--240, 2007	DOI
Abstract: The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to nondeterministically decide a set, and present a system that solves an NP-complete problem called SubsetSum. Because of the nature of NP-complete problems, this system can be used to solve all NP problems in nondeterministic polynomial time, with high probability. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense "large" and "slow." The system presented here uses 49 = O(1) different tiles and computes in time linear in the input size. I also propose how such systems can be leveraged to program large distributed software systems.
Citation: Y. Brun (2008), "Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time", Lecture Notes on Computer Science: DNA Computing. Vol. 4848/2008, pp. 26-35. Springer Berlin / Heidelberg.
BibTeX: @article{Brun08dna-lncs, author = {Yuriy Brun}, title = {Constant-Size Tileset for Solving an {NP}-Complete Problem in Nondeterministic Linear Time}, booktitle = {{DNA} Computing}, journal = {Lecture Notes on Computer Science}, publisher = {Springer Berlin / Heidelberg}, year = {2008}, volume = {4848/2008}, pages = {26--35}, note = {A previous version appeared as ``Asymptotically Optimal Program Size Complexity for Solving {NP}-Complete Problems in the Tile Assembly Model'' in the Proceedings of the 13th International Meeting on {DNA} Computing ({DNA}07), pages 231--240, 2007}, doi = {10.1007/978-3-540-77962-9_3} }
Yuriy Brun	Reducing Tileset Size: 3-SAT and Beyond [Abstract] [Citation] [BibTeX]	2008	Proceedings of the 14th International Meeting on DNA Computing (DNA08)
Abstract: In self-assembly research, reducing the number of distinct tiles necessary to compute functions can make it feasible to implement tile systems to solve complex problems. Existing methods for solving 3-SAT, a well-known NP-complete problem, in the tile assembly model involve either using O(n²) distinct tiles to nondeterministically decide whether an n-variable Boolean formula is satisfiable or simulating a cellular automata system simulating a Turing machine, which requires a constant but large number of tiles to deterministically make the decision. Here, I propose a system that solves k-SAT nondeterministically, for all k, in time linear in the input size using only 64 distinct tiles. Further, I propose a mechanism for converting the tilesets of tile systems for many NP-complete and other problems from tilesets whose size depends on the input into O(1)-size tilesets.
Citation: Y. Brun (2008), "Reducing Tileset Size: 3-SAT and Beyond", In Proceedings of the 14th International Meeting on DNA Computing (DNA08). Prague, Czech Republic, June, 2008. pp. 178.
BibTeX: @inproceedings{Brun08dna-sat, author = {Yuriy Brun}, title = {Reducing Tileset Size: 3-{SAT} and Beyond}, booktitle = {Proceedings of the 14th International Meeting on {DNA} Computing ({DNA}08)}, year = {2008}, pages = {178} }
Yuriy Brun	Self-Assembly for Discreet, Fault-Tolerant, and Scalable Computation on Internet-Sized Distributed Networks [Abstract] [Citation] [BibTeX]	2008	Ph.D. Dissertation: University of Southern California	URL
Abstract: When engineers compare biological and software systems, the former come out ahead in the majority of dimensions. For example, the human body is far more complex, better suited to deal with faulty components, more resistant to malicious agents such as viruses, and more adaptive to environmental changes than your favorite operating system. Thus it follows that we, the engineers, may be able to build better software systems than the ones we build today by borrowing technologies from nature and injecting them into our system design process. In this dissertation, I present an architectural style and accompanying implementation support for building distributed software systems that allow large networks, such as the Internet, to solve computationally intensive problems. This architectural style, the tile style, is based on a nature's system of crystal growth, and thus inherits some of nature's dependability, fault and adversary tolerance, scalability, and security. The tile style allows one to distribute computation onto a large network in a way that guarantees that unless someone controls a large fraction of the network, they cannot learn the private data within the computation or force the computation to fail. These systems are highly scalable, capable of dealing with faulty and malicious nodes, and are discreet since every sufficiently small group of nodes knows neither the problem nor the data. The tile style is based on a formal mathematical model of self-assembly. In order to leverage this model to build software, I define the notion of self-assembling computation and develop systems that compute functions such as adding, multiplying, factoring, and solving NP-complete problems SubsetSum and SAT. For each system, I prove its correctness, compute its probability of successful computation, and show that its running time and tileset size are asymptotically optimal. I use the mathematical nature of the tile assembly model to present a formal mathematical analysis of the tile style, proving that software systems built using this style are discreet, fault- and adversary-tolerant, and scalable. I further implement a tile-style system and use it to distribute computation to empirically evaluate the tile style's utility.
Citation: Y. Brun (2008), "Self-Assembly for Discreet, Fault-Tolerant, and Scalable Computation on Internet-Sized Distributed Networks." Ph.D. Dissertation: University of Southern California. Los Angeles, CA, USA, May.
BibTeX: @phdthesis{Brun08PhD, author = {Yuriy Brun}, title = {Self-Assembly for Discreet, Fault-Tolerant, and Scalable Computation on {I}nternet-Sized Distributed Networks}, school = {University of Southern California}, year = {2008}, url = {http://proquest.umi.com/pqdlink?did=1564036421&Fmt=7&clientI d=79356&RQT=309&VName=PQD} }
Yuriy Brun	Solving NP-Complete Problems in the Tile Assembly Model [Abstract] [Citation] [BibTeX]	2008	Theoretical Computer Science. A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2007-703	DOI
Abstract: Formalized study of self-assembly has led to the definition of the tile assembly model, a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply, and factor. Here, I extend the notion of computation to include deciding subsets of the natural numbers, and present a system that decides SubsetSum, a well known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in the input. The system requires only a constant number of different tile types: 49. I describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to 1.
Citation: Y. Brun (2008), "Solving NP-Complete Problems in the Tile Assembly Model", Theoretical Computer Science. Essex, UK Vol. 395(1), pp. 31-46. Elsevier.
BibTeX: @article{Brun08np-c, author = {Yuriy Brun}, title = {Solving {NP}-Complete Problems in the Tile Assembly Model}, journal = {Theoretical Computer Science}, publisher = {Elsevier}, year = {2008}, volume = {395}, number = {1}, pages = {31--46}, note = {A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2007-703}, doi = {10.1016/j.tcs.2007.07.052} }
Yuriy Brun	Nondeterministic Polynomial Time Factoring in the Tile Assembly Model [Abstract] [Citation] [BibTeX]	2008	Theoretical Computer Science. A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2007-707	DOI
Abstract: Formalized study of self-assembly has led to the definition of the tile assembly model. Previously, I presented ways to compute arithmetic functions, such as addition and multiplication, in the tile assembly model: a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Here, I present tile assembly model systems that factor numbers nondeterministically using O(1) distinct components. The computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. I describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to 1.
Citation: Y. Brun (2008), "Nondeterministic Polynomial Time Factoring in the Tile Assembly Model", Theoretical Computer Science. Essex, UK Vol. 395(1), pp. 3-23. Elsevier.
BibTeX: @article{Brun08factor, author = {Yuriy Brun}, title = {Nondeterministic Polynomial Time Factoring in the Tile Assembly Model}, journal = {Theoretical Computer Science}, publisher = {Elsevier}, year = {2008}, volume = {395}, number = {1}, pages = {3--23}, note = {A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2007-707}, doi = {10.1016/j.tcs.2007.07.051} }
Yuriy Brun	Building Biologically-Inspired Self-Adapting Systems [Abstract] [Citation] [BibTeX]	2008	Proceedings of the Schloss Dagstuhl seminar 08031: Software Engineering for Self-Adaptive Systems	URL
Abstract: Biological systems are far more complex than systems we design and build today. The human body alone has orders of magnitude more complexity than our most-intricate designed systems. Further, biological systems are decentralized in such a way that allows them to benefit from built-in error-correction, fault tolerance, and scalability. It follows that if we can extract certain properties of biological systems and inject them into our software design process, we may be able to build complex self-adaptive software systems. Biological systems’ complexity makes them not only desirable to guide software design, but also difficult to fully understand. Thus one approach to building software similar to biological systems is by first building models of biology that we can understand. Then these models can guide the high-level design, or architecture of the software systems, resulting in systems that retain the model’s fault tolerance, scalability, and other properties. I present a general outline of how one might use biology to create a model to guide the architecture of a software system, and develop one such model and the resulting architectural style, the tile style, for computational systems that can use a large distributed network of computers, such as the Internet, to solve computationally-intensive problems in a discreet, fault-tolerant, and scalable manner.
Citation: Y. Brun (2008), "Building Biologically-Inspired Self-Adapting Systems", In Proceedings of the Schloss Dagstuhl seminar 08031: Software Engineering for Self-Adaptive Systems. Dagstuhl, Germany, January, 2008.
BibTeX: @inproceedings{Brun08dagstuhl, author = {Yuriy Brun}, title = {Building Biologically-Inspired Self-Adapting Systems}, booktitle = {Proceedings of the Schloss Dagstuhl seminar 08031: Software Engineering for Self-Adaptive Systems}, year = {2008}, url = {http://drops.dagstuhl.de/opus/volltexte/2008/1499} }
Yuriy Brun and Nenad Medvidovic	Fault and Adversary Tolerance as an Emergent Property of Distributed Systems' Software Architectures [Abstract] [Citation] [BibTeX]	2007	Proceedings of the 2nd International Workshop on Engineering Fault Tolerant Systems (EFTS07)	DOI
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.
Citation: Y. Brun and N. Medvidovic (2007), "Fault and Adversary Tolerance as an Emergent Property of Distributed Systems' Software Architectures", In Proceedings of the 2nd International Workshop on Engineering Fault Tolerant Systems (EFTS07). Dubrovnik, Croatia, September, 2007. pp. 38-43.
BibTeX: @inproceedings{Brun07efts, author = {Yuriy Brun and Nenad Medvidovic}, title = {Fault and Adversary Tolerance as an Emergent Property of Distributed Systems' Software Architectures}, booktitle = {Proceedings of the 2nd International Workshop on Engineering Fault Tolerant Systems ({EFTS}07)}, year = {2007}, pages = {38--43} }
Yuriy Brun and Nenad Medvidovic	An Architectural Style for Solving Computationally Intensive Problems on Large Networks [Abstract] [Citation] [BibTeX]	2007	Proceedings of Software Engineering for Adaptive and Self-Managing Systems (SEAMS07)	DOI
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).
Citation: Y. Brun and N. Medvidovic (2007), "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.
BibTeX: @inproceedings{Brun07seams, author = {Yuriy Brun and Nenad Medvidovic}, title = {An Architectural Style for Solving Computationally Intensive Problems on Large Networks}, booktitle = {Proceedings of Software Engineering for Adaptive and Self-Managing Systems ({SEAMS}07)}, year = {2007}, doi = {10.1109/SEAMS.2007.4} }
Yuriy Brun	A Discreet, Fault-Tolerant, and Scalable Software Architectural Style for Internet-Sized Networks [Abstract] [Citation] [BibTeX]	2007	Proceedings of the Doctoral Symposium at the 29th International Conference on Software Engineering (ICSE07)	DOI
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 Internet-sized systems exists. I 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 cannot break the computation), and (3) scalability (communication among the nodes does not increase with network or problem size). I plan to evaluate the style both theoretically and empirically for these three properties.
Citation: Y. Brun (2007), "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). Minneapolis, MN, USA, May, 2007. pp. 83-84.
BibTeX: @inproceedings{Brun07icse-doc-symp, author = {Yuriy Brun}, title = {A Discreet, Fault-Tolerant, and Scalable Software Architectural Style for {I}nternet-Sized Networks}, booktitle = {Proceedings of the Doctoral Symposium at the 29th International Conference on Software Engineering ({ICSE}07)}, year = {2007}, pages = {83--84}, doi = {10.1109/ICSECOMPANION.2007.12} }
Yuriy Brun	Adding and Multiplying in the Tile Assembly Model [Abstract] [Citation] [BibTeX]	2007	Proceedings of the 4th Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO07)
Abstract: The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to compute a function deterministically and present systems that add and multiply. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense "large" and "slow." The systems presented here all use O(1) different tiles (8 to add and 28 to multiply) and compute in time linear in the input size.
Citation: Y. Brun (2007), "Adding and Multiplying in the Tile Assembly Model", In Proceedings of the 4th Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO07). Snowbird, UT, USA, April, 2007.
BibTeX: @inproceedings{Brun07fnano, author = {Yuriy Brun}, title = {Adding and Multiplying in the Tile Assembly Model}, booktitle = {Proceedings of the 4th Foundations of Nanoscience: Self-Assembled Architectures and Devices ({FNANO}07)}, year = {2007} }
Yuriy Brun	Arithmetic Computation in the Tile Assembly Model: Addition and Multiplication [Abstract] [Citation] [BibTeX]	2007	Theoretical Computer Science	DOI
Abstract: Formalized study of self-assembly has led to the definition of the tile assembly model. Research has identified two issues at the heart of self-assembling systems: the number of steps it takes for an assembly to complete, assuming maximum parallelism, and the minimal number of tiles necessary to assemble a shape. In this paper, I define the notion of a tile assembly system that computes a function, and tackle these issues for systems that compute the sum and product of two numbers. I demonstrate constructions of such systems with optimal O(1) distinct tile types and prove the assembly time is linear in the size of the input.
Citation: Y. Brun (2007), "Arithmetic Computation in the Tile Assembly Model: Addition and Multiplication", Theoretical Computer Science. Essex, UK, June, 2007. Vol. 378(1), pp. 17-31. Elsevier.
BibTeX: @article{Brun07arith, author = {Yuriy Brun}, title = {Arithmetic Computation in the Tile Assembly Model: Addition and Multiplication}, journal = {Theoretical Computer Science}, publisher = {Elsevier}, year = {2007}, volume = {378}, number = {1}, pages = {17--31}, doi = {10.1016/j.tcs.2006.10.025} }
Yuriy Brun and Manoj Gopalkrishnan	Toward In Vivo Disease Diagnosis and Treatment Using DNA [Abstract] [Citation] [BibTeX]	2006	Proceedings of the 2006 International Conference on Bioinformatics & Computational Biology (BIOCOMP06)
Abstract: We propose a technique to diagnose and treat individual cells in the human body. A virus-like system delivers a copy of a diagnosis and treatment DNA complex to each cell. The complex determines whether the cell has a specific disease based on the presence or absence of indicator mRNA molecules and, if the diagnosis is positive, releases a proper drug for treatment. As a tool for the diagnosis and treatment system, we develop a DNA implementation of an arbitrary finite state machine.
Citation: Y. Brun and M. Gopalkrishnan (2006), "Toward In Vivo Disease Diagnosis and Treatment Using DNA", In Proceedings of the 2006 International Conference on Bioinformatics & Computational Biology (BIOCOMP06). Las Vegas, NV, USA, June, 2006. pp. 182-186.
BibTeX: @inproceedings{Brun06biocomp, author = {Yuriy Brun and Manoj Gopalkrishnan}, title = {Toward In Vivo Disease Diagnosis and Treatment Using {DNA}}, booktitle = {Proceedings of the 2006 International Conference on Bioinformatics \& Computational Biology ({BIOCOMP}06)}, year = {2006}, pages = {182--186} }
Dustin Reishus, Bilal Shaw, Yuriy Brun, Nickolas Chelyapov, and Leonard Adleman	Self-Assembly of DNA Double-Double Crossover Complexes into High-Density, Doubly Connected, Planar Structures [Citation] [BibTeX]	2005	Journal of the American Chemical Society (JACS)	DOI
Citation: D. Reishus, B. Shaw, Y. Brun, N. Chelyapov, and L. Adleman (2005), "Self-Assembly of DNA Double-Double Crossover Complexes into High-Density, Doubly Connected, Planar Structures", Journal of the American Chemical Society (JACS), November, 2005. Vol. 127(50), pp. 17590-17591.
BibTeX: @article{Reishus05, author = {Dustin Reishus and Bilal Shaw and Yuriy Brun and Nickolas Chelyapov and Leonard Adleman}, title = {Self-Assembly of {DNA} Double-Double Crossover Complexes into High-Density, Doubly Connected, Planar Structures}, journal = {Journal of the American Chemical Society ({JACS})}, year = {2005}, volume = {127}, number = {50}, pages = {17590--17591} }
Nickolas Chelyapov, Yuriy Brun, Manoj Gopalkrishnan, Dustin Reishus, Bilal Shaw, and Leonard Adleman	DNA Triangles and Self-Assembled Hexagonal Tilings [Citation] [BibTeX]	2004	Journal of the American Chemical Society (JACS)	DOI
Citation: N. Chelyapov, Y. Brun, M. Gopalkrishnan, D. Reishus, B. Shaw, and L. Adleman (2004), "DNA Triangles and Self-Assembled Hexagonal Tilings", Journal of the American Chemical Society (JACS), October, 2004. Vol. 126(43), pp. 13924-13925.
BibTeX: @article{Chelyapov04, author = {Nickolas Chelyapov and Yuriy Brun and Manoj Gopalkrishnan and Dustin Reishus and Bilal Shaw and Leonard Adleman}, title = {{DNA} Triangles and Self-Assembled Hexagonal Tilings}, journal = {Journal of the American Chemical Society ({JACS})}, year = {2004}, volume = {126}, number = {43}, pages = {13924-13925} }
Yuriy Brun, Manoj Gopalkrishnan, Dustin Reishus, Bilal Shaw, Nickolas Chelyapov, and Leonard Adleman	Building Blocks for DNA Self-Assembly [Abstract] [Citation] [BibTeX]	2004	Proceedings of the 1st Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO04)
Abstract: DNA complexes, like the double crossover, are used as building blocks for the assembly of higher-order structures. Currently, the number of experimentally proven reliable complexes is small. We have begun work on expanding the collection of such complexes. Here we report on our design concepts and initial experiments. In particular, we present experimental evidence of two new complexes: quadruple crossovers and triangles. In principle, quadruple crossovers can be extended to three-dimensional, spacefilling lego brick complexes, while triangles are capable of hexagonally tiling the plane.
Citation: Y. Brun, M. Gopalkrishnan, D. Reishus, B. Shaw, N. Chelyapov, and L. Adleman (2004), "Building Blocks for DNA Self-Assembly", In Proceedings of the 1st Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO04). Snowbird, UT, USA, April, 2004. pp. 2-15.
BibTeX: @inproceedings{Brun04fnano, author = {Yuriy Brun and Manoj Gopalkrishnan and Dustin Reishus and Bilal Shaw and Nickolas Chelyapov and Leonard Adleman}, title = {Building Blocks for {DNA} Self-Assembly}, booktitle = {Proceedings of the 1st Foundations of Nanoscience: Self-Assembled Architectures and Devices ({FNANO}04)}, year = {2004}, pages = {2-15} }
Yuriy Brun and Michael D. Ernst	Finding Latent Code Errors via Machine Learning Over Programs Executions [Abstract] [Citation] [BibTeX]	2004	Proceedings of the 26th International Conference on Software Engineering (ICSE04)	DOI
Abstract: This paper proposes a technique for identifying program properties that indicate errors. The technique generates machine learning models of program properties known to result from errors, and applies these models to program properties of user-written code to classify and rank properties that may lead the user to errors. Given a set of properties produced by the program analysis, the technique selects a subset of properties that are most likely to reveal an error. An implementation, the Fault Invariant Classifier, demonstrates the efficacy of the technique. The implementation uses dynamic invariant detection to generate program properties. It uses support vector machine and decision tree learning tools to classify those properties. In our experimental evaluation, the technique increases the relevance (the concentration of fault-revealing properties) by a factor of 50 on average for the C programs, and 4.8 for the Java programs. Preliminary experience suggests that most of the fault-revealing properties do lead a programmer to an error.
Citation: Y. Brun and M.D. Ernst (2004), "Finding Latent Code Errors via Machine Learning Over Programs Executions", In Proceedings of the 26th International Conference on Software Engineering (ICSE04). Edinburgh, Scotland. pp. 480-490.
BibTeX: @inproceedings{Brun04icse, author = {Yuriy Brun and Michael D. Ernst}, title = {Finding Latent Code Errors via Machine Learning Over Programs Executions}, booktitle = {Proceedings of the 26th International Conference on Software Engineering ({ICSE}04)}, year = {2004}, pages = {480--490}, doi = {10.1109/ICSE.2004.1317470} }
Yuriy Brun	Software Fault Identification via Dynamic Analysis and Machine Learning [Abstract] [Citation] [BibTeX]	2003	Masters Thesis: Massachusetts Institute of Technology	URL
Abstract: I propose a technique that identifies program properties that may indicate errors. The technique generates machine learning models of run-time program properties known to expose faults, and applies these models to program properties of user-written code to classify and rank properties that may lead the user to errors. I evaluate an implementation of the technique, the Fault Invariant Classifier, that demonstrates the efficacy of the error finding technique. The implementation uses dynamic invariant detection to generate program properties. It uses support vector machine and decision tree learning tools to classify those properties. Given a set of properties produced by the program analysis, some of which are indicative of errors, the technique selects a subset of properties that are most likely to reveal an error. The experimental evaluation over 941,000 lines of code, showed that a user must examine only the 2.2 highest-ranked properties for C programs and 1.7 for Java programs to find a fault-revealing property. The technique increases the relevance (the concentration of properties that reveal errors) by a factor of 50 on average for C programs, and 4.8 for Java programs.
Citation: Y. Brun (2003), "Software Fault Identification via Dynamic Analysis and Machine Learning." Masters Thesis: Massachusetts Institute of Technology. Cambridge, MA, USA, August, 2003.
BibTeX: @mastersthesis{Brun03masters, author = {Yuriy Brun}, title = {Software Fault Identification via Dynamic Analysis and Machine Learning}, school = {Massachusetts Institute of Technology}, year = {2003}, url = {http://hdl.handle.net/1721.1/17939}, }
Yuriy Brun	The Four-Color Theorem [Abstract] [Citation] [BibTeX]	2002	Undergraduate Journal of Mathematics
Abstract: In this review paper, I introduce graph theory, and discuss the Four Color Theorem. Then I prove several theorems, including Euler’s formula and the Five Color Theorem.
Citation: Y. Brun (2002), "The Four-Color Theorem", Undergraduate Journal of Mathematics. Cambridge, MA, USA, May, 2002. pp. 21-28. MIT Department of Mathematics.
BibTeX: @article{Brun02four-color, author = {Yuriy Brun}, title = {The Four-Color Theorem}, journal = {Undergraduate Journal of Mathematics}, publisher = {{MIT} Department of Mathematics}, year = {2002}, pages = {21--28} }
Daniel Vekhter, Alex Rasin, and Yuriy Brun	Mutual Exclusion Algorithms in Distributed Networks [Abstract] [Citation] [BibTeX]	1997	Journal of Student Research, Science and Technology
Abstract: The problem of mutual exclusion is ever-present in distributed networks. Various algorithms have been suggested as a means to solve the problem. This paper discusses the efficiency of three such algorithms --- Test-and-Set bit, Dijkstra's, and Peterson's. The performance of each of the algorithms depends on the number of competing processes and the length of the remainder section. Our experimental results show which of the three algorithms are the most efficient to use depending on the size of the network and the number of remainder steps.
Citation: D. Vekhter, A. Rasin, and Y. Brun (1997), "Mutual Exclusion Algorithms in Distributed Networks", Journal of Student Research, Science and Technology. Largo, MD, USA, February, 1997. Vol. 2(1), pp. 65-67. Resource Center, Prince George's Community College.
BibTeX: @article{Vekhter97, author = {Daniel Vekhter and Alex Rasin and Yuriy Brun}, title = {Mutual Exclusion Algorithms in Distributed Networks}, journal = {Journal of Student Research, Science and Technology}, publisher = {Resource Center, Prince George's Community College}, year = {1997}, volume = {2}, number = {1}, pages = {65--67} }