# Scheduling computation

## Problem statement

State changes in decentralised applications have thus far either been fully serialised (when executed in a virtual machine on a blockchain network), or only have local state changes without global consensus over state changes.

Advanced computations can only realistically be executed on a parallel architecture with global orchestration of resources and recombination of local (intermediary) results into global answers.

Locality should be understood in these contexts as locality of operations. An operation is local if the operation can be performed on a subsection of the problem.

As a counter example, within Ethereum smart contract calls are not local under this definition, because the execution of a call can call on any arbitrary other smart contract in the global state of Ethereum. This design choice, combined with serial execution, allows Ethereum to solve both the double-spend problem and have powerful composable smart contracts.

### Solution approach

With Mosaic we look to build on the powerful protocols of Ethereum (global operations) and IPFS* (local operations), to construct a runtime environment within which applications can both execute local operations (in parallel) and coordinate over global state results and resources (incl. available nodes online to execute over).

Note: * IPFS is a foundational protocol which enables other protocols to construct local operations. In particular we will leverage ThreadsDB to construct local operations.

## Contract designs

### Engine

contract Engine {

    mapping(uint256 => Scope) scopes;
    
    Pool workerPool;
    mapping(uint256 => Ring) rings;

    function attachGate() {
        
    }
}

contract Reputation {
    
    function join() {
    
    }
    
    function logout() {
    
    }
}

### Users

Users can spot-check the computations done by the engine rings.

Users are represented by _string_ contracts.

### Scope and data ownership model

Data is declared on-chain by storing the 32 bytes of the IPLD Content Identifier (CID) (SHA256) that stores the data off-chain (on IPFS). (The multihash prefix - which exceeds 32 bytes - can be stored once per contract.)

The CID is written into a non-fungible token contract (NFT EIP721), so each data has an `address owner` and is assigned a unique `uint256 tokenId` within the scope of this NFT contract. We call such a contract a `Scope` contract.

Data can be declared as variable or constant. To differentiate between constant and variable data, we register constants with _even_ token identifiers and variables with _odd_ token identifiers.

By storing all data references as non-fungible tokens in a `Scope` contract, ownership is known. Rings are the owners of data, and the `Ring` contracts can be queried to obtain multiaddresses for fetching the associated data objects the data token references.

(Note: in the implementation `Scope is EIP1948`; `EIP1948 is EIP721`)

contract Scope is EIP721 {

    enum Mutability {
        ConstantData, // uint8 = 0
        VariableData  // uint8 = 1
    }
    
    bytes32 const DATA_DELETED = bytes32(0);
    // reference to engine to terminate scope
    address owningEngine;
    bytes multihashPrefix;    
    mapping(uint256 => bytes32) data;
    uint256[2] counter;

    constructor() {
        // skip over first tokenId as zero. 
        counter[0] = 1;
    }

    function declareData(
        bytes32 _data,
        Mutability _mutability
    )
        returns (uint256 tokenId_)
    {
        require(_mutability <= uint8(1),
            "Invalid data mutability");
        require(_data != DATA_DELETED,
            "Data cannot reference null.");
        // assign even tokenIds to constants;
        // assign odd tokenIds to variables;
        tokenId_ = 2 * counter[_mutability] + _mutability;
        counter[_mutability]++;
        tokenOwner[tokenId_] = msg.sender;
        data[tokenId_] = _data;
    }
    
    function readData(uint256 _tokenId) returns bytes32
    {
        require(_tokenId != uint256(0), "tokenId cannot be zero.");
        require(
            (_tokenId % 2 == 0 && _tokenId < counter[ConstantData]) ||
            (_tokenId % 2 == 1 && _tokenId < counter[VariableData]),
            "TokenId out of scope.");
        return data[_tokenId];
    }
    
    function writeData(
        uint256 _tokenId,
        bytes32 _newData
    ) {
        require(_tokenId != uint256(0), "tokenId cannot be zero.");
        require(_tokenId % 2 == 1,
            "Data is not mutable.");
        require(ownerOf(_tokenId) == msg.sender);
        require(data[_tokenId] != DATA_DELETED,
            "Data has been deleted.");
        emit DataUpdated(_tokenId, data[_tokenId], _newData);
        data[_tokenId] = _newData;
    }
    
    function deleteData(
        uint256 _tokenId
    ) {
        require(_tokenId != uint256(0), "tokenId cannot be zero.");
        require(data[_tokenId] != DATA_DELETED,
            "Data has already been deleted.");
        require(ownerOf(_tokenId) == msg.sender);
        delete data[_tokenId];
    }
    
    function closeScope()
    {
        require(msg.sender = owningEngine,
            "Only engine can close scope.");
    }
}

### Circuit

A gate is a contract that defines a computational step to be executed on a set of input data, and output into a set of results. A circuit is then a directed-acyclical graph (DAG) of such gate contracts. The links of the graph indicate the dependencies between the computational steps to be taken. The circuit can be constructed ahead of execution time.

One can think of this construction as programming with `futures`, where the `future` will unblock the execution step when all the input data (ie. output of preceding computations) have resolved. By laying out the future work nodes will need to do, nodes can always maintain a full work queue and avoid "starvation" ("Starvation of work", is where nodes are idling while waiting for data to be received. This is a major inefficiency when orchestrating large parallel work problems.)

### Gate

contract Gate {

    struct FuturePin {
        Gate gate;
        uint96 outputPin;
    }
    
    Scope scope;

    // Input and output pins on gates are represented as uint96
    // because futures must reference 20 bytes for an address if the gate
    // so the remaining 12 bytes (of the word length) can be used for
    // enumerating the output pins.

    // TokenId of data declared in the scope contract. Inputs must be constant.
    // The zero-th input pin has the convention to be used for programmatic input
    // defining the operation to be executed and the layout of input,
    // future and output pins.
    uint256[] inputPins;
    
    // Future pins resolve to output pins of a preceding gate.
    // This way we construct dependencies between gates, and the ring can continue
    // on the computational step when all future pins have resolved.
    FuturePin[] futurePins;
    
    // Output pins can be read by other gates or other components/contracts.
    // An output pin stores the tokenId of the resulting data computed.
    // Outputs must be constants, such that nodes can prefetch data and avoid starvation.
    uint256[] outputPins;
    
    // Track number of output pins set.
    uint96 nOutputPinsSet;

    // Ordered linked-list of primary and optional fall-back rings
    // the additionally assigned rings serve for fault-tolerance
    mapping(Ring => Ring) assignedRings;
    
    Ring primaryRing;
    
    modifier onlyRing {
        require(
            msg.sender == primaryRing ||
            ( primaryRing == Ring(0) && isRing(msg.sender) )
        );
        
        _;
    }

    constructor(
        Ring[] _assignedRings,
        uint256[] _inputPins,
        Gate[] _futureGates,
        uint96[] _futureOutputPins,
        uint256 _nOutputs
    ) {
        require(_assignedRings.length > 0);
        require(_futureGates.length == _futureOutputPins.length);
        require(_assignedRings[0] != address(0));
        assignedRings = _assignedRings;
        primaryRing = _assignedRings[0];
        
        inputPins = _inputPins;
        outputPins = new uint256[](_nOutputs);
        futurePins = new FuturePin[](_futureGates.length());
        for (uint256 i = 0; i < _futureGates.length; i++) {
            futurePins[i] = FuturePin(_futureGates[i], _futureOutputPins[i]);
        }
    }
    
    // Ring::resovle{
    //   
    //   BLS / separately report signatures -> (pin, CID)
    //   t = Scope.declareData(CID, ConstantData);
    //   Gate.output(pin, t);
    // }
    function output(uint96[] _pins, uint256[] _tokenIds)
        external
        onlyRing
    {
        require(!gateHasResolved());
        require(_pins.length == _tokenIds.length);

        // indicate to other assigned rings that we're on the job
        if (primaryRing == Ring(0)) {
            primaryRing = msg.sender;
        }
        
        for (uint i = 0; i < _pins.length; i++) {
            require(_tokenIds[i] != uint256(0));
            require(_pins[i] < outputPins.length);
            require(_tokenIds[i] % 2 == 0, "TokenId must reference a constant.");
            nOutputPinsSet = nOutputPinsSet + uint256(outputPins[_pin] == 0);
            outputPins[_pins[i]] = _tokenIds[i];
            emit Output(address(this), msg.sender, _pin, _tokenId);
        }

        if (nOutputPinsSet >= outputPins.length) {
            emit GateResolved(address(this));
        }
    }

    function challengePrimaryRing() external {
        require(!gateHasBeenResolved());
    
        checkAllFuturesHaveResolved();

        challengedBlockNumber = block.number;
    }
    
    openFloodgate() external {
        require(challengedBlockNumber > 0);
        require(challengedBlockNumber + CHALLENGE_TIMEOUT < block.number);
        require(!gateHasBeenResolved());
        
        removeRing(primaryRing);
        primaryRing = Ring(0);
        challengedBlockNumber = 0;
    }

    function appendRing(Ring _newRing)
        external
        onlyEngine
    {
        rings[_newRing] = rings[SENTINEL_RINGS];
        rings[SENTINEL_RINGS] = _newRing;
    }
    
    
    function removeRing(Ring _ring)
        internal
    {
        ..
    }
    
    function gateHasBeenResolved() internal {
        return (nOutputPinsSet >= outputPins.length)
    }
}

### Procedural Compiler

## Archive notes

### Master

contract Master {

    /* Storage */
    
    address engine;

    mapping(address => address) assignedMapRings;
    mapping(address => address) assignedReduceRings;
    
    bytes32[] resultCIDs;
    
    
    /* External Functions */
    
    constructor(
        address engine,
        bytes32 mapAppDockerCID,
        bytes32 reduceAppDockerCID,
        bytes32[] mapInputCIDs
    ) external;
    
    
    function registerMapResult(bytes32 _resultCID) onlyMapRing external;
    
    function registerReduceResult(bytes32 _resultCID) onlyReduceRing external;
    
    
    /* Internal Functions */
    
    function runMapJob() returns (address assignedMapRing_) internal;
    
    function runReduceJob() returns (address assignedReduceRing_) internal;
}

## random reference