Nonlinearity, or, Can Operating System Be Liberated from the von Neumann Paradigm?
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, especially by only supporting very specific workflows. Many unsupported workflows are possible, but cumbersome, because required information has left the working context, or even destroyed completely. In my opinion, this is the consequence of ignoring a basic cognitive necessity: nonlinearity, the opposite of linearity, meaning step-by-step, sequential, and destroying the old state (“linear” logic). I propose to address this problem category by respecting and supporting this cognitive necessity in the operating system.
The Role of History in Cognition
It is obviously a truth that:
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, or as a result of executing some code. Sometimes, the inference is wrong and needs to be changed. Even if the inference is correct, we may still want to change to a different inference, and we lament the schema migration. Or, it may be more common for us to encounter the situation in the introductory paragraph: resources have left the working context and been destroyed.
Oh, no!
Is the truth false? After a lot of frustration, we may start to accept that:
These two claims seem to be a lot better at characterizing a more complete approach with information systems. They do not contradict the earlier claim, but they are more demanding, in that they require us to manage resources in a fully traceable way.
Here is a narrative that illustrates these claims. 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.
An intelligent creature has no trouble reflecting on its recent trail of thought. With sufficient tools such as pen and paper, it can do this for as long as it wants. It infers things using whatever rules it wants to use, and being a scientific-minded creature, the rules are under scrutiny, too. Therefore, the creature uses the tools in such a way that every derived fact has a provenance.
If this intelligent creature has a computer, it rightfully asks for the same features its mind already has. The most necessary thing for the creature is that any state in any operating system has a previous state, and this state can be saved for future inspection.
Now that a history is established, each time a reasoning step is taken, everything can be interpreted anew by considering the additional result.
Here are some observations:
-
A universal provenance feature is justified by the possibility of experience alone, and is as necessary as experience itself.
-
Intelligence is progressive.
-
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.
-
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.
-
-
Intelligence maintains attention: the selection of useful data for the latest task. This process has very little resemblance to any conventional state management.
All of these, in essence, require a property diametrically opposite to what common information systems have. Common systems, including but not limited to operating systems, are often 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 connection to the von Neumann computer architecture, whose native instructions are imperative and programs linear. My proposal is nonlineaity, in which data is immutable and space is automatically allocated.
The proposed principle can be summarized in one sentence:
Nonlinear Operating System
Looking forward to implementing the nonlinear vision, I propose my technical thesis:
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.
It is notable that a nonlinear operating system has many features of a substrate. The event store provides transparent data persistence, and all programming languages can be used with the operating system.
Related Work
NixOS uses a declarative system configuration framework that supports rollback, so it has some nonlinear features, but is not capable of replaying execution from input in the most general sense.
Nonlinearity and the Computer Ecosystem
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.