Archive for the ‘Uncategorized’ Category

Random Stuff

During last month, I kept improving some code on my little cross-platform graphic library. New design is now in place to support all different pixel format in opengl ( except palette ) the same way than in SDL. It was a fair bit of work, and a lot of test still needs to be written.

I also found something interesting : the FAWN project.
I have been thinking about that concept since I know about “One-Board PCs” and clusters… But I didnt want to spend so much time and money before knowing if it would be useful or not. Well some answer is in their paper, but I still wonder if research is going on there or not. It seems pretty interesting so far, but I am really wondering about hot-swapping nodes…
For those interested, they are selling their cluster on ebay

On the downside I also learned about ACTA… Sometimes I am saddened by the dedication mankind can put to destroy itself, just for the blind profit of some…

Categories: Distribution, Uncategorized Tags: ,

Distributed Programming Language -> What is it exactly ?

There are already quite a few distributed programming languages out there. The most popular being probably Erlang, although it s not a “network transparent” or “distribution transparent” language. On the other hand Mozart ( which I didnt try yet, but probably will very soon ), seems to have some mechanics for transparent distribution, but with the cost of lot of semantics to be learned. And, well to be honest I never heard about it so far, although I am sure there must be clever systems in it… Why is that ?

The difficulty in finding a proper distributed language for your application comes from the fact, that you can write distributed application as soon as you have any “socket related” feature in your language. However the time you need to write such an application in a language that hasnt been designed for it, is humongous. In addition, in the real world, the necessity or distributed languages is arguable right now, because companies dont see much applications for it just yet. Without the wheel nobody thought about cars I bet 😉

The main question I want to discuss here is : “What does a distributed programming language need in its very core to be useful, widely used and accepted by usual developers ??”

=> To be used it needs to be useful, yet simple, so most developers used to imperative programming can grasp it quickly, and do something useful with it.
In traditional local programming, the execution is done on a CPU, one instruction after another.
In concurrent / distributed programming, the execution is done on multiple CPU, many instructions at the same time ( maybe? ) and we do need a way to harness that. It can be an extremely complex “concurrency graph” of relations between different instructions set in different locations. One of the way to harness it with a very fine-grained control system could be based on “Causality-tracking” algorithm, that are already in use by TeleCom Companies, for mobile phones related applications.

In traditional ( imperative and functional ) programming, we are writing instructions in a structured way, that we can represent as a decision tree. Problems arises when you have to mix the “causality graph” of relations between different instructions or events in the different location, and that decision tree.
If I try to write ( in C++ like syntax) instructions like :

var a = 5; if ( condition )
//I am asking remote processB to increment my variable "a"
{ remote_execute ( incr(a), processB); }

//I expect a to be incremented -> MISTAKE !!!
{ getfrom(a, processB ); }

I am making an obvious mistake, because in the “else” block, my variable a is not going to be incremented, and even more, it might not be known by processB at all. Even if it is a programmer error, we do need a way to tell him early on it s an error, or better, make it impossible for someone to write such a code. And this might be the most obvious error that can happen. If you have written multithreaded applications in the past, you know how troublesome it can quickly become.

The main thing behind compiled languages, is that they try to warn the user during compilation of all the possible errors. And they cant prevent most concurrency errors, because these are very dependent on other factors ( execution environment, ordering of instructions, etc. ) that the compiler cannot have knowledge of. The causality tree of a concurrent program is unveiling during the execution, there is no static representation of it that we can code. And even if we could, it would be a big hassle to the programmer who would probably not even want to think about it, since it s not related to his problem, as long as performance is satisfactory.

To conclude, to be useful, a distributed language needs to :
– remain simple and efficient, maybe simplifying the different ways to have concurrency( threads process, etc. )  and making it more transparent.
– harness concurrency with transparent causality tracking, ( simplicity : transparent, efficiency : allowing concurrent events – partial order )
– find simple and intuitive ways to mix that “dynamic” causality tree with the “static” decision tree. This is a very tricky part. Some system have concurrency controling imperative algorithms( BOINC ), some have imperative control over lightweight concurrency ( multithreads )
– be based on “evaluation”, just like script engines, because we already have a running system, and we can dynamically check for concurrency errors using it. It s also a good sandbox for concurrency algorithm tests.

=> To be widely accepted it needs to do *what we are already doing* but better, faster, stronger, even if we are not already doing distributed applications…
The most widespread “development” and “application writing” activity might be website development nowadays. It make sense in a way because it s related to distribution, people interaction, and just like with distributed languages, few years before the invention of the web, all the nice web applications we use on a daily basis right now would have been very hard to imagine.
To be able to compete with traditional imperative local languages, it should have decent performance on local CPU execution. Probably with implicit threading when it is detected possible, since nowadays most new machines have multiples CPU. It should also be quite familiar and intuitive to get used to it quickly. We probably need to keep and use most of the traditional control instructions ( if/else, for, while, etc. )

A good way for people to be able to use a quite low-level language for what they want is to allow “modules” or “plugins” to add high level functionality to it. the core language should however provide interface to most devices.

The road to an accepted distributed language seems still pretty long, but it s definitively an interesting one indeed…

Does someone already a knows a Distributed Language that fits all his needs ? Does anyone has other / better ideas for distributed language features ?
I wonder when the first truly transparent distributed language is going to arrive and be widely used…

Temporal paradox, an interesting DejaVu

Since I have been playing multiplayer video games over the network when I was young, I have been interested in distributed algorithm, and parallel computing. That s also probably why I am working in that area now 😉  And when you start to be deeply immersed into a distributed environment, the more you realize that the concept of time as we usually know it, is not that obvious. Maybe it s also because I did a little bit too much quantum physics back when I was in Uni…

I wont go into details here, but for example in a video game, there is no way for a player to know what another player did, until this information is delivered to him via the network. Therefore, from the point of view of one player, or one machine, what it is seeing as “his” own time-line, and the time-line of another computer he is connected to, might be very different. It s a bit the same while you’re looking at a star : your seeing the past of that star, and that star may not even exist while you re watching it, and the light on the way might have trouble to come to you…

All these phenomenons got me thinking about the very nature of time for a while and, of course, I got interested in science fiction books and movies, and tried to extract from those, theories and paradox, back when I was in University studying all sorts of interesting things. Now that I am more into computers, I can realize how the usual time line that we can perceive everyday truly influence the way we do things. From complex mathematic algorithm to cooking recipes, everythig that can be assimilated to a “process” is based on a time line… And in computer, that start with imperative computing. Imperative computing is based on the fact that one instruction is executed *after* another, and yet you got experts wondering why we cannot adapt usual imperative language to program in parallel intuitively. Thinking in parallel is not intuitive. For the big majority of us, we think in sequential everyday, all day long. And it make me sad when I see so many things in distributed computing and in parallel architecture that could be really great, if only people would just stop thinking by their own time-line…

Among the different ways to conceptualize time that have been used here and there, and paradoxes that have been exploited in different scenarios, I want here to talk about one movie that I saw one more time recently, where the concept of time is used very “liberally” yet in an interesting way. I want to talk about DejaVu, where the main plot is an investigation on an explosion of a ferry, with a main suspect we ll call “terrorist”, and the hero taking interest in a special victim and even trying to save her by going into the past to change the events that happened. Basic bad guy / good guy setup so far…

I will try here to review the scenario and its “timeline” if possible. I am not bothering about the introduction where the hero learns that he actually can see the past, and even interacts with it. Neither am I taking interest in the love story, or whatever romantic stuff is behind it. Lets focus on dates, facts and consequences. Once the possibility of communicating with the past ( seeing it, or even being able to act on it) is introduced in the movie, it open possibilities for the hero to save the victim. However everything has consequences. But the hero must try  to see if he can change the past or not…

– First pass : changing time ?

From the beginning, the hero’s colleague is missing, supposedly went on holidays but his car is found on the ferry. We then assume he was killed in the ferry explosion. But when the hero send a note back in time, his colleague finds it and that trigger events that lead to his death, in the property of the terrorist.

The hero assumes then (very lightly I must say ) that time can be changed and then he s willing to try to go himself back in time to save the victim. Being myself, the spectator, I was quite skeptical. I used to think that no matter what you do when you go back in the past, events triggered in chain will maintain the timeline where it always is, the only way for it to be stable despite having some “actor” traveling back in time, and triggering consequences from his experience of something that didnt happen yet… Looks like it s called the Harmony Theory… But more on that later.

– Second pass : saving the dead ? “Is she dead or alive !?!”

The hero now thinks he can change the past so he is willing to travel himself back in time, and try to save the, so charming, victim… Before we talk about that lets review ( a part of, because I m not going to list all events ) what the hero has already experienced :

1) the property of the terrorist is destroyed, an ambulance car still there.
2) the appartment of the victim, after the ferry exploded, has a message on the fridge, is full of blood and full of the hero fingerprints.
3) the hero has seen the terrorist, in jail. The terrorist is talking just as if he knows what has always happened and what will always happen… almost like a mystic…

The hero then goes back in time, wakes up in an hospital, and is reanimated by the staff there. He then steals an ambulance car, and goes to the terrorist place. He knows the location from  his own past and use this information to change it… Yet, in the fight with the terrorist, the property is blown up, and the ambulance is in place, all causes are there for 1). Terrorist ran away, with the car of the victim.

He then saves the girl and they decide to drive to her apartment where he clean his clothes and his wounds, puts blood everywhere, write stuff on the fridge, etc. Everything is in place for 2). However this time the hero realizes that what he is doing now, is actually already in his own past, in his own experience… From now on he will try everything to change the past he knows and tries to force events in another way. Apparently unsuccessfully for a while.

Then they drive to the ferry before he starts, in order to meet the terrorist and confront him. They are in the car of the hero’s colleague, and stop at the parking to get on the ferry. Where the car has been found in the hero experience -> this is a hint, meaning that his colleague death, might not have been on the ferry, before he sent back the note in the past or after. Rather it would mean that the hero experienced the same, and went back in time to put things in place, just like he has experienced them. Just as if there was a destiny, or only one timeline, and that a loop in time rectifies itself.

Then happens the fight between the hero, the victim, and the terrorist. But, despite all the previous “hints” of ” time cannot change” or ” what has always happen will remain so” , the victim managed to kill the terrorist. The hero said to teh terrorist what the terrorist told him, when they meet in prison. Or maybe it was hte otherway around, and the terrorist told him what he heard from him in his own experience ? Anyway, the hero managed to get the car out of the ferry, and dies in it, when the bomb explodes, under the water. And NOT on the ferry ! That ferry is now saved, and so are all the people on board.

Now here are two questions :

– when exactly does the timeline start to “change course” and means the ferry can be saved ? ( Special mention of : ” It should nt have happen like this”  from the Terrorist just before dying… )

– How many times did the hero went back in time, before being able to make it “change course” ?? ( careful there is a trap… )

I am sure it would be interesting to read the book to see how much the movie changed the scenario. And to see all the little details that havent been used, intentionnally or not, in the movie. But anyway, I tried here to illustrate, word after word, sentence after sentence, how our perceptions and conceptions are almost all based on a timeline we perceive or imagine, and much more than we actually realize. Thats why it s incredibly hard to think differently, and to come up with theories about time, parallelism that are intuitive and efficient alltogether.

But when you want to do parallelism and distributed computing efficiently, we need to get out of our old conceptions, and realize that we cannot build efficient parallel system inside a restricted sequential conception. A sequence is after all just a special ordering of events. Each event is the consequence of one other, and only one, and each event has one and only one cause. The same way that a clock is a just a special case of time flow. Each second of that clocks happen one after the other. Yet at the same time other clocks are ticking other seconds without direct relations to the first one… Take two clocks put them in different places, in different conditions, when you reunite them they might not mark the same date anymore. “Universal Time” is just something we use because it is convenient, not because it actually *is* so.

Here is my conception of it : time doesnt exist. What exists are causal relationships. Even the tiniest, and from them we build time in our minds, because it is convenient. We build time based on our own memories, especially the most recent ones. and since we perceive one thing after another, time for us is linear. We think of time as a line, the same way we usually think that light travel in a straight way… or the same way we now think that earth has always the same round shape… Because it s simpler to think about it like that.

And then, the next question would be : Can an event have a consequence that would trigger is own cause ? Or said in a more compact way : Can an event justify his occurrence by itself ? Well, … I think not. For now… because it is just simpler for me to think like that.
But then, I have to admit that it s possible that an event has no causes at all.
Just because it looks like something started, once upon a time, in a great “Bang”…