Foundations

A proof assistant checks that a term establishes a formal proposition under declared axioms and kernel rules.

A relation is a set of tuples over a schema.

A candidate key is a minimal attribute set uniquely identifying a tuple; a superkey need not be minimal.

A transaction groups operations with atomic commit or abort.

PostgreSQL 18 repeatable read uses snapshot isolation: each transaction reads a stable snapshot, but concurrent writes to different rows can produce write skew and a nonserializable joint outcome.

An operational semantics defines a transition relation between program configurations, including state when needed.

For the declared simply typed language, progress says a closed well-typed term is a value or can take a step; preservation says evaluation retains its type.

Sequential consistency presents operations in one order preserving each thread's program order.

CompCert's principal semantic-preservation theorem relates accepted C abstract syntax to generated assembly abstract syntax: generated behavior refines permitted source behavior under the theorem's hypotheses.

The official CompCert 3.18 release in August 2026 revises formal handling of alignment/free and adds Rocq 9.2 support.

Crash faults stop a process; Byzantine faults permit arbitrary behavior, including inconsistent messages.

Fischer, Lynch and Paterson prove that a deterministic consensus protocol in their fully asynchronous message-passing model can have an admissible nondeciding run with at most one crash.

Raft uses term-numbered leader election, majority voting and log matching to replicate a state machine under crash faults.

A linearizable object admits a sequential explanation in which each completed operation appears to take effect between invocation and response, preserving real-time precedence of nonoverlapping operations.

In Gilbert and Lynch's asynchronous read/write model, an implementation cannot provide both atomic consistency and a terminating response to every request at every nonfailed node during arbitrary partitions.

In the synchronous oral-message Byzantine-generals model, agreement with at most f faulty participants requires at least 3f+1 participants, with identifiable senders and reliable delivery but no unforgeable transferred signature chain.

UTF-8 encodes scalar values with a variable number of octets.

Text equality and character counts depend on the declared representation and convention.

A combinational output depends on current valid inputs after a bounded settling delay.

Logic gates compute Boolean functions with truth values 0 and 1.

Sequential circuits retain state, so current inputs alone do not determine their behavior.

Stored instructions control computation through a specified hardware/software interface.

Names refer to values through an execution environment.

Selection and repetition determine which program statements execute.

A call connects arguments with local parameter bindings.

Self-calls reduce a problem toward a terminating case.

Types describe values and permitted operations; checks occur at different stages.

An operating system manages a program's execution as a process.

A process's address view is distinct from physical memory placement.

File contents, directory names and durable storage have distinct roles.