After about 10 years at Sun and thus Oracle, I have decided to leave Oracle to pursue other opportunities. Today, 9th April, is my last day.
My time at Sun was enjoyable. I will miss all the intelligent and friendly people at Sun. I hope Oracle and Solaris Cluster continue to do well in the future.
I will continue blogging here.
I mentioned earlier that the puzzle named “Facebull” in Facebook, is a variation of the traveling salesman problem. Let us define the facebull problem more formally and see if it is really true.
As I mentioned before, this problem can be modeled as a graph problem, where every chemical compound is a vertex and every machine is a directed edge in the graph. The cost of the machine is the weight of the edge in the graph. In this model, the following information is given in the problem definition.
Now, the following are the unknowns,
Thus facebull(FB) problem can be stated concisely as below.
Given a strongly connected directed graph G = (V, E) with vertex set V and weighted edge set E, find the strongly connected subgraph G’ = (V, E’), with E’ ⊆ E having minimum total weight.
The definition of a asymmetric travelling salesman problem(TSP) is as below.
Given a fully connected directed graph, find the minimum cost tour that visits every vertex exactly once and returns to the starting vertex.
A tour that visits every vertex of a graph exactly once is also known as a hamiltonian cycle.
Any fully connected graph is also strongly connected, so the inputs to TSP and FB could be the same graph. Usually in a real TSP the distances between the vertices are Euclidean distances, this is not true for the FB problem.
The main difference between the TSP and the FB problem is the unknown in the problem. In TSP, the unknown is a cycle in the graph. In FB problem, the unknown is a set of edges, with the only constraint that the resultant graph be strongly connected. Another key difference is, every time a edge is used in a TSP solution, a cost is added to the solution. However, a edge that is added to the FB solution is a machine that is bought and therefore could be used multiple times at no cost.
Finally, consider the computational complexity of TSP and the FB problem. TSP belongs to the class of NP-Hard problems, it is O(n!) in its worst case, where n is the number of vertices of the graph. For a graph of 12 nodes, the program must consider 12! = 479001600 possibilities. A brute force solution that considers all the possibilites for a graph of 20 nodes, will take many years to complete!
There are 2^m possible subsets of edges in a graph of m edges. Therefore, the complexity of FB is 2^m, where m is the number of edges of the graph. If the given graph is fully connected, m = n², where n is the number of nodes. Therefore FB is O(2^n²) is its worst case. For a graph of 12 nodes, a solution to FB must consider 22300745198530623141535718272648361505980416 possibilites. O(2^n²) is worse than O(n!). FB is a harder problem than TSP!
Another way of saying this is, the size of the search space for a FB solution is 2^m. The solution can be any where within that space, so any correct algorithm must guarantee to be able to find the solution any where in that space. An algorithm can restrict the size of its search space, but only if it can prove that the solution cannot be in the unsearched area. I will talk more about some of these pruning techniques in a future blog entry.
[cross posted from my Sun Blog]
June was a good busy month. The source code to Solaris Cluster was open sourced late May. We have been seeing some excitement from universities so far. See here, here and here. There is great technology here that is accessible to everyone now.
My fun at home became "highly available" with the arrival of my second son, Dalvin Jonan Diraviam, in the last week of June. It is pretty exciting to see nature at its best.
The marathon training for the San Francisco marathon is in its final month now. Julianne joined our long runs couple of times. She is a experienced runner and it was great fun to run with her. Here is the long run schedule for July. Sorry about the delay in posting this. This is the last one, you are ready for the marathon after this. Good luck.
| July 5th | 13 miles |
| July 12th | 22 miles |
| July 19th | 13 miles |
| July 26th | 6 miles |
They are round gardens of about two metres in diameter and raised to
waist-height to make them easy for the sick and elderly to work. Inside, the garden-beds are layered with tin cans, mulch and
ash which together provide the nutrients to make the gardens
extraordinarily productive.
Here is the full article. As they say, necessity is the mother of invention.
Many have reviewed the popular Jared Diamond’s book, Guns, Germs and Steel. It is a good book that talks about the history of humankind and provides broad explanations for the direction in which different parts of the world have evolved.
There is a slightly less popular but equally engaging book by the same author called Collapse. Collapse is a effort to understand the reasons why certain societies of the world collapsed. Jared says that there are five major causes why societies collapse. They are,
It pains me to hear about people eating mud to survive in our times. Human population is straining the resources of the earth. If Gaia hypothesis is true, then earth will just realign itself to a newer equilibrium. There are multiple causes at play that has lead to this food crisis, but it is our responses to these problems that will define our future. What am I doing about it ? For starters, I am reducing my consumption to only what I really need. Stop wasting resources that are at my disposal.
If you like behavioral economics, this article titled, "What Makes People Give?" is a nice read. I wish I had read some of these reports before I tried my hand at fund-raising last year. My only peeve with the article is that there are no links to the formalized studies by John List and Dean Karlan. It would be nice to look into the research studies in more detail.
Freakonomics by Steven D. Levitt and Stephen J. Dubner is another good read on behavioral economics. I read this book last year based on James’s recommendation.
By the way, what is it between apples and these economists!
There are certain things in life that give me great pleasure. Among the top is intellectual stimulation. My job provides me with plenty of those. Another aspect that is almost as good is, when I help someone and see their eyes light up. You have to be physically close to the person that you are helping to see that. It could be any kind of help. Teaching someone the way something works; helping someone see a familiar situation in a new perspective; providing a helping hand to someone slipping down a hill. It is the same feeling, the feeling of doing good. It is the discovery of the exact value of your action to the receiver.
There is a problem with this, it is the problem of scale. The problem with enjoying the feeling of altruism is that it is not always possible to be physically close to the person that you want to help. so what do you do ? I try to find a organization that I can trust, a organization that has a similar goal. I have recently chosen a cause which has the greatest impact, the cause of educating children. Say what you will about people that are poor, but the children of the under-priviledged cannot go to school because they do not have a choice. They are on the path of withering away without even an opportunity to succeed. That is not right. I intend to fight to change it.
People have dedicated their life for a cause that they believe in, I am just running a marathon. I want to make a difference to these children’s lives. I want to see the light in their eyes. I want to visit the school at Pune to see the effect. If I do, I will provide a complete report, I promise. Join me in this cause and support my marathon. Let us make a child smile with gratitude. It will change their lives forever, guaranteed.
This is my second try at blogging. I am from the Solaris Cluster engineering team. With Solaris Cluster’s plans to go open source, now is a good time to start a conversation.
Here is a little bit about me. I have been working in the area of systems, OS and network management since 1998. My contributions to Solaris Cluster are in the management area. In the recent release, I was involved in the architecture and design of the configuration wizards for Solaris Cluster.
Blogarithm 