$Id$

Why Order Matters:
Turing Equivalence
in
Automated Systems Administration

Steve Traugott -- http://www.stevegt.com
Lance Brown -- labrown@nc.rr.com

Abstract

Self-administering hosts are in effect Turing machines; they do brain surgery on themselves. They don't behave according to strict state machine rules, but incorporate complex feedback loops, evolutionary recursion, and self-modifying code.

No language or tool can reliably administer a machine without also tracking complete change history and specifying the order of changes still to be made.

This is because the behavior of the interpreter or compiler for any language or tool is itself dependent on the current disk contents, because the interpreter/compiler executes in the context of the current disk.

Using a change management tool to detect current disk content and act accordingly is problematic for that reason. Also, sampling subsets of disk content to determine current state is non-reentrant.

It appears that any method which uses cradle-to-grave deterministic ordering of all changes made to managed portions of a disk, without sampling any managed portion of that disk, would overcome these problems.

Overview

At LISA '01, much debate erupted, starting in Mark Burgess' cfengine workshop and continuing through the week, around the question of whether strict ordering of administrative actions is important.

This question has important implications for our industry. The answer will guide our actions as well as our effectiveness for decades to come.

Those of us who practice deterministic ordering, and those of us who do not, will quite literally work against each other if administering the same set of machines.

The Issue

There seem to be roughly two schools of thought on this topic:
Order doesn't matter
An automated administration tool utilizing a sufficiently descriptive language will be able to detect the current disk state through sampling a subset of the disk, and take the correct action in all cases. Reproducible change order is not required.
Order matters
It is not possible to forecast and code for all possible machine states; if there are N bits on a disk, then there are 2^N possible disk states. Sampling is deceptive; a 100k sample cannot determine the state of a 2Gb disk. The only method of creating reproducible change is to deterministically order the changes made to a disk. Reproducible change is required in order to validate a build or an enterprise-wide update.

Automated systems administration is very straightforward. There is only one way to change the contents of disk or RAM in a running UNIX machine -- the syscall interface. The task of automated administration is simply to make sure that each machine's kernel gets the right system calls, in the right order, to make it be the machine you want it to be.

The Problem Domain

Our primary driver is the need to avoid unpredictable behavior when automating the administration of mission-critical, usually commercial, enterprise infrastructures.

We require administration techniques which don't call for periodic rebuilds of production hosts or testing in production. We require techniques which allow no divergence other than that caused by security breaches.

We require administration techniques which require no extraordinary talents on the part of the administrators. An Intermediate level systems administrator [sage] must be able to learn these techniques via only several hours's training.

We expect some change actions which can be performed while machines are live, and others which can only be done at reboot.

We expect to use these techniques to manage machines over their entire life, from initial install until retirement.

A Quick Turing Review

A Turing machine has a ruleset which cannot be changed, and a tape which does change. The tape is a bitstream which contains instructions which are evaluated according to the ruleset. Results are written back to the same tape.

A Turing machine overwrites its executable instructions with new instructions as it executes, eventually reaching the desired end state.

Due to the monotonic process of overwriting the instructions themselves, a Turing machine's tape state must be assumed to be non-reversible without an external reset.

Brown/Traugott Turing Equivalence

Self-administering hosts are in practice complex Turing machines. They do brain surgery on themselves. They must be very careful when doing this.
  1. We still often think of Von-Neumann behavior in terms of inputs and outputs, such as punched cards and paper tape -- write-once media.
  2. The fact that Von-Neumann machines gained rewriteable non-volatile storage in recent decades is often overlooked in terms of administrative behavior.
  3. Self-administering Von-Neumann machines, with operating systems loaded from rewriteable disks, incorporate a complex feedback loop, with self-modifying code and recursive behavior which can evolve during each recursion -- elements of a Turing machine.
  4. The hardware and firmware of a conventional Von-Neumann machine correspond to the unchanging ruleset of a Turing machine. (For the purposes of this discussion we will ignore upgradeable firmware and microcode.)
  5. The disk of a conventional Von-Neumann machine corresponds to the tape of a turing machine.
  6. As a Von-Neumann machine executes the code found on disk, it typically changes the content of the same disk, but in most cases, these changes are restricted to user and business data, logs, and such. Executable code is not altered during non-administrative operations.
  7. But when we do system administration, we cause the machine to change the executable portions of its own disk, like the tape of a Turing machine. We also change the configuration files which control the fundamental behavior and viability of those same executables.
  8. When we do administration via automated means, we rely on the executable portions of disk, controlled by their configuration files, to rewrite those same executables and configuration files. Like the Turing machine, changes made in this manner must be assumed to be non-reversible short of "resetting the tape state" by reformatting the disk.
  9. As a self-administering Von-Neumann machine changes its disk contents, it changes its ability to change its disk contents. A change directive which works now may not work in the same way on the same machine in the future and vice versa.

Implications for Automated Administration

Each host in an infrastructure must, over the course of its entire life, follow an ordered, contiguous procedure which is validated elsewhere and is known to work. Failing to do this will result in unpredictable and divergent behavior.

Due to the stateful, Turing-like behavior of a Von-Neumann machine with a disk drive, a given version of configuration file, executable, or shared library cannot be depended on to work correctly in all stages in the lifecycle of a machine. You need to use the right version for the current state of the machine. This is common sense for most systems administrators.

The implications for self-administering machines are not as obvious:

  1. Change management tools used by self-administering machines run in the context of the host kernel and configuration files, and depend either directly or indirectly on other executables and shared libraries on the host's disk. This dependency tree forces us to assume that, even though we may not ever change the change management tool itself, we can unintentionally change its behavior if we change other components of the operating system.
  2. Therefore, there is no "sufficiently descriptive language" which can describe the desired state of a disk while neglecting history. This is not a language problem: The behavior of the language interpreter or compiler itself is subject to current disk state.
  3. The entire past history of changes to a machine, and the ordering of future changes, is significant. This is particularly important if we expect deterministic, reliable behavior in operation and repeatable rebuilds for disaster recovery.
  4. If we allow the order of changes to be A,B,C on some hosts, and A,C,B on others, then we must test both versions of the resulting hosts, rather than one, due to possible unforeseen interactions between changes. Worse, due to the risk of unforeseen interactions we must also test both versions of hosts for all future changes as well, regardless of ordering of those future changes. The hosts have diverged.
  5. If we were to allow the order of changes to be unsequenced, then we must test each possible sequence of changes. This is an intractable problem: the number of possible orderings of M changes is M!. If each build/test cycle takes an hour, then any number of changes beyond 7 or 8 is impractical -- testing all combinations of 8 changes would require 4.6 years. It's easier to freeze the sequence.
  6. If hosts receive unsequenced changes, then before restoring these hosts to production we must test each host individually, due to the risk of unforeseen interactions between changes. As above, we must continue to forever treat these hosts as diverged and test them individually henceforth, even if future changes are identically ordered across the set. This is very expensive. It's easier to avoid unsequenced changes.
  7. Therefore, if we need repeatable builds of the same machine, or predictable builds of multiple machines, we can constrain state changes to a deterministic path, with change A followed by B, then C.
  8. The "ideal" sequence is the one which is known to work -- the sequence in which the changes were created and tested.
  9. If we don't constrain changes to a deterministic path, then we by definition do not know the history of the machine.
  10. If we do not know the history of the machine, then we do not know its current state without examining all N bits of the disk.
  11. If we do not know the current state, then we cannot in advance predict the outcome of future changes to that machine.
  12. If we cannot predict the outcome of future changes to a self-administering machine, then we cannot trust its reliability in a mission-critical environment.

What to do about it

A concise and reliable way to describe any arbitrary state of a disk, without describing all N bits of the disk for each state, is to describe the entire history of changes made to the disk, including ordering. A concise and reliable way to describe any arbitrary future disk state is to describe the starting point and history of changes as above, followed by the change itself.

Example Tools and Techniques

[ Compare and contrast some popular and research tools from the perspective of Turing equivalence, with focus on how they can be used deterministically. ]

Acknowledgments

Alva Couch provided an invaluable sounding board for the theoretical foundations of this paper. Conference etiquette prevents him from being named as co-author (he is program chair), otherwise we would have done so.

The debate which was the genesis of this paper began in Mark Burgess' cfengine workshop, LISA 2001.

References