Contract Net Protocol: a distributed problem solver framework

Overview

The Contract Net approach was introduced by Reid G. Smith in the 70s, as a means to distribute the resolution of a problem between multiple nodes (in this example, we can think of a node as a computer on a network). This framework is best suited when there are multiple nodes cooperating to solve a difficult task, and no individual node has the knowledge to solve the task by itself. The basis to understand this mechanism is that it functions as an auction.

Step one: task announcement

A node on the network must start with a task that needs to be solved (we’ll call this node “the manager”). It communicates with other nodes to announce the task.

Reid G. Smith and Randall Davis (1981)

Step two: bidding

The other nodes on the network will bid on the task. The bid value must be the cost that it will take to solve the task. This cost will be related to the node’s local knowledge, resources, and processing power. A node may abstain from bidding if it can’t solve the task.

Reid G. Smith and Randall Davis (1981)

Step three: contract award

The manager will receive the bids and award the node with the best bid with the contract. Upon receiving the contract, the contractor can, for instance, subdivide the task and create new auctions for them. If a contractor node fails, the manager may re-announce the task.

Reid G. Smith and Randall Davis (1981)

Example: distributed area monitoring

In this example, the system monitors vehicles moving inside a given area:

An initiator node subdivides the area into subareas, and for each subarea, goes through the bidding process to find a contractor to monitor it. The contractors will report the results to the area manager.

Each subarea contractor creates more contracts for tasks to get data from sensors. The manager should avoid overlapping and maximize coverage. If a sensor fails, the subarea contractor may create new tasks to fill the coverage gap.

Each sensor contractor will send to the subarea contractor information about any new vehicles that they detect, or movement on existing vehicles on that sensor’s range.

If a new vehicle is detected on this subarea, the manager creates a new task for monitoring this vehicle and forwards the data. If the vehicle moves inside the area, the manager forwards the data to the existing contractor that is monitoring this vehicle.

Conclusion

This framework is easy to grasp, but there are many details left out and complications that arise from the implementation of such a system. If you’re interested in learning more, I recommend starting with this paper:

Reid G. Smith; Randall Davis. (January 1981). Frameworks for Cooperation in Distributed Problem Solving.

About the author

Gabriel Allegretti is a software developer at Poatek. He studies Computer Science at the Federal University of Rio Grande do Sul. He works on the frontend and backend for web applications, as well as native Android development. On his spare time, he likes to make video games, play guitar and take his dog for a walk.