Friday Apr 09, 2010

Farewell

After about 10 years at Sun and thus Oracle, I have decided to leave Oracle 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 have relocated this blog to http://afdiraviam.wordpress.com/


Monday Oct 26, 2009

Facebull Problem Definition

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.

  • The given graph is a weighted strongly connected directed graph, because every vertex can be reached from any other vertex.
  • The given graph need not be a fully connected graph, because every pair of vertices need not have a edge.

Now, the following are the unknowns,

  • We want to find the set of edges among the given set of edges, such that every vertex can still be reached from any other vertex.
  • When there are multiple such subsets, we want to find the subset that is the minimum weight sum of its edges.

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.

Tuesday Jul 28, 2009

Intellectual Dessert

"The excitement of learning separates youth from old age. As long as you're learning you're not old." - Rosalyn Yalow

One of my most enjoyable activity at Sun is to have "intellectual dessert". Intellectual Dessert is the name given to a series of regular talks and presentations in Sun on varied topics from experts in different fields. These talks provide opportunity for any Sun employee to interact with many smart people and know about work in other related areas. I have attended talks all the way from Rupert Sheldrake on his controversial morphic resonance theory, to talks by Turing award winners, like John McCarthy on the evolution of intelligence and Vinton Cerf on bit rot. Recently I enjoyed a talk by Nobel prize winner, Martin Perl on developing creativity in science.

I learnt recently that the talks at Palo Alto Research Center(PARC) is open to the public too. This is also a weekly forum with discussions on varied topics. The talk this Thursday is about the adventures of Cuil, a startup in the world of search engines. I plan to drive over to Palo Alto for my first visit to the PARC Forum.

Sunday Jun 28, 2009

Links for Crafting Software

As a practitioner of computer science and software engineering, I am always looking for opportunities to learn. I also consider learning from my peers valuable. Here are some interesting articles that I read recently.

  • API Design Matters
  • "The way to keep designers sharp and honest is to make them eat their own dog food. Any process that deprives designers of that feedback is ultimately doomed to failure."

    Joshua Bloch  has given a talk on the same topic. API design was also the cause of a tiff between James Gosling and Paul Buchheit sometime back.

  • A Conversation with Steve Bourne, Eric Allman, and Bryan Cantrill - Part1 & Part2
  • All three of them did their best work to write popular tools because they needed to use it. Notice how this validates the point that I highlighted from the previous article.

  • Real-World Concurrency

    The authors have a single system view of the world though. Many of the concurrency ideas presented also applies to programming in a distributed computing environment. Systems that run MapReduce and Hadoop like workloads could use these as well.

Partly because most of the links from ACM and the ACM Queue are useful and partly to heed to Bryan Cantrill's call to join ACM, I recently became a professional member of ACM. I invite you to join ACM as well.

[ cross posted at http://afdiraviam.wordpress.com/  ]

Tuesday Jul 08, 2008

Sometimes the snow comes down in June

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



Tuesday Jun 03, 2008

Keyhole Gardens

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.

Friday Apr 18, 2008

Earth is not highly available

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,

  1. Damage that people inadvertently inflict on their environment
  2. Natural climate change
  3. Hostile Neighbors
  4. Decreased support by friendly neighbors
  5. Society's responses to its problems

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.

Monday Mar 17, 2008

Economics of altruism?

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!

Monday Sep 10, 2007

Help me educate children

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.

Thursday Jul 05, 2007

Hello there!

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.
About

Augustus Franklin Diraviam works for the Solaris Cluster engineering group at Sun Microsystems. He lives in the San Francisco bay area.

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today
Bookmarks
Links

No bookmarks in folder

Blogroll

No bookmarks in folder