module node_architecture.engines.compute;
Compute¶

Inputs
 Computational searches to perform

Outputs
 Results of computational searches

Preferences
 Who to delegate computational search to

Accounting
 Computational searches actually performed, time taken
The compute engine is responsible for performing expensive computation, i.e. searching for witnesses to predicates which are (in general) in the complexity class NP. Frequently, however, more efficient search algorithms will be known for particular predicates. The compute engine is designed so that local and networkaccessible compute resources may be automatically balanced between based on costs and trust assumptions.
State¶
The compute engine keeps in state:

A local cache of solutions satisfying particular predicates

A local cache of algorithms to use to solve particular predicates
type ComputeEngineState := mkComputeEngineState {};
Input messages¶
Input messages to the compute engine specify:

A predicate (by hash) which a valid solution must satisfy

An optional algorithm (by hash) to use in searching

A maximum search cost in time and space usage (after which the compute engine will stop searching), including precision requested
Todo
Figure exact units for time and space bounds.
axiom Hash : Type;
axiom Option : Type > Type;
axiom Integer : Type;
axiom Rational : Type;
axiom Pair : Type > Type > Type;
type ComputeRequest :=
mkComputeRequest {
predicate : Hash;
algorithm : Option Hash;
max_cost_time : Pair Integer Rational;
max_cost_space : Pair Integer Rational
};
Output messages¶
Output messages from the compute engine specify:

The predicate (by hash)

The algorithm used, if specific (by hash)

The solution found, if one was found (by hash)

Cost (in time and space) actually incurred, and precision of cost estimates
type ComputeResult :=
mkComputeResult {
predicate : Hash;
algorithm : Option Hash;
solution : Option Hash;
actual_cost_time : Pair Integer Rational;
actual_cost_space : Pair Integer Rational
};
Internal accounting¶
The compute engine internally tracks available resources (time and space) available.
Todo
 Queue compute requests (perhaps priority queue) to avoid overloading available resources
 Define some message types for querying available resources
 Think about boundaries of networked compute abstraction layer vs local compute abstraction layer