Nonlinearity, or, Can Operating System Be Liberated from the von Neumann Paradigm?

Table of Contents

When it comes to personal computing, we require a lot of flexibility. But even meticulously designed tools regularly fail to meet some of the most natural user expectations.

In order to figure this out, let us start with a truth:

Mutability. To use a system is to change the data in it.

We would probably not disagree with this statement. So we change the data to reflect what exists in the real world. But very quickly, we have a lot of things that exist only by inference. Sometimes, the inference is wrong. Even if the inference is correct, we may still want to change to a different inference, and we lament the schema migration.

Oh, no!

Is the truth false? After a lot of frustration, we may start to accept that:

Append-only paradigm. To use a system is to add data to it.

Reference founded in experience. Reference must not be made to things that exist, but only to things that have been experienced.

These two claims seem to be a lot better at characterizing our complete process with information systems.

But I think there is a stronger argument and, as a philosopher, I feel compelled to write it down. Here is an illustration without any philosophical jargon. Although I am not citing any work here, much credit should go to Immanuel Kant and his influence. The distilled idea is quite standalone and close to common sense.


Here are some observations:

Observations.

  1. A universal provenance feature is justified by the possibility of experience alone, and is as necessary as experience itself.

  2. Intelligence is progressive.

    1. In the cognitive process, new space is continuously allocated, without existing space deallocated. The creature would be severely disabled if its mind is space-limited.

    2. History subsumes all concepts and data, making them meaningful to the creature. In other words, everything must be understood in the context of cognitive history.

  3. Instead of maintaining state, intelligence maintains attention: the selection of useful data for the latest task.

All of these, in essence, require a property diametrically opposite to what current information systems have. Current systems, including but not limited to operating systems, are linear in the sense that data is fundamentally mutable, and space in any environment is fundamentally fixed, unless explicitly allocated. I call such a von Neumann (operating) system for its resemblance to the von Neumann computer architecture. My proposal is nonlineaity, in which data is immutable and space is automatically allocated. The linear-nonlinear comparison is very similar to the imperative-functional comparison in the programming language world.

My philosophical thesis can be summarized in one sentence:

The significance of nonlinearity. Nonlinearity (history and its automatic space allocation) is a basic feature of intelligence, hence it should also be a basic feature of a personal computer.

Looking forward to implementing the nonlinear vision, I propose my technical thesis:

Where to implement nonlinearity. Nonlinearity is best implemented within the operating system.

First, there should be a desired feature set of a nonlinear operating system. These features are intentionally stated in a way compatible with both functional and imperative programming paradigms.

  • Provenance. Any execution result (return value and output) knows what execution (program and input) produced it.

  • I/O control. All input is stored, and all I/O is audited.

  • Replay. (A result of the first two features) Any execution can be run again, producing identical behavior.

Next, an extremely oversimplified design of this proposed operating system can be:

  • The OS is an event store and an execution engine with I/O control.

  • Input data, which can include executable programs, is ground truth and not supposed to be deleted. All other things are cache.

  • Once the execution starts, it has access to anything it can find by reference in the event store, subject to audit.

  • Result is returned by the OS posting the output of execution, including the provenance, as a non-input event on the event store.

  • Real-world output must be queued for approval, and the approval result is not available to the program.

  • Reactive execution is by the OS pattern matching on the event store.

  • The only synchronization primitive is the global event store, which can be watched by pattern matching.

Much of the event store is left undefined, because a formal system needs to be designed for its pattern matching, and this should be the major portion of theoretical work. The hope is that when this formal system is in place, it is possible to write any program with only the global event store as the synchronization primitive.

Here I talk about the benefits, the cost, and the difficulties I expect.

The benefits of nonlinearity include:

  • Malleability. The ease of changing and composing software, since intermediate state is now available.

  • Availability of the nonlinar feature set: provenance, I/O control, replay.

  • The operating system is more explainable.

  • Storing input increases resilience to external failures. By “caching” as much as possible, the user can be sure that anything that has been downloaded can be viewed again, even if the data center is up in flames.

The cost of nonlinearity can be summarized as three points. They are immediate, but not without nuanced details:

  • Amount of storage space. Fortunately, nonlinearity requires just space, not throughput or IOPS. It even requires less write longevity in favor of amount of space. All of these combined, the real cost can be significantly lower than a naive estimate.

  • Security commitment. “Do not store it if you cannot secure it.” In addition to regular meaningful data, there is also non-meaningful security-related data. Storing certain security-related data will effectively remove some security features. For one, forward secrecy is rendered pointless, since the nondeterministic input used to derive the session key is now stored in the history along with the private key, rather than destroyed as intended.

  • Potential more work of using history, compared to getting information that is available on demand.

Apart from the cost, there are some difficulties for nonlinearity at the society level. Risking repetition across other submissions, it is included for completeness:

  • Our metaphysical assumptions are too many and too deeply rooted. Using an operating system which categorically rejects metaphysical assumptions will be cumbersome.

  • More emphasis is put on time complexity than space complexity in theoretical computer science education, according to my own experience. This makes it harder for students to understand the value of space in computing.

  • A rigid society encourages thinking in terms of workflows rather than resources and experience. The former has comparative advantage when it works, even though the latter is more adaptive.