This project develops the Propagator Model, a concurrent decentralized framework designed to support computing in large, open, dynamic environments. It provides powerful tools for organizing computations to operate effectively in a world of rapidly changing and globally inconsistent data by adopting a fundamental shift in viewpoint: the things manipulated by basic computing elements are not fixed values. Rather, they are information about values, and this information is continually refined as new information becomes available.
This project creates the architectural and linguistic foundations for systems that can operate effectively in environments where there is no central management, and where one cannot rely on resources being consistently available or consistently operating, and where the data is rapidly changing and globally inconsistent. Using three mechanisms implicit in the computational substrate: (1) constraint propagation, (2) partial information structures, and (3) dependencies, systems built on the propagator model automatically have the ability to support their conclusions with arguments and report on the provenance of the ingredients. They can automatically discover and use consistent subsystems of inconsistent data.
This project erects a naturally concurrent and distributed model and infrastructure for computation that makes it easier to build systems that are reliable in the face of natural failures and deliberate attacks. It provides support for auditable and accountable systems that are robust and adaptable to novel applications.
Goal: The aim of this project was to develop the Propagator Model, a concurrent decentralized framework designed to support computing in large, open, dynamic environments. It provides powerful tools for organizing computations to operate effectively in a world of rapidly changing and globally inconsistent data by adopting a fundamental shift in viewpoint: the things manipulated by basic computing elements are not fixed values. Rather, they are information about values, and this information is continually refined as new information becomes available. This project develops architectural and linguistic foundations for systems that can operate effectively in environments where there is no central management, and where one cannot rely on resources being consistently available or consistently operated, and where the data is rapidly changing and globally inconsistent. Using three mechanisms implicit in the computational substrate: (1) constraint propagation, (2) partial information structures, and (3) dependencies, systems built on the propagator model automatically have the ability to support their conclusions with arguments and report on the provenance of the ingredients. They can automatically discover and use consistent subsystems of inconsistent data. This project erects a naturally concurrent and distributed model and infrastructure for computation that makes it easier to build systems that are reliable in the face of natural failure and deliberate attack. It provides support for auditable and accountable systems that are robust and adaptable to novel applications. Accomplishments: Graduate student Micah Brodsky designed and built a prototype Remote Procedure Call protocol. Micah Brodsky and P.I. Gerald Jay Sussman have employed Brodksy's RPC mechanism to extend our propagator system to allow multiple independent propagator processes collaborate on solving a problem. Using this mechanism we have made it possible for a propagator network to be shared among multiple processes, so that each process is in charge of updating cells and maintaining consistency in its own subnetwork. Brodsky and Sussman have implemented mechanisms for supporting multiple agents that can access and query a shared propagator network. Each agent has its own worldview: the set of premises believed or tentatively assumend. So multiple agents can use the same knowledge base, but have mutually inconsistent assumptions and beliefs. An agent may employ this freedom to be "of two minds" about some subset of its beliefs. Distributed propagators have distributed state. We have made headway along two different avenues into the problem of mutable state management, a weak point for both pure functional languages and propagators, and a bottleneck for distributed propagators. Micah Brodsky and Pavel Panchekha (an undergraduate student) have invented a novel mechanism for maintenance of distributed shared state that they call a "History Maintenance System," a generalization of the notion of a transaction log. The idea is an extension of the well-known operational transform technique used in version-control systems for text documents. Their idea extends the work to arbitrary data and it ensures eventual consistency, without deadlock, even in the face of transient communication failures. They have demonstrated their idea in the context of a simple shared file system. The propagator system's support for contingent facts and multiple worldviews allows logical mutation via worldview changes on natively immutable or monotonic primitive data types. So, based on new information, old values contingent on hypothetical assumptions can be kicked out and replaced with new values contingent on new, dynamically generated hypotheses. Graduate student Ian Jacobi and Gerald Jay Sussman have constructed a mechanism to integrate the control of program flow in a dynamic fashion, taking into account the need to support multiple world-views and appropriate backtracking. We have prepared five problems requiring various tasks for their solution, including risk accumulation from multiple sources and controlling the evaluation of recursive rules. We have built reusable abstract problem-solving mechanisms for solving these problems, such as divide-and-conquer and value accumulation mechanisms. We have identified several modifications needed of the propagator mechanism to support several other problem solving approaches, including proof by contradiction. This work culminated in an Engineer in Computer Science thesis for Mr. Jacobi. Micah Brodsky's now complete PhD thesis applied the propagator model to elucidate some parts of the process of developmental patterning and construction of geometric structures in embryos. Constraint propagation proved to be a surprisingly apt language for expressing problems in distributed patterning. Patterns are built in stages. Sometimes it is important for one stage to be complete before the next stage starts. Brodsky developed a self-timing strategy that expresses pattern computations in the form of hard, local, quasi-acyclic constraints. A little bit of cleverness is needed to ensure that the system is neither under-constrained nor over-constrained and will converge by propagation alone. When the set of possible values for a node narrows down to a single definite result we have convergence. On the other hand topological constraints, that enforce the correct connectedness of a system, are built on the biological rule of normal neighbors. This is modeled by the propagation of soft local constraints, without the restriction of monotonicity in the cell contents. One of the virtues of constraint propagation is the ability to run a computation in many different directions, exchanging inputs for outputs. This allows hints to be derived from any number of sources (reminiscent of the myriad hints that can be used to cajole stem cells to differentiate) and supporting regeneration of a partially destroyed pattern.
