Asynchrony

I humbly propose: this may be the most fundamental, or at least this may be the word which comes first if we are to choose only one, .... asynchrony, asynchrony in computation, and therefore, asynchrony in communication (two are the same thing, since computation includes communication inseparably, I hope you at least agree it is one way to see distributed computing, that's my hypothesis in these discussions, as I outlined in my previous post) (and by the way just in case you are worried: I am not forgetting about scribble, in fact we are in the middle of it).

Emphasising asynchrony does not mean for example we should assume a communication medium with unlimited bandwidth (and certainly not with zero latency!). And we wish to have different ways to analyse such a medium --- they may be modelled as "ether" separate from processes or formalised as a collection of processes. We may need a queuing model on some occasions. But these will come later and as needed: at this point we do not mind these aspects, we solely want computation to be asynchronous.

But what does it mean to be "asynchronous"? One may define the notion informally thus:

the potential for each distributed process to be able to work following its own local clock, as far as there is no need to be fed data from other programs and synchronise.

First of all, it is about the potential: and we want that potential as a key element embedded in the model. Second, "local clock" etc is not too good a metaphor: anyway it gives us some idea, that a local program can be left to compute on its own as much as possible. Third it says there is some need to exchange data and synchronise --- but not saying how. Not saying it is to compute a function. If it is computing a function --- well that is one way. But there can be other ways. And there are.

Why do we know? We have known about it from the study of process algebras which are about the universe of concurrent, communicating behaviours. And especially because of our study of the pi-calculus which miraculously captures a very rich variety of interactional behaviours, and, as interactions, a wide variety of computational behaviours, in its tiny syntax. And this wide variety --- for studying which one can use many ideas, such as separation which Palamidessi once used in her beautiful and celebrated result. So we know. There are many kinds of behaviours, all couched in a small calculus of name passing.

What is further fascinating to me ---- and this is the first thing which fascinated me in theory of computing and why I started to work on science of computing seriously --- is that this calculus has an asynchronous version, and it turns out to be a minimal meaningful kernel of this calculus.

This point was observed based on the work by Milner/Parrow/Walker in 1989, and later by Milner in 1990, and let's face it I also contributed in my small way and, as I wrote, this incidental observation fascinated me so irresistibly. Later I found Gerald Boudol discovered the same calculus concurrently (and completely independently), in the context of his Chemical Abstract Machine.

Coming back to behaviours --- so I can tell you we have a huge universe of computational behaviours, and many of these things are meaningful, certainly realisable, and they are not always computing functions.

But that is not enough. That fact I knew for long and of course had been known before me by others. What we needed to know in addition is what it means for behaviours to be functions. Then we know the ground --- by knowing the figure. Since if so we know there is more than the figure --- now the ground can be a figure in its own right.

A series of studies have clarified this, starting from an embedding of functions in processes by Milner, and I do not quote them since there are so many, but let me say studies on logic and games (as we call them in our community) play a fundamental role here. This line of studies is still a very rich field and will continue to be.

So --- to make a long story short --- there are many kinds of interactional behaviours which go beyond what compute functions. And for all of them asynchrony is a foundation, a starting point, even though they may constrain asynchrony in diverse ways. So what we see is messages going hither and thither asynchronously. It is wrong to assume order-preservation in the delivery of these messages a priori --- which does not mean we cannot have it based on some mechanism, but can you think of a Turing machine which embeds a notion of objects and classes? Or data structures? Or even procedures... That will make a bad model, a good execution model should have two properties: being simple, and being very simple. And perhaps the third: being very very simple up to the point it almost (or perhaps completely) flat. I know this does not sound anyway informative (I know that) so I promise --- if you are interested --- that we shall come back to this point later. For now it suffices to say that we start from asynchronous exchange of data which may not preserve order. And we do not go into further details here, since probably the party ain't started yet and it is too early to start eating (but is about to, I believe).

For now, we have mentioned several very basic properties. Incidentally the characteristics I observed above are close to what Matthew Rawings once told me --- or declared to me --- as what should be an abstract model for financial networks.

I am not related to money so much (which surely makes me deal with money issues critically sometimes). Neither in my life nor in my profession I feel intimate about how international financial networks carry trillions of dollars each day, that's a different world, anyway it is a huge network, billions of messages going hither and thither each day, distributed all over the world, and this cannot work synchronously, can it? It cannot be order-preserving, can it? So this is something I do not understand in terms of amount of money involved but can surely understand some basic aspects of it in terms of computation involved.

So this story is after all (partly but honestly) about scribble: "One of its primary application areas of this language is modelling of financial protocols." By the way Gary just wrote to me about identities in interactions --- which are a little different from asynchronously operating localities at the abstraction level we are exploring now, but are closely related, and are certainly one of the key subjects for scribble. That is another topic, we shall surely reach there in near future: for now, we need to think a little more about hardware, to cultivate our understanding of this "a" word further.

kohei

Into the imperative depth

Imperative, I am talking about Turing machines, I am talking about Von Neumann machine, I am talking about read and write, but I am also talking about distributed systems. That has been ignored. Models of distributed systems have been ignored: as a result things are not working. At various levels, but especially at deep architectural levels, be it the Internet or multicore computing.

What are distributed systems? Perhaps one simple axiom gives you some idea:

The only way one can know the state of a remote system is to communicate with it.

And another (related) axiom, this time about a general idea to make your program run fast:

Let your program make the most of the available network bandwidth.

In other words it is a good idea to overlap computation and communication since without communication computation cannot proceed: in fact it is best to regard communication (the process of messages being sent and passed and delivered) as part of computation. In distributed systems we can see this in Internet: and in computer architecture we can see this in Transputers.

You may realise we can shorten these two axioms into one:

Communication and Concurrency

That is we cannot have concurrency without communication (in effect). Communication comes first. This is what Robin Milner said in 1980.

Imperative computation has something weird. The most weird thing is it runs. Another weird thing is it seems to become more easily cooked when it is sequential but by itself it has a strong need for asynchrony and concurrency (on this we shall come back in a later post). In other words its usual outlook may be a bit different from what it really desires in its instinct.

There are several things which have not been working: one of these things is models of distributed systems. That is why we cannot see very clearly what is taking place in CMP, chip-level multiprocessing, that is to say things are happening asynchronously and concurrently inside a chip so we say it is multiprocessing and it is happening on a chip so we say it is a CMP. And we seem to be struggling about understanding what we are struggling about. We feel there are difficulties but we do not know what they are.

A bad thing is the same thing seems to be true with the direction of hardware... When transputers were designed there was a clear understanding of what they wanted and that was deeply achieved... The history did not go in the direction of transputers, it is true. And ironically (but in fact inevitably) the other history, which is the actual history we have experienced, again leads to this idea of concurrency and asynchrony for imperative computing. But if you do not know what you wish to do then what will you do? If only so-called marketing is in your mind you see what you believe to be real which is something immediately possible and desirable or at least looks possible and desirable which means it is an answer interesting to almost nobody when it is finally introduced to this world (that is to say we do not see the potential since marketing or at least bad marketing only sees what is visibly desired now, not what is possible, since for the latter one needs true imagination which is different from both a fancy forgetting hard reality or a conformism which again is unrelated with reality in effect). Let me add in a hurry I am not criticising ignorance of others, far from it, since I confess that I do share that ignorance with everybody, in the sense that I do personally feel a severe lack of understanding, which I hope we can make clear together or at least investigate into it.

I think we have forgotten what the Von Neumann machine is about, what struck Alan Turing on one rainy day 80 years ago which started this science, this engineering, this adventure.

(To be continued.)

kohei

How the world is born

I was in Oslo. I was in Reykjavik.

In these places I thought about how the world is born. For example the world of data. If everything is a sequence of zeros and ones then there are no data --- unless they come from data.

When you start to think there are numbers and characters and strings and instructions you start to have data and then you start to have records and tagged unions and objects and all that.

The world of interactions is born in the same way. There are always messages, asynchronously born, issued, exchanged, received, processed. This has been so for thousands of years. There are however nothing we can catch there, nothing on which we can build --- not yet. Only when you single out a streak, or a zig-zag, of messages, some collection of messages, and say "here is a conversation" and you now see not messages but a flow which makes up a conversation, that is, you only have to single out one collection of messages as a flow, as an exchange, that is when a conversation is born.

Then you have many conversations, just as you have many data.

That is how types come about. Types in their basic form are there to single out, and once you learn to single out, once you can de-lineate, put a circle on the ground and find the "figure" (hence the "ground" too) you say (and this is a violent act, in a philosophical sense) there are messages inside (so in fact this is the first time you have seen those messages) and there are messages outside of it, only at that time you start to have a type, since types are there to delineate and describe, you want to say this is a "number", this is a "function/procedure over numbers", a basic form of types is something which can never be separated from individualisation.

I know this part is subtle. I know I need concrete examples. Not today. Here I hurriedly record my further thought from Reykjabik.

Static analysis can make things right and there are many powerful methods: for that purpose we first need something to start with and that is not static analysis. Similarly assertions and logic however snappy your reasoning would be are not something you can ultimately rely on since there is nothing you can ultimately rely on --- when you think you are not relying on anything you are doing so based on some tacit understanding of a closed community (which may give you comfort but which does not give you clarity). No ultimate. So you need to rely on something which has an explicit act of starting. I do not know why this is like this but it is so.

Kripke, a great thinker, wrote about something similar --- about an act of naming. For many "names" no ritual of naming as he described may have actually taken place. What he meant is that it is an explicit act, even if an unconscious act, you communicate that decision of naming, even if one on the receiving side does not see that it is a decision. And how it was fitting for me to think about these acts in Reykjabik, in the world of volcanoes and barren lands, where we need to name, we need to delineate, since if we do not do so we do not have anything to cling to, we cannot (re-)claim a place for human.

(By the way that is why there are only few good names in science and they are what will remain. And science of computing is almost not science --- at least its subject is so new in comparison with what we know as natural sciences or even mathematical sciences. So it has very few good names --- of course we have many fashionable ones but good ones are rare).

And just as yellow is yellow and a dog is a dog we have data, and we reach delineation of the whole collection of messages --- in the past, now and in the future ---- zig-zags of interactions, flows of interactions, we say "here is a conversation taking place" and "this conversation has such and such structure" and I do not think I am proposing this as a new technology, I am describing how it has begun and how it is always beginning repeatedly, just as an act of naming is taking place every time everywhere every now-and-then, but let me tell you this at least, albeit in a low voice: I do suspect things begin like this since I have some recollection of seeing them taka place.

In fact how can you analyse if you do not have the target of analysis? How can you assert and reason if you do not have the target of assertion and reasoning? What do you reason? What do you assert? Of course you can leave things implicit ... but that may be a bad strategy, in the end. And what I am saying is something well-known in science: do not think clever ideas work, clever ideas never work, only deep understanding works. One thing we have known for a long time in science is all good ideas are accumulative and almost uninterestingly built up towards generality and uniformity.

But I am not saying we cannot have that moment of striking clarity, like when Turing wrote to his mother he had found something very different from theories by his contemporaries, that his theory runs.

And it ran, and is running. That abstract discovery (with others' subsequent contributions including and notably Von Neumann's) has led to what we know as computing. And quite a few decades after that discovery perhaps only these days we started to have theories which can describe and understand the meaning of that discovery as science. But that is another story.

I was in Oslo, I was in Reykjavik. Tonight I wrote a few lines from what I remembered there, as well as after I came back to Britain. I am a foreigner living on British soil, and perhaps a foreigner for ever wherever I live. But I invite you to this abstract topos, a forum, since neither is what I pointed out above about science telling us that we cannot enjoy a few conversations, dialogues --- this is the place friends can exchange ideas in a most abstract and most concrete way, in a way which is about something universal but which can only be done in a most personal way, as human has continued to do so since they found this way of conversing and as they will continue to do so as far as human's history lasts.

kohei