Friday, February 26, 2010

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.

Thursday, July 23, 2009

Redirection and 2>&1

In Unix, one often finds a input and output redirection "<", ">", ">>". These are simple to understand.

Users can also do redirect one stream into another stream. This is done by using standard file descriptors. So, if someone wants to redirect all standard errors to whereever standard output is going, add 2>&1 in the end of the command. 2>&1 means send the standard errors to where standard output is going. 2 is the default file descriptor for stderr and 1 for stdout. If certain command is redirecting stdout to, say some file, stderr still goes to default screen. If you want stderr also to be sent to the file where stdout is going, use 2>&1.
Similarly, you can also redirect stdout to whereever stderr is going by 1>&2.

Also, remember that "some unix command > some_file 2>&1" is different from "some unix command 2>&1 > some_file". The first one redirects stderr to some_file, whereas the second won't.

Saturday, July 11, 2009

A tutorial on setuid and sticky bits in Unix

Unix users are sometimes confused with setuid and sticky bit permissions on files and directories. Below is a small tutorial on the most common use of setuid and sticky bits.

There are certain files or devices that are writable only by root. Nevertheless, ordinary users often have to use root-owned programs that try to write to those files. Since these files are writable only by root, how would a non-root user run the program that writes into that file. The solution in Unix is setuid bit. When this bit is set on a root-owned program, the program gets the effective privileges of root even when run by non-root user. This happens only for setuid programs i.e. for programs that have setuid bit set by owner/root. Example is passwd program that modifies the password files that are writable only by root. Since passwd program is setuid id, any non-root user can run this program and modify his/her password. Another example is ping program that is also setuid since ordinary users also run the ping program that accesses network devices.

In the file permission listing found by command “ls –l” setuid programs have the s in place of x. This means the program is both executable by owner and setuid. Another possibility is S in place of x which means the program is setuid but NOT executable. The program permissions could look like

rwsr-xr-x ( executable by root and setuid; what matters for setuid bit is the third letter)

OR

rwSr-xr-x ( hmmm…does it make sense !?)

One can make a program setuid by

chmod u+s prog_name

OR

chmod 4755 prog_name

Although the explanation above was specific to root-owned files, it could apply to any owner. So any user can make a program owned by himself/herself setuid and let others modify some of the owner’s files by this program.

Another related special permission setting for a program is setgid bit which is similar to above, but is useful only to the owner’s group. The setuid and setgid bits have different meanings when applied to directories. setgid bit on directory "d" means that any file or directory created under it would get the group id of "d". Remember that normally the group id of any newly created directory is the group id of the user who created it.

Yet another special permission is the sticky bit. Now-a-days, it is mainly used for directories. Let us first understand what directory permissions mean. Some directories are writable by all users. That means all users can create files as well as delete files inside such directories. Execute permission for a directory means search permission into that directory. So, execute permission is necessary to descend into that directory.

An example of directory with sticky bit set is /tmp. This directory stores temporary data that is created by user programs. Since these directories are writable by all, any user can delete any file! Even those files that are owned by others! To fix this state, such directories have sticky bit set. Now only the owners can delete any file in such directories.

Directories with sticky bit set have t letter in the execute permission set for others, as seen by the output of “ls –l”.

rwxrwxrwt ( sticky bit is set and execute permission for others)

OR

rwxrwxrwT ( sticky bit set but no execute permission for others)

Capital T means that others don’t have execute permission for that directory, so they can’t search into it.

update: Added setgid directory explanation.


Tuesday, May 19, 2009

How Unix shell executes commands

Unix shell runs all the commands in a new forked child process. It means, the shell in which the command is invoked becomes the parent that creates a child process ( a shell process). The child in turn exec's the command by overlaying itself with the command's image. Why would the new process be created for executing the command? Can't the shell run the command in the same process. The answer is:
If the shell overlays itself with the command's process image, it would have nowhere to return when the command finishes executing. This would close the parent shell. Running "exec command_name" effectively does this i.e. runs the command that evetually closes the shell when the command execution is over. To avoid closing the invoking shell itself, all commands are run in a new child process by the shell.

We can use "strace" utility to track down the child process creation and execution system calls. Note that doing strace on the command will only trace the command after fork i.e. the output will show execve(...) followed by other syscalls ending with some exit call. This is so because we are tracing only the command which really is in the child process. To trace how the shell has created a new child process by fork() (clone() family in Linux), do strace on the current shell in a separate terminal and then run a command in the current shell.

PS: edited off the 'subshell' part as that is a different beast altogether...

Friday, January 2, 2009

Software engineering vs teaching

I faced a reality check last week. I always wondered why anyone, competent and educated in the field of computers, would pursue a career in teaching and not join a company as software engineer. It was perhaps the inability of the person to cope up with the demanding environment in the software field. That could be the reason anyone leaves a better paying job and settles for lowly-paid teaching career - or so I thought.

Last week I sat down and tried to list the pros and cons of the two careers.
Here's what I got from my "findings".

Let's tackle the salary part first. Since a teaching career asks for a formal degree, preferably a post graduation, let's assume the person is a post graduate in Computers.

Now, if the person choses to join an IT career, he has to devote at least 40 hours a week for work; in reality it could be much more if one takes into account the unpaid "late-nights". Assuming a 30 days month, and a good INR 50,000 a month in salary, the person makes about INR 285/hr.

On the other hand, a teacher at an engineering institute has about 18 hrs a week of teaching load. For INR 40,000 a month, the teacher would be making about INR 500/hr on average - a full 215/hr more on average than his counterpart!

Other pros of a teaching job vs software engineering -

- no late-night unpaid overtime work that one is expected to do
- better quality of life, better family life as well; a teacher can spend much more time with family
- no continuous sitting-in-front-of-computer-screen until you visit your doc for back-pain; backache is known to be a common ailment with IT professionals
- less stress; no deadlines
- stability; none of those pink-slip days inspite of very good performance. It's not uncommon to find star-achievers, poster-boys being given a boot if the head honchos make company wide cost-cutting plans

Taking all the above into account, I wonder why anyone would prefer IT career over teaching if given a choice. Is it for that extra few thousands? Consider this! IT companies are located mostly in places where the extra salary of a software professional would be spent on rent and other costs. A teacher can take up consultancy work and could earn even more ...

Tuesday, December 16, 2008

C++ inheritance - public, private, protected

Inheritance in C++ could be public, private, or public. It could be confusing for a beginner to find out accessibility of members and objects of these classes. Though public inheritance is mostly used, especially if there are virtual functions in the base class, other two types of inheritance have their uses as well. Here's an example program to make it clear how the 3 of them work i.e. public inheritance, private inheritance, and protected inheritance.



#include

class B{
char a;

public:
char b;

protected:
char c;
};

// public inheritance

class D:public B{

// private members of B can't be accessed
//can access public and protected members of B

char d;

public:

void f(){
//can't do this
// d = a;

d = b; // works
d = c; // works
}

// class D has the following additional members inherited from B
// public: char b
// and
// protected: char c
// this means that any class derived from D can access both b and c
// b is accessible by objects of derived class, c is not (#1)
};

// private inheritance

class E:private B{

// private members of B can't be accessed...
// can access public and protected members of B

char d;

public:
void f(){
//can't do this
// d = a;
d = b; // works
d = c; // works
}


// class E has the following additional data members inherited from B
// private:char b
// and
// private: char c
// this means that any class derived from E can't access any of the above derived data
// members, nor are they accessible to objects of derived class, public functions
// though are accessible to objects of this class (#2)

};

// protected inheritance

class F:protected B{

// private members of B can't be accessed in this class as above, so
// can access public and protected members of B

char d;

public:

void f(){
//can't do this
// d = a;
d = b; // works
d = c; // works
}

// class F has following additional members inherited from B
// protected:char b
// and
// protected: char c
// this means that any class derived from F can access
// the above members, but they can't be accessed from
// derived class objects (#3)
};

class DF: public F{
char d;

public:
void g(){
d = b; // works from #3 above
d = c; // works from #3
}
};



int main(){

char i;

B b;
D d;
E e;
F f;

// these won't work by definition
// b.c = i;
// b.a = i;


// for object d of publicly derived class
// this works from (#1)
d.b = i;
// this won't work from (#1)
// d.c = i;


// for object e of privately derived class
// these won't work from (#2)
// e.b = i;
// e.c = i;


// for object f of protected-ly derived class
// these won't work from (#3)
// f.b = i;
// f.c = i;

return 0;
}

Sunday, October 26, 2008

Small company or MNC

One of my friends has recently graduated and is in a dilemma on which among the two offers to accept. An offer he has is from a multi-billion, multi-thousand-employees product MNC where he would be using C language and Unix at work that is about debugging one of the company products. The other offer is from a small EDA company where he would be using C++ and Windows as a developer of EDA tools for engineers. The smaller company has less than 50 people on roll. The CEO himself interviewed my friend and has suggested that the friend would have more opportunities to learn and grow in a smaller company like his one.

On the other hand, the big MNC's salary offer is more than twice that of the smaller company's.

Friend is in a dilemma and is seeking my advice. Which company should he join?

Friday, October 24, 2008

pointer pitfall

Some C pointer fundamentals manage to fox even seasoned programmers.
For example, what is wrong with the following piece of code:

func() {

char *c;
c = "this is a string.";
*c = 'T';
printf("%s", c);
}


The code tries to capitalize the first letter of the string. It looks correct at first glance, but is not. It might even compile without any error, but will throw out an error when run.

Wednesday, November 28, 2007

Fun with JavaScript

This is a JavaScript I found while stumbling.
It works like this. Just search for an image in Google. Once it shows up images as the result of your search, enter the script (without quotes) in the address bar of your browser. It will rotate the images around. If you keep pressing enter again and again, the speed of rotation keeps increasing as well.

Thursday, August 9, 2007

UltraSparc T2 : Mainframe-on-a-chip?

In my previous post, I wondered whether Niagara 2 (ULtraSparc T2) could run 64 different OS instances or were they just Solaris Zones (containers). It is confirmed that it could indeed run 64 OS instances using LDom built-in technology in T2. I found this Sun blog post that demonstrates 64 instances of Solaris running in 64 T2 threads. In another post it goes further and shows Solaris and Ubuntu running simultaneously. That makes T2 one helluva multicore chip!

Steps to install PyTorch on VMware workstation (Ubuntu guest)

  The following is the list of steps to install pytorch 2.0 in VMware workstation (Ubuntu guest): $ mkdir ~/pytorch $ mkdir ~/pytorch/as...