Consona constraint Networks for the Synthesis of Networked Applications Lambert Meertens

CONSONA Constraint Networks for the Synthesis of Networked Applications

• Lambert Meertens

• Cordell Green

• Kestrel Institute

Administrative

Subcontractors and Collaborators

• Subcontractors

• none

• Collaborators

• none

Consona Constraint Networks for the Synthesis of Networked Applications

Project Objective

• The Consona project aims at developing truly scalable fine-grain fusion of physical and information processes in large ensembles of networked nodes

• ‘‘Truly scalable’’ means that — at least conceptually — the networked system can be viewed as a discrete approximation of computation on a continuous field

• Large-scale fine-grain systems have many potentially serious bottlenecks, and the design process must allow exploring trade-offs

NEST needs New Methods

• For NEST we need model-based methods and tools that

• integrate design and code generation
• design-time performance trade-offs
• of NEST applications and services
•  cross-layer fusion; low composition overhead
• in a goal-oriented way
•  goal-oriented run-time performance trade-offs

Why Middleware?

• Current Software Technology approaches to Middleware aim at creating abstractions that hide the ‘‘imperfections’’ of a physical system

• Such abstractions are indispensable to keep system design intellectually manageable,

• but threaten to hide the very thing that we need for exploring design-time trade-offs

Perfection is Unattainable

• In a NEST system all guarantees are probabilistic: nodes may go dead, messaging may be subject to serious interference, …

• Sensor readings are subject to noise; actuator settings differ from the effects

• While the network is maintaining abstractions, the outside world changes and information gathered becomes obsolete

• A late result may be as useless as no result

• Timeliness (or other resource-related criteria) may be more important than precision

Tunable Middleware Services

• In the NEST context, a ‘‘Middleware Service’’ is an idiom (e.g., Distributed Constraint Optimization or Sense-Fuse-Disseminate), expressing a (quantifiably) imperfect but nevertheless useful abstraction, typically realizable in a variety of ways

• For NEST we need Middleware Services that are tunable to desired quality-cost profiles, customizable to application-specific aspects, and specializable to the actual capabilities used

Scalable Middleware Services

• NEST Middleware Services are represented by agents that are replicated throughout the network (i.e., the code is replicated, not the state)

• Such agents are typically lodged on groups of nearby nodes, and the agent-node assignment is typically dynamic

• A Middleware Service is an anytime thing

Contributions to NEST Program

• Generation of Middleware Services that achieve useful global behavior using scalable local methods

• Laying out ground rules for techniques that can be extended to extremely large network

• (Future:) Tool for cross-layer optimizing code composition and generation for combined Application and Middleware Services

Success Criteria

• Applications that use synthesized middleware code and scale to arbitrarily large networks

• Applications that use synthesized middleware code and run as well as with hand-crafted code (e.g. speed, communication cost, tracking accuracy)

• Complexity of middleware services that can be generated (e.g. measured in the complexity of the constraints)

Overview of Technical Approach

• Services and applications are both modeled as logical formulas, expressing soft constraints to be maintained at run-time

• High-level code is produced by repeated instantiation of constraint-maintenance schemas

• Constraint-maintenance schemas are represented as triples (C, M, S), meaning that
• provided that ancillary constraints S are maintained, executing code M maintains constraint C

• High-level code is optimized to generate efficient low-level code

Project Progress

• Demo: Making the Boeing OEP CP Distributed

• implemented Distributed Group Formation Service
• designed and implemented Distributed Assignment Service
• designed and implemented Distributed Actuator Control

• Modeler (Constraint Refinement System)

• designed a prototype; implemented alpha version

Distributed Boeing OEP CP Services

• The Boeing OEP Challenge Problem is concerned with active control for vibration damping in a rocket fairing

Distributed Boeing OEP CP Control

• Designed and implemented a distributed algorithm for control of vibration damping, strongly reducing the vibrational energy

• Algorithm is based on purely local sensor readings and actuator control

Prototype Modeler

• Alpha version

• Basic capabilities:

• multiset matching & instantiation
• automatic filtering for applicable schemas
• history mechanism; unlimited undo

• Not implemented:

• domain-level simplification (such as n = 0 V n > 0  true )
• version tree
• library browser

Publications and Milestones

• Publications

• Specifying Components for NEST Applications. Asuman Sünbül. The Sixth Biennial World Conference on Integrated Design & Process Technology, H. Ehrig, B.J. Krämer & A. Ertaş (Eds.)
• Scalable, Anytime Constraint Optimization through Iterated, Peer-to-Peer Interaction in Sparsely-Connected Networks. Stephen Fitzpatrick & Lambert Meertens. The Sixth Biennial World Conference on Integrated Design & Process Technology, H. Ehrig, B.J. Krämer & A. Ertaş (Eds.)
• Asynchronous Execution and Communication Latency in Distributed Constraint Optimization. Lambert Meertens & Stephen Fitzpatrick. The Third International Workshop on Distributed Constraint Reasoning, pp. 80-85, Makoto Yokoo (Ed.)
• Experiments on Dense Graphs with a Stochastic, Peer-to-Peer Colorer. Stephen Fitzpatrick & Lambert Meertens. Probabilistic Approaches in Search, pp. 24-28, Carla Gomes & Toby Walsh (Eds.)
• Towards Component-based Systems: Refining Connectors. Mathias Anlauff & Asuman Sünbül. Proc. Refine 2002, Electronic Notes in Theoretical Computer Science, 2002

• Milestones

• October 2002: design of Prototype Modeler
• January 2003: implementation of Prototype Modeler (alpha version)
• January 2003: demonstration on Boeing OEP

Goals and Success Criteria

• Measures of success:

• flexibility of combining components
• dynamic adaptivity
• run-time efficiency
• correctness & maintainability of generated applications

• Metrics:

• run-time resource utilization
• complexity of specification vs. code
• number of critical errors (that cause failure)

OEP Participation

• Berkeley OEP

• Midterm Demo:
• distributed resource allocation
• data diffusion
• distributed tracking
• Kestrel POC: Lambert Meertens
• Berkeley POC: David Culler

• Boeing OEP

• Demo (past contributions):
• distributed group formation & constraint service
• distributed control
• Kestrel POC: Lambert Meertens
• Boeing POC: Kirby Keller

Project Plans

• Develop Prototype Code Generator

• Work on Berkeley OEP Midterm Demo:

• Adapt existing services and tools to nesC
• Identify middleware services that can be synthesized
• Use modeler/generator to produce code

• Specific performance goals:

• code gets generated and runs

• Progress will be measured and success determined by verifying that code gets generated and runs

Project Schedule and Milestones

• Modeling using constraints: achieved

• Toolset: preliminary design – done, informal

• Alpha version prototype modeling toolset: done

• Prototype modeling toolset: March 2003

• Prototype code generator: June 2003

Technology Transition/Transfer

• Technology transition activities identified: currently none

Program Issues

• Two recurrent themes:

• high-level coding paradigms for mote-like systems
• approximate solution techniques

• It would be a worthwhile program achievement to draw out the common ideas