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:

• the cost of deploying large sensor and effector networks will be greatly reduced;
• the computational and communication costs of run-time management of such networks will be greatly reduced;
• the networks will be able to operate more effectively due to improved resource management;
• they will be able to tolerate dramatically varying loads;
• their robustness against resource failure will be enhanced.

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.