Research
Programming Languages and Computational Orchestration
I'm in the research group of Profs. Chris Rossbach, William Cook, and Jayadev Misra, investigating computational orchestration — specifically the model of programming languages and distributed computing embodied by Orc.
Distributed Orchestration: Programming the “Internet of Things”
Publication: , John A.; , Arthur Michener; , William R. Implicitly Distributing Pervasively Concurrent Programs [extended abstract]. In: PMLDC’16: First Workshop on Programming Models and Languages for Distributed Computing; 2016 Jul 17; Rome. ACM; 2016. Article 1. doi:10.1145/2957319.2957370.
Until recently, the Internet has been used as a network of information—delivering e-mail messages, Web pages, audio-video programs, and other units of data to its users. Now, the Internet is increasingly used as a network of activities. For example, internet technologies are used for coordination by various devices in home automation systems, for control of utility networks, or for cooperation within multi-robot teams. The applications envisioned for the much-discussed “internet of things” are predominantly network-of-activities-style applications.
These shifts in the types of network applications drive shifts in the types of programming necessary.
Software systems are engineered by decomposing them into modules. For example, object-based systems use objects as the primary decomposition unit. Although most modern software systems are object-oriented, current distribution technologies do not permit objects to span network nodes. This requires that distributed software be written as a set of communicating objects, where each object must be completely contained on one node.
The designer of an object-based software system determines a “natural” decomposition of the problem into objects. However, in a distributed system, if a natural design choice would result in an object that would span multiple nodes, the designer must artificially split up the object and place parts of it on the various nodes. From a software engineering prospective, design requirements for modularity and distribution are in conflict.
To allow a program’s design to be maintained in its natural form, we are creating a novel programing language called Distributed Orc, which allows a single program text to be executed across multiple hardware nodes distributed across a network. Module boundaries within the program text need not align with hardware communication boundaries, thus allowing separation of distribution concerns from modularity concerns. This is in stark contrast to other approaches to distribution.
To enable this, Distributed Orc makes dynamic distribution decisions at a fine-grained (sub-expression) level, based on the current distribution state, needs for data at various nodes, and a cost model of communication. In conventional programming languages, attempting to distribute subexpressions would be intractable, because of the difficulty of maintaining intact the language mechanisms provided to the programmer (i.e. the language semantics), and because of the large amount of communication that would result in such languages. This work demonstrates that there are language semantics that are both easily usable to programmers and that make this fine-grained automatic distribution feasible, thus greatly simplifying the programming model for future distributed systems.
Orc — Structured Concurrency
Orc uses four combinators to express concurrency. (Surprisingly, the familiar fork–join construct is not one of them.) These four combinators form an simple but very expressive system for structuring concurrent work. Using Orc's combinators has been called “structured concurrent programming”, drawing an analogy to structured programming's replacement of unmethodical use of goto and if statements with systematic control statements.
One can think of a continuum of types of parallelism, from processor instruction-level parallelism at the fine-grained end, to loosely-coupled cross-organization human process concurrency at the course-grained end of the continuum. Orc addresses the needs at the middle-to-course part of the continuum, by providing language semantics for developers to easily use services such as wide-area distributed services (for example, Web services) and address the resulting reliability and timing concerns.
The Orc research group (several graduate students, including me) enhance and maintain the language and its compiler, runtime engine, and library (mostly written in Scala). I'm also the author of the Orc language plug-in for the Eclipse Integrated Development Environment. (Also available in the Eclipse Marketplace.)
Report: , Brian; , David; , John A.; , Jayadev. Orc User Guide v2.1.0. The University of Texas at Austin, Department of Computer Science; 2013 Sep 21. 74 p. Report No.: TR-13-23. Available from: http://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2208.pdf
Report: , Brian; , David; , John A.; , Jayadev. Orc Reference Manual v2.1.0. The University of Texas at Austin, Department of Computer Science; 2013 Sep 21. 229 p. Report No.: TR-13-24. Available from: http://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2209.pdf
Publication: , Arthur Michener; , David; , John A.; , William R. OrcO: A Concurrency-First Approach to Objects. In: OOPSLA’16: Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications; 2016 Oct 30–Nov 4; Amsterdam. ACM; 2016. p. 548–567. doi:10.1145/2983990.2984022.
Orchestration of Robotics
Orchestration languages (Orc in particular) are suitable for coordinating the agents in robotic systems. Tasks expected of robots have evolved to require coordination among multiple active entities (agents) in a dynamic environment.
Here at UTCS, our roboticists cite the example of a user asking a service robotics system to bring a drink from a coffee shop. Some activities in accomplishing this assignment are: 1) determining the appropriate robot to allocate to transporting the drink from the coffee shop to the user; 2) notifying the coffee shop to prepare the drink and arranging payment; 3) instructing a robot to retrieve the drink and transport it; and 4) control of building systems facilitating the robot’s journey, such as doors and elevators.
Allocating, coordinating, and monitoring these agents is a coordination problem. Coordination from a central point, called orchestration, is an essentially concurrent activity. In the coffee example above, monitoring the robot’s progress and controlling the building systems must occur concurrently.
Addressing these types of coordination problems is difficult or even intractable for software developers in conventional languages. Orc, as an orchestration programming language, is designed to express concurrent programs naturally, so it seems to be a natural fit for this problem domain. The current work is to explore this possibility and qualitatively evaluate it.
Updating Executing Orc Programs
A problem that I have worked on (but is currently dormant) is updating running Orc programs. A large class of envisioned Orc applications are long-running processes, such as workflow procedures. These processes can be expensive to shut down to update the program. For example, if a workflow job representing an insurance claim has been in progress for weeks, it would be very undesirable to restart it because the claims handling rules have been updated. Migration of running instances from an old version to a new version of the program without restarting would prevent this. This work investigates a “safe” manner to transfer executing threads with minimal backtracking or other compensating actions. (This problem has also been called dynamic software updating, hot swapping, and online upgrading.)
Quality of Service of Software Service Orchestrations
Collaboration with Albert Benveniste, Claude Jard, Ajay Kattepur, and Sidney Rosario of INRIA/IRISA, DistribCom group, Rennes, France.
Publication: , Albert; , Claude; , Ajay; , Sidney; , John A. QoS-Aware Management of Monotonic Service Orchestrations. Formal Methods in Systems Design. 2013; 44(1):1–43. ISSN 0925-9856. doi:10.1007/s10703-013-0191-7.
Abstract: We study QoS-aware management of service orchestrations, specifically for orchestrations having a data-dependent workflow. Our study supports multi-dimensional QoS. To capture uncertainty in performance and QoS, we provide support for probabilistic QoS. Under the above assumptions, orchestrations may be non-monotonic with respect to QoS, meaning that strictly improving the QoS of a service may strictly decrease the end-to-end QoS of the orchestration, an embarrassing feature for QoS-aware management. We study monotonicity and provide sufficient conditions for it. We then propose a comprehensive theory and methodology for monotonic orchestrations. Generic QoS composition rules are developed via a QoS Calculus, also capturing best service binding—service discovery, however, is not within the scope of this work.
Monotonicity provides the rationale for a contract-based approach to QoS-aware management. Although function and QoS cannot be separated in the design of complex orchestrations, we show that our framework supports separation of concerns by allowing the development of function and QoS separately and then “weaving” them together to derive the QoS-enhanced orchestration. Our approach is implemented on top of the Orc script language for specifying service orchestrations.
Small Projects (term projects)
Probabilistic Robot Control
Project report: Probabilistic Robot Action Planning/Control, Dec 2009. (PDF format, 119 kB)
Introduction: Robot behaviors are often designed using a set of states, with transition conditions among them, i.e. a finite state machine. The transition conditions often depend on uncertain inputs. Thus, transitions could fire incorrectly or fail to fire. This necessitates complicating the behavior design with additional transitions to “back out” of states judged to be erroneous.
Current robotic systems maintain probabilistic models of their environment. Deterministic state transitions are a mismatch for these models in that they require a single datum to be extracted from the probabilistic models to use as an input to the state transition decision. For example, a particle filter would be processed to produce a choice for “the” current robot pose to use as a basis for action decisions. In some sense, this “throws away” the advantages of tracking multiple hypotheses in the particle filter.
In this work, we seek to carry the probabilistic models into behavior decision making, insofar as it is possible. Clearly, a robot cannot choose to, for example, move to two different places at once, but not all decisions are mutually exclusive. For example, a robot could move its head to visually scan for objects while walking to a target location.
Secure Information Flow in the Orc Concurrent Programming Language.
Project report: Secure Information Flow in the Orc Concurrent Programming Language, Dec 2009. (PDF format, 240 kB)
Problem Statement: A secure information flow analysis of the Orc language, aimed at answering:
- What are the various channels that information could flow among expressions in Orc (by design and covertly), under standard Orc semantics?
- To what extent can an secure information flow policy be enforced in standard Orc with appropriate security extensions?
- How does concurrency change the secure information flow problem or solution, if at all?
- Can a policy be implemented reasonably that is more practical than strict noninterference?
- Beyond the pure Orc semantic model, are there aspects of the implementation of the Orc compiler or runtime engine that affect the information flows?
Isolation of Untrusted Application Installers
(Isolation from the rest of the system, using the Alcatraz/Etrace work at Stony Brook University as a basis.)
Project report: Total Installation Awareness, with Robert , Dec 2008. (PDF format, 602 kB)
Abstract: Users often install applications from untrusted sources. Alcatraz is a system that provides isolation of a system from potentially untrustworthy user programs. However, we find performance and functionality concerns with Alcatraz. Nevertheless, Alcatraz demonstrates the feasibility of one-way isolation of user programs. During a port of Alcatraz to a modern commodity operating system, Mac OS X, we observe that the various security goals present in such a system can be at odds with each other. This conflict impedes implementation of features such as isolation. We propose an alternative that preserves system adaptability properties while still serving the trusted platform needs of DRM. A substantially different approach to implementing one-way isolation appears feasible, and is left for future work.
Other Views on Research
R. Hamming's Bellcore talk You & Your Research [700 kB PDF].
