module arch.node.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 network-accessible 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

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.