e-Merge-ANT

Distributed, Real-Time Allocation of
Loosely-Coupled, Critically-Loaded Resources

Stephen Fitzpatrick, Cordell Green & Lambert Meertens
Kestrel Institute

Sponsor: DARPA/IXO ANTS*
Contractual & technical support: AFRL


This project wrapped up in 2004. Kestrel's research on distributed constraint algorithms and sensor networks continues in it's CONSONA project. This web site will not be further maintained, but please feel free to contact Stephen Fitzpatrick (fitzpatrick at kestrel.edu) if you have inquiries.


In Brief

The Problem: Large sensor and effector networks are subject to high communication latencies and dramatically varying loads that can wreak havoc on conventional resource management techniques and undermine a network's ability to service tasks that have stringent real-time requirements.

Our approach: We will build on our experience in specification & synthesis technology and in scheduling algorithms to develop efficient, time-sensitive, decentralized schedulers and to make these available for rapid deployment.

The Payoff:


At Length

Background: distributed resource networks
Motivation and technical challenges.
Our general approach
Distributed, real-time resource management through decentralized, anytime, local-repair scheduling.
Challenge problem
Details of the ANTS challenge problem (a network of simple radar sensors) and our approach to it.
Soft Graph Coloring
Soft graph coloring is an abstraction of resource allocation for distributed, real-time systems.

Further Information

Presentations
A selection of presentations.
Publications
Scheduling Background
Background information on scheduling. Includes a glossary, formal specifications of scheduling sorts and operators and an informal discussion of classes of scheduling algorithms.
Project web site
Containing such information as project status reports.
Other sources of information
Links to other sites with information on real-time systems and anytime algorithms.

* The views and conclusions expressed on this web site are occasionally those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the U.S. Government.