An Axiomatic Definition of Distributed Systems

CS 537 - Client-Server Interfaces, Spring 2002

Axiomatic Definitions

• An axiom is a statement assumed to be true.

• A set of axioms can define an entity.

  • Any entity for which all axioms hold.

• A set of axioms also allow for reasoning about entities.

  • Start from axioms and prove theorems.

• Example - Euclid's five axioms (postulates) for geometry.

  1. Unique lines through point pairs.

  2. Congruent segments.

  3. Unique circles through point pairs.

  4. Congruent right angles.

  5. Unique parallel lines.

  • Defines a Euclidean geometry (surprise!).

  • A line segment defines an equilateral triangle.

Process Control Systems

• Advanced Real-Time Languages for Distributed Industrial Process
  Control by Hartwig Steusloff, IEEE Computer, February, 1984.

• Process control systems

  • Distributed systems - shop floor monitoring and control.

  • Hard real-time systems.

  • Perhaps the oldest and most studied form of distributed computing.

• Rejects all (then) current programming languages.

  • Algol 68, PL/I, and Pascal.

  • Ada is ok.

• Defines a set of axioms for distributed systems.

Distributed System Axioms

axiom a - Multiple computations.

Several processes participate in the execution of system functions.

axiom b - Independent computations.

For any given process P, no other process exists that has exactly
the same view of the system state.

axiom c - Subsystem independence.

The architecture comprises separable units including a possibly
varying number of processing elements.

axiom d - Common communication channels.

Communication is achieved via message passing on a shared
communication structure (excluding unprotected memory).

axiom e - Global coordination.

Some system-wide control is performed to provide for dynamic
interprocess cooperation and runtime management.

axiom f - Unbounded, nonzero communication delay.

Interprocess message transit delays are variable, and some time
always exists between the production of an event by a process and
the materialization of this production at the destination process.

Comments

• Axiom b is the heart of the problem.

  • Common global state is expensive.

  • Good distributed design minimizes it.

• Axiom d is usually dropped or folded into axiom f.

• Axiom e is never true (it's cheating and non-scalable).

  • However, a global coordinator is a useful concept.

This page last modified on 7 February 2002.