gistfile1.txt

Deterministic Concurrency

1. All threads with every (e.g. Gno) VM Opcode computes on the side a
synchronized virtual universal clock timestamp. Every operation happens at an
incrementing virtual timestamp.

2. All operations involving channels, and all channel meta events like channel
closures, are sent implicitly (invisibly to the Gno programmer) through
channels with associated local timestamp data from the sending routine to the
receiving routine.

3. The timestamp information is also implicitly passed through channels from
sender to receiver upon the completion of a select statement with cases
involving channel read or send operations (or other io operations). 

4. Such information is received from channel to sending routine when writing to
write-only channels.

// routine main
a := make(chan int, 0)

// time_main 0
go run func() { // routine A
 // time_a 10
 a <- 1
 // time_a 21
}()
// time_main 10
go run func() { // routine B
 // time_b 20
 _ <- a
 // time_b 21
}()
// time_main 20

From routine A to B, along with the message `1` is sent routine A's local
virtual clock timestamp time_a: `(1, time_a)`.

In the above unbuffered channel example, you can see that in routine A, `a
<- 1` results in time 21, because it depends on `_ <- a` (1 atomic
instruction) which happens after time 20 in routine B.

This is straightforward because there is only one send to a non-buffered
channel, and a simple receive on the other end. The following is a more
complex select statement.

-----

// routine main
a := make(chan int, 0)

// time_main 0
go run func() { // routine A
 // time_a 10 is 10
 case <-time.Timeout(100):
     // time_a 111
 case <-a:
     // never occurs
 }
 // time_a 112
}() 

// time_main 10
go run func() { // routine B
 // time_b 20
 time.Sleep(100)
 // time_b 120
 a <- 1 // halts at time_b=121
 println("hello") // never prints
}()

Timestampped (system internal) messages are received and processed under
the hood from routine A to routine B (concurrently with execution of
time.Sleep(100)), whereby the channel closure (system internal) event
which originated at time_a=112 gets backpropagated to routine B, such that by
the time `a <- 1` is called it knows to halt, since nothing is receiving
from `a` anymore, as 121 > 112. To clarify, it would not be correct for
routine B to complete the statement `a <- 1` and continue execution
without halting.

For routine B to send 1 to a, it must also receive timestamped events from
A. Depending on what routine B has received thus far from routine A, it
may or may not need to block in real time. From routine B's perspective,
even if `a` were a write-only channel, it is in fact implicitly receiving
timestamp information from routine A, namely here about when the select
statement was completed.

Event information about the closure of the channels, or the receival of a
message from a channel, or the change to available capacity of a buffered
channel due to aforementioned receive, must be communicated under the hood
FROM the receiver's routine that is affecting the channel state, TO the
singular or shared channel state, and TO the sending routine, for the
sending routine to know whether the send should deterministically succeed
or not.

For the purpose of this patent we are restricting the scope of the
language such that inter-routine communication *only* happens through
channels. This is generally not the case, even for Golang where
go-routines can modify other go-routine's state without relying on
channels or any syncing primitives (albiet it would result in a
race-condition, which is not guaranteed to be discovered by the race
detector even at runtime). It is possible to extend this invention to
enable the mutation of state in such a manner even in the GNO vm by
translating such mutation statements into implicit channel operations.

------

It would be reasonable and obvious to allow the extension of this system
by allowing channel operations to take some variable or fixed delay,
so as to simulate actual physical distance between points of computation.

XXX explain in more detail, such as a fixed delay channel system.
Basically, the more delay there is, the more inefficient the system is,
but only slightly. Massive paralellization is still possible even with
slight delays in communication channels.

XXX How does this interact with channel buffer size? Example: If the
buffer length (used capacity) is at capacity, then it will take a little
longer for the information that a receive happened somewhere to result in
actual progress from any sender side routine.