Introduction
In the late 1970s, the evolution of Large Scale Integration (LSI) technology suggested a future where computing would be handled by hundreds or thousands of interconnected microprocessors. However, managing these "loosely-coupled" networks presented a significant software challenge. Traditional centralized control models created bottlenecks and single points of failure, which were antithetical to the goals of distributed computing. Reid G. Smith’s "Contract Net" emerged as a pioneering framework to address these challenges, proposing a decentralized approach to coordinate "expert" nodes through a market-inspired mechanism.
The Problem of Distributed Control
The primary objective of the Contract Net was to enable effective cooperation among nodes while relying primarily on local information. Smith sought to achieve "coarse-grained parallelism"—a state where nodes perform substantial local computation and communicate only occasionally for coordination. This approach aimed to maintain system flexibility and reliability without the overhead or vulnerability of a central controller.
The Contract Net Protocol
The formalism treats individual nodes as autonomous "experts" that interact through a structured negotiation protocol. The process follows a distinct lifecycle:
- Contract Announcement: A node requiring assistance (the Manager) broadcasts a task description to the network.
- Bidding: Other nodes (Potential Contractors) evaluate the task against their current state and specialized expertise. If they have the capacity and skills, they submit a bid.
- Awarding: The Manager evaluates the bids and selects the most suitable node, formalizing the contract.
- Execution and Subcontracting: The Contractor executes the task. If the task is complex, the Contractor may act as a Manager, breaking the task down and issuing further subcontracts to other nodes.
- Reporting: Upon completion, the Contractor transmits the results back to the Manager.
Crucially, roles are fluid; a node can simultaneously act as a Manager for one task and a Contractor for another, allowing the network to adapt dynamically to changing workloads.
Key Architectural Insights
The Contract Net introduces several key concepts that have since become foundational in distributed systems:
- The Market Metaphor: By applying economic principles like bidding and contracting to resource allocation, the system enables "opportunistic" problem-solving. Tasks are naturally routed to the most capable and available resources at any given time.
- Fault Tolerance by Design: The system is inherently resilient. If a contractor fails, the manager can simply re-announce the contract to find a replacement. The absence of a central controller ensures that the failure of a single node does not compromise the entire network.
- Knowledge-Based Communication: To reduce network congestion, announcements can be targeted. If a manager possesses information about which nodes hold specific data or expertise, it can utilize limited broadcasts or point-to-point messaging rather than flooding the entire network.
Evaluation via Simulation
As an architectural proposal, the Contract Net was evaluated using a SAIL (Stanford Artificial Intelligence Language) simulation. This environment mapped simple application programs onto a simulated distributed processor with a variable number of nodes. The simulation helped quantify the trade-offs between communication overhead (the cost of negotiation) and the speedup gained through parallelism.
A notable finding was the concept of software persistence. Nodes that received specific software to fulfill a contract could "cache" that expertise locally. This made them more competitive for similar future contracts, leading to the natural emergence of specialized nodes within the network over time.
Conclusion and Limitations
The Contract Net is most effective for coarse-grained tasks, where the computational effort significantly outweighs the communication costs of the bidding process. For very small tasks, the overhead of negotiation can become a bottleneck. Despite this limitation, the framework provided a robust foundation for distributed heuristic search and deduction, moving the field of AI toward decentralized, market-based models of intelligence.
Summary updated