Initial ideas for framework's system model

[sergefdrv]

This is a discussion for gathering initial ideas concerning the framework's system model as described in #47.

[sergefdrv]

Perhaps, we should start thinking about the framework's system model from the most abstract level: the distributed system as a whole. At that level of abstraction, the distributed system can be represented as a single entity. Obviously, it doesn't make sense to consider it in total isolation, for it must exist within and somehow interact with the rest of the world.

Here it already starts getting interesting and we can ponder on the following questions:

• What could be considered a part of the external world and what could belong to the internals of the distributed system?
• How could we represent the external world w.r.t. the distributed system?
• How could we think about the state of the distributed system and the state of the external world?
• What is time w.r.t. the distributed system and the external world and how could it manifests itself in the system model?
• How could we represent non-determinism in the system model?
• How could we model the interaction of the distributed system with the external world?
• How could we think about failures at this level of abstraction?

[anchalshivank]

What could be considered a part of the external world and what could belong to the internals of the distributed system?

Internals of the Distributed System

1. Nodes -> part of distributed system that has its own local state , computation and communication abilities
2. Communication channels or the networks that connect the nodes

External World

1. Clients or users who interact with the system
2. External services like databases, apis or other distributed system
3. Environment in which the distributed system runs , including the physical network , hardware or cloud infrastructure

[anchalshivank]

The key distinction between the internals of the distributed system and the external world is largely based on control and responsibility:

• Internal components are those that we can control , configure and define. We are responsible for their behavior and operation (nodes, algorithms and communication logic).
• External components are those outside our direct control, but we must design the system to cope with them (clients, external services, infrastructure).

[sergefdrv]

I think we are getting closer to the essence of your point, but there were new entities introduced into the discourse. Who are "we", who is responsible for the behavior of the distributed system being designed? Are we a part of the distributed system? Where do our responsibilities come from that determine what is distributed system's internal and what's not?

[anchalshivank]

1. Who are "We"?
In this context, "we" refers to the designers or developers responsible for building, configuring, and maintaining the distributed system.

2. Are we part of the distributed system?
No, we are not part of the system itself. We are not nodes or part of the infrastructure. Instead, we are external actors responsible for the system’s design and management.

3. Where do our responsibilities come from that determine what is internal or external to the distributed system?
Our responsibilities in defining what is internal or external to the distributed system stem from the degree of control over the system component.

Internal Responsibilities:
We are responsible for everything we control, design, configure, and directly manage. This includes components like nodes, communication protocols, and algorithms.
These components are considered internal because we shape their behavior and operation directly.
External Responsibilities:
We are responsible for ensuring the system interacts properly with components outside our control, such as clients, external services, and infrastructure.
These components are external because they exist independently, but we need to design our system to adapt and interact with them effectively.

[sergefdrv]

Do you mean that we are more or less free, and in fact that is one of our responsibilities, to define what is internal and what is external w.r.t. the distributed system we model and design, expect for the components that we (or rather the distributed system that we define) cannot control? If we decide to include something as a part of the system then doesn't it necessarily mean that the encompassing system takes control of that something in our model due to the fact that it is now considered a part of the system?

[sergefdrv]

Perhaps, the point of view on the distinction between internals and externals based on control and responsibility is somewhat similar to the point of view in terms of uncertainty and non-determinism (see here and here).

[sergefdrv]

I suggest to think of whole distributed systems as something purposeful, sufficient and complete.

In a functional model, a distributed system must be a part of a greater system, playing a certain role within the encompassing system, performing a certain function therein, i.e. have a purpose. From this perspective, at the most abstract level, everything that is used to fulfill the purpose of the distributed system, and nothing more, can be considered internal to it, making it sufficient and complete.

[sergefdrv]

Of course, it matters how we define the system's purpose. For example, let's consider a state machine replication system. We can define the purpose of such system as simply serving client requests according to a specified deterministic state machine in a reliable, fault-tolerant manner. Alternatively, we can define the purpose as totally ordering client requests, triggering execution of those requests in that total order on replicas of the deterministic state machine, and responding to the client requests with the corresponding execution results. The former is a higher-level purpose, and the replicated state machine (including, e.g., the database to persistently store its state) would be internal to the correspondingly modeled distributed system; whereas, in the latter case, the replicated state machine would be external w.r.t. the distributed system. So the system's purpose can be defined at different levels of abstraction, and this determines the scope of the modeled system in terms of sufficiency and completeness.

[anchalshivank]

I initially approached the distinction between internal and external components from a control-based perspective. My thinking was that internal components are those we can design and manage, while external ones are outside our control.

However, I now see that we can also frame this distinction in terms of the system’s purpose. The purpose of the system can serve as a guiding principle for determining what is internal or external. Components that directly contribute to fulfilling the system's purpose would be considered internal, while those that interact with the system without directly serving that purpose could be treated as external.

That said, how do we define the purpose in a way that remains useful, given that the purpose will change based on the specific use case?

[sergefdrv]

The purpose of a distributed system will naturally depend on the purpose and structure of the greater system that it is considered a part of. I think, to make it more useful, one can try to define the purposes of a given type of distributed systems in a way that makes it reusable in the contexts of possibly many other encompassing systems, i.e. by making to more generic.

[sergefdrv]

Abstractly speaking, the purpose of any system is to reduce uncertainty, i.e. non-determinism of the external world, in a certain way.

[sergefdrv]

Time is closely related to the notion of change. Intuitively, we can start by considering time as a dimension of change, a continuum for representing the dynamics of the system. Then a dynamically changing system can be represented with a function of time, where the image of the system at each point in time corresponds to the state of the system at that moment.

Assuming there are countably many system states, the time-function effectively defines a sequence of system states or, equally, a sequence of state transitions. Time makes each state transition distinct from any other state transition in the time-sequence, even if the corresponding changes in the system state are equivalent. So we can think of time as ordering of changes.

We can take a part of the system, a subsystem, and obtain that subsystem's time-function by projecting the result of the original time-function onto the corresponding partial system state. Partitioning the original time-sequence into contiguous intervals according to the partial state projection, we can relate the subsystem's state transitions to the state transitions of the original system corresponding to the transitions between those intervals. This will preserve the ordering according to the precedence relation.

For any pair of state transitions in the same time-sequence we can tell which one precedes the other in time, thus defining a precedence relation. If we take two arbitrary subsystems and try to relate their state transitions in terms of precedence according to the encompassing system, there might be some state transitions that correspond to the same state transition of the encompassing system. We can say that such state transitions are simultaneous. The precedence relation should be undefined for simultaneous state transitions and thus become a partial relation.

Time is also closely related to the notion of causality. We can consider state transitions as events, where one event may causally depend on another event. An event casually depends on another event if a modification of the latter can affect the former. Casual dependency must be an asymmetric and transitive relation. There might be events such that are neither casually depends on the other, so the casual dependency relation can be partial, as well.

An event can only casually depend on an event that precedes it in time. Time must ensure casual consistency by ordering events such that this rule is obeyed.

So we can think of time as causally consistent partial ordering of changes.

[dtornow]

I believe "simultaneous" implies "at the same point in physical time" whereas the term "concurrent" implies "unrelated". So if two transitions are concurrent they can happen in any order or simultaneously. (I am not an English native speaker tho)

[sergefdrv]

"simultaneous" implies "at the same point in physical time"

which is kinda what's implied by "correspond to the same state transition of the encompassing system". As I put it there, simultaneous transitions are just different projections of the same transition. However, this changes when we think about causality and relax the ordering from total to partial.

whereas the term "concurrent" implies "unrelated"

indeed, we can say that transitions that don't causally depend on each are concurrent. It should not matter how we order concurrent transitions.

[sergefdrv]

We should remember that the distributed system that we model must be a part, a subsystem of a greater system. And we should think of its relations to any other subsystem of that greater system in a similar way as we think about relations between subsystems within our distributed system.

[sergefdrv]

Some ideas from Are We There Yet by Rich Hickey:

• future as a function of the past
• identities associated to series of causally-related values
• state as a mapping from identities to values

By values, I believe, Rich means a piece of information. He emphasizes that values are immutable. In our thinking, we abstract a series of causally-related values as an object by associating an identity to the series of values. The system state is an immutable snapshot of the system that is a mapping from object identities to the corresponding values. When there is a change, the future is created from the past by applying a function to the state of the past.

[sergefdrv]

Time and non-determinism are closely related. If a system is fully determined by the initial assumptions then it's absolutely static, and time is irrelevant to it. Distributed systems are not like that.

Non-determinism primarily manifests itself as uncertainty of changes happening in the system over time. On the other hand, deterministic intermediate transformations within the system should be irrelevant in terms of time. Building upon previous considerations, we can think of time as causally consistent ordering of non-deterministic changes.

The ultimate source of non-determinism must be outside of the system because a system is determined by everything that is a part of it. Thus we can think of non-determinism as external dependencies of the system.

If we take a certain state transition of a system then everything it depends on must also be certain. From that perspective, the past is fully deterministic; thus non-determinism belongs to the future. We can say that a dynamic system consumes (resolves?) non-determinism from outside as it progresses in time.

[sergefdrv]

Although the past is fully deterministic, as a finite system progresses in time, the system can only retain and expose a bounded amount of determinism.

[sergefdrv]

Building upon previous considerations about time and non-determinism, we can think of system state as consistent image of the system or information that is necessary and sufficient for preserving the system's causal consistency as it progresses in time. In other words, the system state represents the past of the system, the result of causally consistent partial ordering of changes that possible future changes may causally depend on.

The system state does not, and often cannot, represent the history of the system in full detail; instead, it contains just enough information about the past to preserve the consistency of the system in future, thus connecting the past and the future. Since the system state may lose unnecessary information about the past, and it must do this if the lifetime of the system is indefinite, it may be uncertain about the exact prior history of the system, as if partially retaining the non-determinism absorbed from outside in the past.

[sergefdrv]

Interaction is a dynamic process, something that happens over time, and thus it inherently involves non-determinism (see previous considerations about time and non-determinism).

We can think of interaction as causal dependencies between the interacting systems. In unidirectional interaction only one system depends on the other; in bidirectional interaction both systems depend on each other. A subsystem interacts with the encompassing system by interacting with other subsystems within that encompassing system.

The system that acts in interaction as an external dependency of the other represents a source of non-determinism for the latter. If we consider the interacting systems as one then we shall see that the non-determinism of their interaction must ultimately originate from the outside of both systems. Thus we can also think of interaction as redistribution of non-determinism from outside.

[sergefdrv]

Note that the presence of causal dependencies between interacting systems implies that they must also share common state (see previous considerations about state).

[sergefdrv]

A correct system must fulfill its purpose given the assumptions hold. However, when the assumptions are violated, the system may fail to fulfill its purpose. In other words, a system as a whole may fail if the amount of uncertainty (non-determinism) imposed on the system exceeds what it was supposed to handle. In that case, the system will leak the excessive non-determinism imposed on it.

[sergefdrv]

In computer science, there are metaphoric concepts of "angelic" and "demonic" non-determinism. Angelic non-determinism aims to favor desired results, whereas demonic non-determinism allows for unpredictable and potentially unfavorable outcomes. We might also want to distinguish those types of non-determinism in our system model.

[sergefdrv]

As noted earlier, we can think of interaction between (sub)systems as establishing new causal relationships between events (changes) in those systems or, more precisely, occurrence of events in one system that causally depend on some events from the other system.

We can also think of such interaction as communicating information about causal dependencies between past events. The information thus communicated can be of different fidelity, i.e. preserving different amount of details about transitive causal dependencies between past events. The amount of detail communicated determines what causal dependencies the new event can establish with the past events. The amount of information that can be communicated in interaction is limited; therefore, new causal dependencies may only refer directly to a limited part of the actual causal dependency graph.

At the same time, each act of interaction effectively resolves some amount of non-determinism imposed on the recipient system from the outside by determining which from all possible communication events occurs. On the other hand, since only limited amount of information can be communicated, some uncertainty, i.e. non-determinism, may be re-introduced in communication from the perspective of the system where it originates from.

[sergefdrv]

We cannot allow absolutely arbitrary interaction, i.e. establishing new casual relationships, between (sub)systems, or we end up with chaos instead of a purposeful system. Therefore, there must be something that determines which interactions are possible and which are not.

Absolutely isolated, unrelated systems should not be able to interact; in order for interaction to happen between systems, they must already have some relationship. Thus interactions are enabled by already established relationships.

We can think of those prior relationships enabling interactions as links or connections between systems. Such connections can be established dynamically as a result of prior interaction, but ultimately, there must be some set of relationships determined by the way the system was initially prepared. Those initial relationships effectively characterize, define the system and its possible behavior.

[sergefdrv]

Though, if this is all then there is a problem: once a potential interaction is enabled, there is no way back, it would remain enabled, and nothing would prevent it from happening. Non-trivial distributed, concurrent systems should allow interacting with them in different ways, and prior interactions should influence the future behavior of the system. If possible interactions only ever get enabled but never disabled then the number of possible interactions would monotonically increase as the system keeps interacting. Intuitively, this is not what can happen without a bound in a real system. Therefore, interactions should not only be able to introduce new possible future interactions but also exclude previously enabled interactions.