Non linearity and clock in distributed system

How the word distributed matters

Let's imagine Einstein existed, and two observers live with different clocks.

According to their differential acceleration, their clock diverge according to a 3rd observers.

Let's name observers 3 the user. And two components of a distributed system A & B.

Let's assume A & B have a resource for treating information per seconds called bandwidth. Let's assume that the more load, the more it takes time to treat instruction. Let's say that it means the clock «slowed down».

Let's assume that tasks are in form f x g x h .... (data). where f g and h are composable functions. And let's assume A or B can treat 2 sets of functions that can be overlapping.

Now let's make a pun a choose only function that supports distributivity vs non linear functions and see what happens.

if  {f, g, h} is an ECOC (Ensemble Complet d'OpĂ©ration qui Commuttent) then f x g x h gives the same results as h x g x f applied to the data.

Thus, the distributed system does not need a clock, because g(data) does not have any hidden relationship with f(data) in terms of chronology. It works perfectly has just message iteration between functions. The function can be applied in any order. No chronology needed.

Whereas if you use non linear functions you introduce time, and your system must have a central clock that will be the limiting factor of your «distributed system» aka the fastest speed at which you can guaranty transactionality.

Ex: banking system.

I cannot let an actor spends money if is credit/account = 0.

So if I send in parallel the actions of putting money and retrieving it there is an order. I cannot let a user trigger withdrawal after withdrawal (that are fast operations) as long as the slow accounting informations are not treated.

I have to put a lock. Something to ensure the absolute state at a reference moment called now. As a result I cannot distribute in an even fashion on a distributed system  my task. I have a global Lock that must exists.

Because of pure geometry acquiring and releasing this lock has a minimal incompressible delay.

Inside a single CPU : Speed of light, centimeters, nanoseconds.
Inside a LAN : Network latency, meter :  , X ms
Inside a WLAN: kilometer XXXms.
Worldwide: X Seconds.


Since there can be no global states without information transmitted, a global state requires the introduction of a unique absolute arbitrer.

The more distributed your system, the more redundant, the more your clock diminishes if you have transactions. That is an incompressible limiting factor.

What happens with Commutative operations?

Well, they are dazzling fast. You can implement a robust dazzling fast system distributed system.

Commutative functions can be executed out of order.

They just require to be routed as mush time needed in the right circuitry.

Meaning you can avoid a congested node easily, because you can reroute actively at the node level without knowledge of the global system, just the state of congestion of your neighbours.


An efficient distributed system should support only distributive operations that are asynchronuously delivered. And, reciprocally if you want want an asynchronuous system that can scale, you should not accept non commutative operations. 

The commutative part should be distributed, the non linear one should be more logically treated ideally on a strongly synchronuous not distributed system. Systems where the clock is ideally one cycle, thus ideally close to the metal using all the trick of atomic instructions.

Oh, another lad is asking why you can't use your fancy nosql distributed system to have a nice leaderboard for his game.
Well, a > b is a non linear system, sorting is non linear. So well, somwhere a clock or a lock or a finite state machine, or a scheduler has kicked in.
Non linear operations introduce a before and an after. With loss of informations.

if you need the result of a>b then a and b being 2 distributive operations, then you have to wait for both a and b before processing in non reversible way.

To ensure everything was made in the right order, in a non distributive way; there had to be time, so that action are made in the right order. Every non linear operation in a distributed system introduces an hidden clock.

Are non linear operation bad?

I call them filters. I think they are a hell of a good idea, but I say it is very hard to make them distributed. So we should live with them and architecture our distributed system accordingly.

(PS in the map reduce idea, Map can be seen as dedicated for stuff that are commutative, and Reduce for the non commutative one)


PS Let's imagine a distributed system with Forth or RPN

if
def Radius: square SWAP square SUM 
def square : DUP *
def sum : +

Can I write a²+b² as distributed system?

Data Stack : a b
Exec distributed Radius

Can I play the operation of square, swap square sum in any order?
No.

f(a, b) = f(b,a) thus it is commutative. But what is the problem?

The use of a stack introduce a scheduling because there is now a relation ship of order on the application of the operation hidden in the data structure/passing. so a queue is also a introducing a clock.
Distributed system should be wired (message passing) and not programmed (actively scheduling tasks).