Difference between revisions of "The Internet Computer for Computer Scientists"

From Internet Computer Wiki
Jump to: navigation, search
Line 20: Line 20:
  
 
The reason for using a replicated state machine, rather than just a single state machine,
 
The reason for using a replicated state machine, rather than just a single state machine,
is to achieve [[wikipedia:fault tolerance|fault tolerance]].
+
is to achieve [[wikipedia:fault tolerance|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: <b>crash failure</b> and <b>Byzantine failures</b>.
 +
A <b>crash failure</b> occurs when a replica abruptly stops and does not resume. <b>Byzantine failures</b> 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.

Revision as of 15:29, 5 October 2021

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.