The Internet Computer for Computer Scientists

To a first approximation, the IC (Internet Computer) is a network of replicated state machines.

Each replicated state machine comprises a subnet of replicas. Subnets may communicate with one another, but otherwise they operate (for the most part) independently of each other.

As in any replicated state machine, a series of transaction requests is processed. A transaction request may come from either an external client or from another state machine in the IC. The replicas in a subnet must run a consensus protocol to order the incoming transaction requests, so that each replica processes the transaction requests in the same order. Each replica processes the transaction requests in the agreed-upon order. In processing a transaction request, each replica will update its internal state according to a deterministic function that maps the pair (current state, transaction request) to a new state. Because all replicas in a subnet process transaction requests in the same order, their internal states will evolve over time in exactly the same way. In response to processing a transaction, a subnet may also generate an outgoing message, which can be sent to either an external client or to another state machine in the IC.

The reason for using a replicated state machine, rather than just a single state machine, is to achieve fault tolerance: a subnet should continue functioning correctly even if some replicas are faulty. Generally in this area, one considers two types of replica failures: crash failure and Byzantine failures. A crash failure occurs when a replica abruptly stops and does not resume. Byzantine failures are failures in which a replica may deviate in an arbitrary way from its prescribed protocol. Moreover, with Byzantine failures, one or possibly several replicas may be directly under the control of a malicious adversary. Of the two types of failures, Byzantine failures are potentially far more disruptive.

Protocols for consensus and for implementing replicated state machines typically make assumptions about how many replicas may be faulty and to to what degree (crash or Byzantine) they may be faulty. In the IC, the assumption is that if a given subnet has [math]\displaystyle{ n }[/math] replicas, then less than [math]\displaystyle{ n/3 }[/math] of these replicas are faulty and these faults may be Byzantine. (Note that the different subnets in the IC may have different sizes.)

Protocols for consensus and for implementing replicated state machines also typically make assumptions about the reliability communications network.