Augustus Franklin's Blog

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.

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

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/  ]

A solution to every software problem must have two characteristics, it must be correct and and it must be efficient. One of the most important steps of solving a problem is to model the problem. A good software model of the problem determines how the problem gets solved and how efficient the solution is. Right modelling requires a good knowledge of software techniques and tools.

An engineer with good knowledge of data structures and algorithm techniques should be able to the model a single problem in multiple different ways, be able to see the trade-offs in the different models and pick a model using which the problem can be solved. Once the model has been decided, then a variety of tools can be used to implement the solution.

Here is a example. Facebook lists a variety of problems in their puzzles page that is ordered by how hard it is to solve the puzzle. Let us look at one of the hardest puzzles,  "FaceBull". The problem is to find the cheapest way to produce all the chemical compounds needed for the new super-energy drink from any single source compound. How would you model this problem?

Let each compound to be a vertex of a graph. There will be a edge between any two compounds, when there is machine that converts one compound to another. The weight of this edge is the cost of acquiring the machine that does the conversion. Let us draw this graph with the example input given in the problem.

Now in this model, the problem becomes, starting from any vertex find a path with the minimum cost that visits every vertex of this graph atleast once. This is a variation of the classic traveling salesman problem(TSP). Traveling salesman problem is a NP-complete problem. No wonder Facebook marked this as a hard problem.

We have identified a well known and well studied problem. The brute force approach to solve the problem is in the order of O(n!), where n is the number of vertices. It will take years for such a program to complete for just 20 vertices. Although it is difficult to solve TSP and to find the optimal solution for all inputs, there are many heuristics and approximation algorithms that will give a solution that is close to the optimal solution.

Notice how we transformed a chemical industry application problem into a well studied computer science problem with the right modelling.

When Nick and Thorsten were visiting the bayarea for Open HA Cluster Summit, we talked about some of the difficult problems in Solaris Cluster and how we may model them. This is one of the exciting aspects of working at Sun and at Solaris Cluster. There are many difficult problems to solve and people are eager to solve it. I  love the opportunity that every difficult problem presents. Stay tuned, we are just getting started.

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

Two years back I led and designed a project to make Solaris Cluster easy to use. The wizards that resulted from this effort is a key element of the Solaris Cluster user experience now. Many new projects want their features supported using the wizards today. The architecture of the project even made it to the IEEE Cluster conference.

This past year I led another important effort for Solaris Cluster. This feature, Shared Nothing Storage, that was released as part of Open HA Cluster 2009.06 removed a major hardware requirement for the cluster: the necessity to have a shared storage. This was achieved by configuring the iSCSI protocol stack present in COMSTAR in a particular fashion and layering a ZFS mirror on top. This feature allows a user to use any local disk present in the system as a storage for the service and to make that service highly available. There is no need to turn disk fencing on for this configuration and therefore it also removes the need to have SCSI reservations. Here is a picture of the configuration, with detailed configuration instructions here.

The key challenge in providing this feature was to make the cluster device subsystem robust enough to handle devices that are attached via the network. The design details are present here.

This configuration becomes more interesting when I/O multipathing is configured, because it shows the flexibility and the power of the COMSTAR architecture. With COMSTAR, a single logical unit of storage can be accessed via multiple port providers, multiple iSCSI targets in this case. These multiple iSCSI targets can be used to create multiple paths to the same logical unit. This provides fast mirroring of data in the cluster configuration. If you want to understand the different configurations with multi-pathing, Aaron Dailey and Scott Tracy have a excellent white paper on using MPxIO on Solaris. Here is a picture of the cluster configuration with I/O multipathing.

 Try it out. Join the discussions at ha-clusters-discuss@opensolaris.org

San Francisco is a charming city. The best time to be at San Francisco is early in the morning to see the city wake up. The marathon starts at 5:30AM in the morning. I started running around 6:00AM. It was a nice cool weather of about 54 Fahrenheit . I did not have to use my home-made non-organic jacket, the garbage bag. The first sign that breakfast was ready was around Mile 1. The aroma of fresh baked bread from Boudin made every runner around me gasp, as if we could breathe the calories into us!  

We ran through Crissy Field to the Golden Gate Bridge. This was the first real hill of the course. Rajeev and I decided to slow our pace slightly. It was a good idea to hold off a bit at this time. Once we were on the bridge, the course became very crowded. We had to run around many people, speed up at some places and slow down at others. With all this going on, it was easy to forget to look at the mile markers or worry about the hill. I missed all the mile markers on the bridge and I saw mile marker 10 after we came off the bridge. This turned out to be good because we did those 5 miles at a faster speed than what we had planned. After the bridge, there is another hill. I remember coming down from that hill the most, because that was a steep down hill and it was also my fastest mile of the entire course, Mile 11.

 I had lost Rajeev in the crowd on the bridge, he then caught up with me between mile 10 and 11. From that point, we got into good rhythm and breezed through the next 7 miles at a consistent pace. The first half marathon runners finished at mile 13 and the second half marathon had not started when we crossed, so the number of runners reduced after mile 13. At mile 18, Rajeev said that real marathon starts now. That was so true, this is where all the training and mental preparation really helps.

Rajeev had to slow down a bit to adjust his shoe laces around mile 19 and I was waiting for him to catch up again, as he did at the bridge, but that did not happen till the end of race. Mile 21 is another easy mile at the race. It is all down-hill and I got my second fastest mile after mile 11. At Mile 24 my body was all ready to give up, but I do not know what kept my legs moving. The next mile was the slowest mile of the race for me. After Mile 25, there is small jump to get on to the sidewalk along Embarcedero road, the last mile is mostly on concrete. The Bay Bridge acted as a homing beacon to the finish line and it was just awesome feeling to complete the marathon in my best ever time.

 The marathon was perfect in many aspects. I had very positive and encouraging training partners through this season. The weather on the day was good, it was a cool and cloudy through out the race, with not a hint of sun. The best of all, I had my running mentor pacing me and looking out for me through 18 toughest miles of the course. It is for days like this that I run. What a wonderful day!

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

It looks like there is interest in the long run schedules that I am posting here. The long runs for the month of June is critical to the training for the San Francisco marathon. This month contains 2 of the 3 long runs that will be over 18 miles. Long runs over 18 miles are important endurance training runs for a marathon.

June 7th	17 miles
June 14th	12 miles
June 21st	19 miles
June 28th	20 miles

Have you seen the Adidas Ads, "Runners, Yeah We're Different". These are good.

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.

If you have been following my long run schedule to train for the San Francisco marathon 2008. Here is the schedule for the month of May.

May 3rd	10 miles
May 10th	12 miles
May 17th	14 miles
May 24th	10 miles
May 31th	16 miles

 It is also a good idea to start doing some speed workouts at this time. Speed workouts help in the long runs by increasing the efficiency at which your muscles burn oxygen. The efficiency of the body to use oxygen is measured using VO₂ max. You can use the McMillan's running calculator to determine the optimal speed at which you can get the maximum benefit of a speed workout.

Update: Corrected the mileage for May 3rd.