A probabilistic solution to the Two Generals problem

Here is a probabilistic solution to the two General's problem; it gives a high probability of succcess if the number of messages(messengers) is kept high.


The two General's problem is a problem of synchronization between two army Generals. They have surrounded an enemy army that is more powerful than any one of the two armies. But together the two armies outnumber the enemy and can win. The problem is that the two Generals are far enough from each other and can't communicate with each other except by sending messengers. The messengers have to move through enemy line. The messengers can either get caught or reach the other General with a message.How would the army Generals agree on a time to attack? If they don't synchronize their attack, the enemy will win. The receiver General has to send an acknowledgment back to the first General now. The acknowledgment has to be sent through a messenger. The messenger again has a possibility of getting caught by the enemy. To acknowledge the receipt of acknowledgment, a messenger has to be sent again. Thus, the cycle of acknowledgments will continue...

Let's make some assumptions before discussing a solution to this problem:

Assumptions:

A1- Each messenger has 50% chance of reaching the other General with the message.
A2- We will expect a 99.999 % chance of agreement between the Generals as sufficient enough.
A3- Each General sends an equal number of messengers.

Now, the chance of a messenger reaching the other General is 50%; it means the chance of failure is also 50%. If a General sends N messengers, the probability that none of them will reach the other General is (0.5)^N. So, the probability that at least one of the messengers will reach the other General is 1-(0.5)^N.

So, the probability that at least one messenger from each General will reach the other General is (1 - (0.5)^N)^2. When at least one messenger from a General reaches the other General with a time to attack, and an acknowledge from the other General reach the first one the message+acknowledgment is complete and there is an agreement.

We are taking the probability of 99.999% as success.
So, (1-(0.5)^N)^2 > 0.99999
or, (1-(0.5)^N) > 0.999995 (thanks to the calculator that is present in Google search, "square root of .99999" and search)
or, 0.5^N > 0.000005
or, N = 17

So, if a General sends 17 messengers one after the other with a message, and the other General replies with 17 messengers with acknowledgment, we have a greater than 99.999% probability of an agreement on the time to attack. Increasing the number of messengers increase this probability even more.

RAID Primer

Found a brief and good online paper on different types of RAID ( Redundant Array of Independent Discs ). It explains RAID concepts with a brief explanation of each type along with their pros and cons.
The paper can be read here.

The toilet

1- Say, there is a common toilet with many doors.
2- A person can enter from only one of these doors at any time i.e. the door to enter is fixed for him.
3- A door can be used for entry into the toilet by many persons i.e. it is a common entrance for some persons.
4- Only one person can use the toilet at a time.
5- There is a toilet supervisor whose job is to see that persons behave properly.
6- The supervisor gives each of the persons who use that toilet a number so he can recognize them when they come to use the toilet.
7-The higher the number the higher the chance of the person getting to use the toilet.
8- If a person is using the toilet and another person comes up whose number is bigger, the supervisor kicks the first person out and lets the second person to use the toilet. The kicked one get to use the toilet once the bigger number person is finished. The same fate awaits the second person if another person with even bigger number comes. In this case however, the first kicked person has to wait even longer. If the small number person is one unlucky guy he will find all persons coming with numbers bigger than his and he never gets to use the toilet or may have to wait for too long.
9- Seeing the plight of persons with small numbers the supervisor decides to help them out. He now puts a lock on each door. A person with small number now has option to lock as many doors from inside as he wants.
10- A door is open unless someone is using the toilet and has locked it from inside.
11- Any person can enter if his door is not locked and no higher number person is using the toilet. If a smaller number person is using the toilet when higher number comes and the door is not locked, the supervisor kicks the smaller person out and the higher number person uses it. The smaller person can reenter once the higher number person is done.
Now the supervisor is happy. The person who got small numbers can happily use the toilet if they lock the doors. But the person using the toilet often don't lock all the doors, so they still get kicked out by higher number person whose door they didn't lock.
This also cause another problem. Now sometimes the higher number person can't use the toilet because his door is locked by smaller number person who got kicked up by another person with a number somewhat in the middle of the other two. The highest number person should be using the toilet but the door is locked so he can't. Instead the middle person is using it. The supervisor didn't like it but he can't do anything with present rules so he does something else to help out the highest number person in such cases.
12- Now when a smaller number person goes in the toilet and locks a door, and a higher number person comes to that door, the supervisor exchanges the numbers of the two persons for the time while the small number person is using the toilet.
13- Once the person using the toilet is done, the two get their numbers back. The smaller person opens the door and comes out. And the higher number person enters the toilet.
14- If a person with a number somewhere in the middle comes before the (original) small number person finishes, he sees that a bigger number person is using the toilet since smaller and higher guys have exchanged their numbers. After the guys is done, the real higher number guy gets his number back and enters the toilet. So the middle guy has to wait for both the other two persons and gets a chance to use the toilet after them.

Now substitute the toilet with processor, supervisor with scheduler, persons with processes, and numbers with priorities. 1- to 8- describe the priority based scheduling with preemption. 8- is known as process starving. 9, 10, and 11- constitute what is known as priority inversion.
12, 13, and 14- are examples of priority inheritance.

The analogy isn't perfect though, and there might be some loopholes.

Virtualization is where the action is !

Virtualization is the buzzword in the world of Operating Systems these days. Recently KVM - Kernel based Virtual Machine capability was introduced into Linux. When completed, it would make it possible to run Windows ( maybe other OS too) as a guest OS on top of Linux in the newer Intel and AMD processors that have support for virtualization.
KVM is virtualization specific to Linux. Other virtualization technologies also exist some of which like VMware are very advanced and allow many more OS's as hosts and guests.
Another virtualization technology under development is Xen which will be a real competitor of VMware as it will have support for many OS's just like VMware and can be used with older processors as well. Xen is an open source project unlike VMware which is proprietary.
Then there's hardware virtualization which allows one set of hardware to run many OS's. UltraSparc T1 aka Niagara is supposed to get Logical Domain ( LDom ) support in the near future which will allow one Niagara processor to run many different versions of Solaris OS simulaneously.
IBM and Sun have had hardware virtualization in their big iron for a long time but now even smaller machines can have it. Solaris for example allows a form of virtualization with Zones where a machine with Solaris 10 or some OpenSolaris distro can run dozens of virtualized instances of the the OS. Each Zone is a secure virtual OS instance on which applications can run which can be compromised without compromising other zones in the same system.
With all these different virtualization techniques in Unix, Linux, Mac OS X and even in Windows, user today is the king! What was unthinkable a few years back is now possible thanks to all the advances in technology, be it open or proprietary.

Trends in CPU design

For the past few years, in the processor field, the trend has been slowly shifting from a single high Hz CPU to multicore processors. Intel has Xeon dual core and has managed to paste two such chips to bring out what it calls quad core, AMD still has only Opteron dual-core CPUs and is likely to release native quad-core chip next year. There are other smaller players like Azul claiming to have much more cores in a CPU but the real players are only four of them, the remaining two being IBM and Sun Microsystems. IBM along with partners worked on designing Cell chip but it is a special-purpose processor, not for general computing. Sun surprised everyone last year with its eight-core Niagara processor also known as UltraSparc T1. It not only had eight cores in a single chip, but has the capability to run 4 simultaneous hardware threads in each of them giving an impression to the OS of running on a 32 CPU machine.
Sun is going to follow it with Niagara 2 which will have twice the number of threads in each core, thus a virtual 64 threads in eight cores! While Niagara has one floating point unit (FPU) shared by all 8 cores thus slowing down the floating point performance, Niagara 2 will have an FPU for each core. It'll also run with a higher clock rate. So it will be a complete server-on-a-chip when it comes out next year. Seems to be the most interesting processor at present.

More about Niagara 1 at :
Acehardware

about Niagara 2 :
Official Sun doc
and
News.com

Cell processor info at:
Official IBM link