| Author | Title | Year | Journal/Proceedings | DOI/URL | |
|---|---|---|---|---|---|
| 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 | 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. In Press | |||||
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 = {In Press},
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 | 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 | 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 | 2009 | Proceedings of the New Ideas and Emerging Results Track at the 31st International Conference on Software Engineering (ICSE09). A previous version appeared as a Center for Software Engineering, University of Southern California 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 a Center for Software Engineering, University of Southern California 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 | 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 | 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 | 2009 | Theoretical Computer Science. A previous version appeared as a Center for Software Engineering, University of Southern California 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 a Center for Software Engineering, University of Southern California 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 | 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 | ||
| 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},
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 | 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(n2) 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 a Center for Software Engineering, University of Southern California 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 | 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 | 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(n2) 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 | 2008 | Ph.D. Thesis: 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. Thesis: 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 | 2008 | Theoretical Computer Science. A previous version appeared as a Center for Software Engineering, University of Southern California 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 a Center for Software Engineering, University of Southern California 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 | 2008 | Theoretical Computer Science. A previous version appeared as a Center for Software Engineering, University of Southern California 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 a Center for Software Engineering, University of Southern California technical report USC-CSSE-2007-707},
doi = {10.1016/j.tcs.2007.07.051}
}
|
|||||
| Yuriy Brun | Building Biologically-Inspired Self-Adapting Systems | 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 | 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 | 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/ICSEW.2007.31}
}
|
|||||
| Yuriy Brun | A Discreet, Fault-Tolerant, and Scalable Software Architectural Style for Internet-Sized Networks | 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 | 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 | 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 | 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 | 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 | 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 | 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 | 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, May, 2004. 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 | 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 | 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 | 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}
}
|
|||||