Notes from ISCA - ACLD 2009 Workshop

Jim Larus from Microsoft Research gave a nice overview of their research in the large datacenter space. He pointed out the problem of limited bisection bandwidth and how that prevents applications from running across clusters. Microsoft is working on a mesh network called Monsoon connecting adjacent datacenters. Besides the mesh network, two of the key ideas in Monsoon are Valiant Load Balancing and source routing. Source routing keeps the switches simple and largely stateless and avoid hot spots. Mike Foss from Rice who presented a poster later also was working on something similar in principle that employed source routing to its advantage.

Another problem that Jim mentioned of which I heard about in several other peoples' research was putting idle machines into a low energy sleep state in order to conserve power. There are interesting challenges here. For instance, a network packet or a timer interrupt is sufficient for "disturbing" the sleep of conventional operating systems. Tickless linux solves part of the problem. For the networking part of the problem, someone is working on a microcontroller that can address most of the stuff without involving the processor. Others were working on disabling ethernet ports.

A direction MSR is exploring is "self-aware" and "self-managing" grid applications which automatically reconfigure themselves based on input and SLA requirements. It was great to hear that Jim's team is thinking about this problem since I've been thinking about this for a while myself and I should read up more on MSR's publications in this area. Ben Sigelman from Google pointed out later in the session how this is a hard problem in general and there are less powerful but practical alternatives (like visualization).

Also, Jim was very optimistic about PCM (Phase Change Memory) as a more scalable and efficient alternative to FLASH. PRAM is quite expensive today but Jim felt it was a matter of time before it was cost effective. Chuck Thacker from MSR also later showed some confidence in PCM but did not quite share Jim's enthusiasm.

This also came up in the next talk by Sarah Bird, who is a grad student at UCB about hardware performance counters. Sarah's research deals with providing a single consistent view across all the many performance counters in a multicore machine + adding many multicore specific counters to the hardware -- and doing this all in a standard way across platforms. Ben Sigelman pointed out that integrating this information with a distributed tracing service might be useful. Sarah also talked about the Autotuning project they are working on at Berkeley. Several people in the audience pointed out that adding new hardware support is a bad idea. But Sarah pointed out to a previous project (PAPI) that aimed to solve the same problem in software was a failure.

This was followed the poster session. The next speaker was Richard Kaufman from HP Labs. Richard's point of view was that of a server supplier as compared to MSR's make-your-own-servers. So he cited several general purpose trends in power and datacenter design.

The final speaker was the Chuck Thacker. He presented the case for modular datacenters based on containers, several of which will be deployed in a "parking lot" type datacenter. He gave a good high level overview of the technology required, including left to right cooling, network switches, and rack space considerations. In response to an audience question, he seemed to be pretty determined not to violate the absolute symmetry in the system -- all containers are meant to be equal, so you cannot have special containers with high level network switches for example. I found a nice overview of Chuck's talk here.

Beautiful post

http://www.nplusonemag.com/node/678/print

C++ super simplified

Caution: This blog post is the result of a long and boring flight. Also, my "C++ age" is little over an year, same being true for Python as well.

In the beginning there was C. C has a statically typed system which the compiler uses to verify type safety at compile time. It is possible to evade type checking by making raw memory accesses, but it's rarely a good idea to do so. Compare this with Python. In Python, type checking happens at runtime. It is type safe, but you find out violations only at runtime.

A language's type system allows you to write code to an interface. Programming to an interface allows different components of a system to evolve separately, one can be changed without affecting the other. However, different languages, or specifically C, C++, and Python differ in how the interface is enforced.

In traditional C, all code is checked against a predefined interface. It is generally tough to alter implementations without affecting multiple components or breaking the interface. Function pointers offer one way of doing this but the language lacks features to expose their full potential to the programmer.

C++ formalizes and streamlines function pointers using polymorphism. Polymorphism allows multiple implementations of the same interface. The different implementations can be attached to an object at runtime and they are all type-safe since the compiler verified it so at compile time. Thus, C++ increases the life of an interface and improves isolation between components.

This in some ways is similar to Python's dynamic typing. Python programs are written to an implicit interface which provides maximum isolation between components and expands the possible implementations of an interface.

For example, consider the following piece of Python code:

def fn(arg1, arg2):

if (arg1.valid) {

    return arg1.x;

} else {

    return arg2.y;
}

This method is programmed to an implicit interface of arg1 and arg2, viz., that arg1 have fields 'valid' and 'x', and arg2 have field 'y'. Beyond that it doesn't care about what else is inside arg1 and arg2. Furthermore, it can accept far more implementations of arg1 and arg2 than say similar C code.

This fashion of defining interfaces between components is definitely more generic than polymorphism in C++. In particular, it allows for a richer set of objects to be passed between components (and hence improves component isolation ?).

Fortunately, C++ provides a similar framework, viz., templates. A template is essentially programmed to the implicit interface of the template parameters. Just like Python, the C++ compiler does not care about properties of objects outside of those used in the template code. Still, the compiler verifies that the implicit interface used in the template is valid for each instantiation of the template (strictly speaking, it is possible to "control" C++ type checking of template code using various tricks, e.g., by offloading the checking to compile time (this->...) or by "using the using directive". See Scott Meyers Item #43 for details).

So, C++ does come close to Python's implicit interfaces and dynamic typing with features such as templates and polymorphism, albeit with their syntactic weirdness. Well, that explains most of C++, except "overloading" of course. I assert that the sole purpose of overloading is to facilitate template programming. All other uses of overloading can be attributed to programmer laziness (aka convenience). For example, consider the following code snippet.

struct A {

    int x;

};

struct B {

    int y[10];

};

template <>

void fn(A_or_B arg, others) {

if (/* found A */) {

    arg.x = 10;

} else if (/* found B */) {

    arg.y[0] = 10;

}

Will this compile ? No. Is this something you may want to do ? Maybe. The solution (to make it compile) is to use overloading.

template <>

void fn(A_or_B arg, others) { do_fn(arg); }

void do_fn(A arg) { arg.x = 10; }

void do_fn(B arg) { arg.y[0] = 10; }

Since all code inside a template must adher to the *same* implicit interface, an object whose implicit interface is a proper subset of the template's implicit interface may not compile even though the usage is logically correct. The solution is make the template's implicit interface the intersection of implicit interfaces of all possible type arguments and move type-specific code into overloaded methods/classes.

Code Coverage and KLEE from OSDI 2008

I once wrote a coverage tool that randomly replaced function calls at runtime with one of the many values assumed by the output of the call (as determined at compile time). I did this for "well tested" systems code and was pleasantly surprised by the number of bugs it discovered, especially on error paths. Of course, the number of false positives was rather high as well, and replacing entire function calls doesn't always work either.

A more "correct" approach, one with zero false positives, is to have the programmer inject faults in the code, perhaps randomly thereby forcing error paths to be taken. This still requires executing the code in development environments in order to trigger a whole lot of code paths. Also, there is a trade-off between coverage and code readability.

An intermediate approach is to do symbolic execution of the code and ensure that all code paths are taken for all possible program inputs. That right there is an intractable problem for path space can be infinite and input unknown and hard to model. The paper by Cristian Cadar et al on "KLEE" at OSDI 2008 describes a "new symbolic execution tool capable of automatically generating tests that achieve high coverage on a diverse set of complex and environmentall intensive programs". KLEE manages to get a handle on both, the path explosion problem and the "environment problem".

Symbolic execution isn't new. What KLEE does differently is optimizing the constraint set in order to speed up constraint satisfiability tests upon each "unsafe" access (viz., pointer dereferences, asserts, etc.). But first, let's take a step back and look at KLEE's architecture which I find cooler than icecream.

KLEE is modeled as an operating system for symbolic processes. Each symbolic process is incharge of a code path currently being explored by KLEE, and contains a register file, stack, heap, program counter, and path condition - state typically associated with a "real" process on a "real" operating system. Just like a "real" operating system picks up one among several competing processes for scheduling, KLEE's scheduler picks up a symbolic process amongst many for symbolic-execution. Of course, KLEE's "scheduler" has a different goal than a real OS's scheduler. KLEE's scheduler's goal is to run those symbolic processes that are likely to offer biggest improvements in coverage. Each symbolic-process (called "state" in KLEE lingo) has a current set of constraints on the environment, which must be met for the current path to be reached. If KLEE detects a violation in the constraint set, it triggers an error and generates a test case.

Apparently, KLEE is a total rewrite of another tool by the same research group (EXE) which I'm not familiar with. But the interesting part is that in EXE's case, the individual processes were real operating system processes. Hmmm...

Symbolic execution of even small problems can result in path explosion thereby limiting the chances of finding true bugs. Moreover, most constraint solvers (KLEE uses STP) take quite a bit of time as well. KLEE's approach is to optimize away large parts of the state of each symbolic-process before the constraints are passed on to the solver. This alone reduced the running time of an example in the paper by more than an order of magnitude. More importantly, they show how the running of KLEE using their optimizations is nearly linear in the lines of code as compared to super-linear without the optimizations. Also, even with all the optimizations, KLEE does not sacrifice accuracy, so it never reports false positives - which is one of the key benefits of using a symbolic executor over other program analysis methods IMHO.

Additionally, they use some cool tricks in picking which symbolic-processes to execute in order to maximize coverage. For example, KLEE favors scheduling paths which are high up in the code tree, since they are likely to expose more unique paths.

The other trick used by KLEE is environment modelling. Instead of requiring the environment to be concretely specified, users can create models for the environment, written in proper C code. During (symbolic) execution, the model can generate inputs and error conditions. I did not get a good handle on the usefulness of environment modelling though, so don't know how powerful it is in practice.

Overall, it seems like a pretty good value proposition from a programmer point of view. Zero false positives, benefits proportional to analysis time (KLEE allows you to specify how long should it run and it uses that to optimize its scheduling behavior), and improved code coverage all seem like useful features. I wonder when these features will be available in some open source package, or how much does one have to pay Coverity for this.

Emails Are Forever

I don't know about you but the way I access my emails is almost always through the Gmail search box, whether I'm looking for that email about someone's flashy new job (since I forgot where they are working) or my todo list from last week.  And that's primarily because of the amount and nature of data in my Gmail.  All the communication of any consequence is reflected in emails (including facebook, orkut scraps), and additionally I've moved a lot of note taking to Gmail as well - implemented by sending an email to myself.

With so much of my life depending on my online existence, I'm getting a bit paranoid about several what if scenarios, like what if the online servicing maintaining my data goes bankrupt, etc.  Of course my case is not unique.  Millions of people worldwide have a lot of precious data sitting on computers spread out across the world, owned by a foreign corporation, and supported free of charge (e.g., free Gmail is partially supported by Google's online ads revenue).  But assuming some of this data will remain as valuable to me a decade or two later, I'd like to ensure that I don't leave all of it to the vagaries of a ticker symbol.

Maybe you would argue that Google and Yahoo and Microsoft are not going away anytime soon and I believe you.  But less than 20% of firms that existed two decades back are still around, so that increases the odds against your hypothesis.  Another possible argument is that a product getting phased out doesn't necessarily imply that user data will be lost (e.g., Yahoo photos to Flickr), maybe user data will become all the more precious over time.  Still, I'd argue that the expected lifetime of your present online data will only go down over time.  So the big question is do you care enough about _all_ that data or not.  In my case, I care about most of it.

A poor man's solution is to immortalize your data is to periodically "download" and archive it at your home or better still at another online service.  Of course, switching services may affect the usability of the data, which affects its value to you.  E.g., if I zipped all my Gmail into one single archive, I can't search freely like before.  It may still be useful for litigation purposes but not for looking up my roommate's phone number.  This brings us to the first rule:

1.  When archiving your data, the functionality supported by the archived data should be comparable to the primary copy's functionality.  If not, it will probably be forgotten.

A more difficult problem for me is figuring out _where_ to archive or move my data, making the decision, verifying that it worked, etc.  This is potentially very time consuming.  So what I'd want to see is a computer "program" that will keep track of the service level trends for your current data provider, monitors/evaluates upcoming alternative services, and replicates your data across a "diverse portfolio" of service providers, so over time your data is likely to survive somewhere - and almost always it can be found on the new and upcoming service.

It may seem that I just borrowed a dialog from Star Trek and I can understand your sentiment.  Some key components that will be needed to create such a "program" include:

• A service for evaluating and recommending data service providers.
• A data API supported by different data service providers that enables easy migration between them.  For example, if you must migrate a photo sharing service to an email provider, you'd probably store a single photo album as a single email.  Someone will have to write such interfaces for all new services.

Before I conclude, I'd like to observe that this problem is similar to money management.  When you give your money to a money management firm, you expect them to keep reinvesting it in the most appropriate business presently.  Maybe that is too complex to delegate fully to a program, but I think keeping your data up and running forever should be simpler.

Essays of Warren Buffet... Chapter 2

This chapter begins with the most useful concept in value investing - Mr. Market, originally introduced by Ben Graham. In Buffet's words:


"You should imagine market quoatations as coming from a remarkably accommodating fellow named Mr. Market... Even though the business that the two of you own may have economic characteristics that are stable, Mr. Market's quotations are anything but. For, sad to say, the poor fellow has incurable emotional problems. At times he feels euphoric and can see only the favorable factors affecting the business. When in that mood, he names a very high buy-sell price because he fears that you will snap up his interest and rob him of imminent gains. At other times he is manic depressive and can see nothing but trouble ahead for both the business and the world. One these occasions, he will name a very low price, since he is terrified that you will unload your interest on him."


And now the killer:


"Mr. Market has another endearing characteristic: He doesn't mind being ignored. If his quotation is uninteresting to you today, he will be back with a new one tomorrow. Transactions are strictly at your option. Under these conditions, the more manic-depressive his behavior, the better for you... Mr. Market is there to serve you, not to guide you. It is his pocketbook, not his wisdom that you will find useful."


Buffet quotes Ben Graham again on the issue of holding: "In the short run, the market is a voting machine but in the long run it is a weighing machine." According to Buffet, the speed at which a business's success is recognized, is not that important as long as the company's intrinsic value is increasing at a satisfactory rate. In fact, delayed recognition can be an advantage: It may give us the chance to buy more of a good thing at a bargain price.


Buffet elaborates a bit on how he generally resists selling when the price is high which he contrasts with Wall Street attitude of: "You can't go break taking a profit". He explains that he is quite content to hold so long as the prospective return on equity capital of the underlying business is satisfactory. He doesn't explain this much further except for quoting David Ogilvy: "Develop your eccentricities while you are young. That way when you get old, people won't think you are going ga-ga".


The next section is an interesting one. Here Buffet talks about how a successful investor gets happier to see stocks falling. He poses a simple question: "If you expect to be net saver during the next five years, should you hope for a higher or lower stock market" ? "Even though people are going to be net buyers of stocks for many years to come, they are elated when stock prices rise and depressed when they fall. In effect, they rejoice becauses prices have risen for the "hamburgers" they will be buying soon. This reaction makes no sense... So smile when you read a headline that says "Investors lose as stocks fall"".


Arbitrage.


The next essay is on Arbitrage. This section carries a few of Buffet's experiences making and losing money in arbitrage positions, especially "risk arbitrage".


Efficient Market Theory.


In the next essay, Buffet lambasts Efficient Market Theory (EMT)... "Observing correctly that the market was frequently efficient, they [academics] went on to conclude that it was always efficient. The difference between these propositions is night and day". Buffet akins this ideology as "not even trying" when it comes to evaluating business principles of prospective investments.


Portfolio concentration - Too much of a good thing can be wonderful.


Another interesting point in this essay is related to portfolio concentration. Buffet says "we believe that a policy of portfolio concentration may well decrease risk if it raises, as it should, both the intensity with which an investor thinks about a business and the comfort-level he must feel with its economic characterstics before buying into it". He explains that the difference between portfolion-diversification and portfoloio-concentration is really the difference in how risk is defined. Proponents of portfolio diversification define risk as the relative volatility of stock - that is, the volatility of the stock as compared to a larger universe of stocks. Under this definition, stocks whose prices have dropped severely are considered riskier. In contrast, the definition of risk accepted by proponents of portfolio concentration is from the point of view of the owner of business - "the possibility of loss or injury". I noticed that this is a recurring theme in the book - Buffet indeed thinks about his investments a lot like an owner rather than a speculator.


Buffet provides some guidance about how to evaluate risk. He cautions that these characteristics are often difficult to quantify, but that does not negate their importance:


1. The certainty with which long term economic characteristics of the business can be evaluated.
2. The certainty with which management can be evaluated...
3. The certainty with which management can be counted upon to channel the reward from the business to the shareholders rather than to themselves.
4. Purchase price,
5. Taxation, inflation, and competition.


Portfolio insurance.


Portfolio insurance is a money management strategy which dictates that ever-increasing portions of a stock portfolio, or their index future equivalents, be sold as prices decline. So, a downtick of a given magnitude produces a huge sell order. In fact, one popular corollary is to repurchase these companies, once the stock has rebounded significantly. Apparently, in the crash of October 1987, $60 to $90 billion of equities were offloaded on this hair trigger. Buffet concludes by saying that a smart investor only stands to benefit from such speculative acts of others. In fact, he can be hurt by such volatility only if he is forced, by either financial or psychological pressures, to sell at untoward times.


Value-investing: A redundancy.


This is well stated by these four rules. The business should be one (1) that you can understand, (2) with favorable long term prospects (durable competitive advantage), (3) operated by honest and competent people, (4) available at an attractive price.


When deciding what is an "attractive price", the Margin of Safety rules may come handy... "If we calculate the value of a common stock to be only slightly higher than its price, we're not interested in buying. We believe this margin-of-safety principle, so strongly emphasized by Ben Graham, to be the cornerstone of investment success".


Buffer believes that an intelligent investor buying common stocks will do better in secondary markets than he will do buying new issues. The favorable factor for secondary markets being Mr. Market. For new issues, Buffet mentions that issuing corporation has little incentive to undersell their stocks than its intrinsic value, since they can set the price and time the IPO.

Book: The Essays of Warren Buffet: Lessons for Corporate America

I recently finished reading "The Essays of Warren Buffet: Lessons for Coporate America". Given my thin knowledge of corporate finance, corporate governance, and investing, this book was quite useful. Over the next few posts I'll be presenting a few interesting ideas from the book. This first post is based on the first chapter.

Chapter 1 Corporate Governance

The chapter is mainly about Buffet's frustration with the top management of firms not owned by Berkshire and how things are different at Berkshire owned firms.

He starts with talking about the significance of full and fair disclosure of company performance. He doesn't approve of any company that highlights EBITDA (Earnings Before Interest, Taxes, Depreciations, and Amortization). He says that proponents of EBITDA argue that depreciation is not truly an expense, given that it is a "non-cash" charge. He offers a convincing counter-example: imagine that at the beginning of this year a company paid all of its employees for the next 10 years of service. In the following nine years, compensation would be a "non-cash" expense - a reduction of a prepaid compensation asset established this year. Would anyone care to argue that the recording of the expense in years 2 through 10 would simply be a bookkeeping fomality ? Buffet offers some more views on the significance of clear accounting. He finally sums up his views as follows: "We want our managers to think about what counts, and not how it is counted."

Buffer is quite critical about CEO performance and compensation. He believes that CEOs of many public companies get away with underperformance for two reasons. Fistly, there are no clear standards of CEO performance. And secondly, the system charged with monitoring the CEO - the board of directors - often doesn't do a good job. Buffet provides some interesting insights into who should and should not be in the board. According to him, a director must have 3 qualities: (1) business savvy, (2) interest in the company, and (3) care about the owners. The most important service a director can do is to watch the CEO, ensure that he/she is doing a good job, and fire the CEO asap if not. Regarding the CEO, Buffet says that his message to every CEO is to run the business as if (1) you own 100% of it, (2) it is the only asset in the world that you and your family have or will ever have, and (3) you can't sell or merge it for at least a century.

Even if you have the best management and best board, you can still come out a loser if there are issues with the line of business. Buffet cites the example of a very well managed company, Burlington textiles, that has yielded substantially below average returns over the past few decades. He : "If you want to get a reputation as a good businessman, be sure to get into a good business". He offers another handy quote about working too hard on terrible businesses: "A horseman that can count to ten is a remarkable horse - not a remarkable mathematician". Buffet has a large repository of handy quotes on this topic. For example, in Chapter 2 he cites "When a management with a reputation for brilliance tackles a business with a reputation for bad economics, it is the reputation of the business that remains intact".

In the last section of this chapter, flaws in options based compensation and how that corrupts CEO performance. Buffet argues that if a midly profitable company reinvests its earnings (instead of giving dividends), it can still maintain a pretty decent stock price growth over time assuming a constant PE ratio. Consequently, managers will reap good profits from the fixed-price stock options they received when starting, even though they have merely sustained the company's slow growth. Buffet suggests that cash bonuses have all the same merits as stock options since the managers can use it to buy as much stock as they want from the open market.

Sources of Power

Interesting points from Sources of Power - How People Make Decisions, by Gary Klein.

The author tries to avoid advocating any single approach towards decision making, but instead studies how people make decisions in various circumstances. Knowledge of decision making in field is at least one take away from the book. Besides that the author analyzes the decision making process based entirely on rigorous research of real people and circumstances and presents his results. It's up to the user to draw any strong inferences or lessons from these results. The author simply ensures that the research is rigorous and relevant.

I've only read first half of the book so far. The book begins by dispelling the common belief that most decision making is comparative analysis based. In reality, most decisions, and important ones (examples cited are from military, fire fighters, ICU nurses, etc.), are of type RPD (Recognition Primed Decision). These are decisions which are essentially sequential in nature where the decision maker considers a list of options sequentially and picks the first one he likes. In fact, most such decision makers believe that they are not actually making a decision. In contrast, most outside observers get the impression that the decision maker actually made a "decision" (meaning decided based on comparative analysis).

According to author's survey of few hundred important decisions taken by individuals in serious and/or time-pressure circumstances about 80% fall into the RPD category. There are several scenarios where RPD is not the primary decision process, e.g., RPD is based on recognition for which an essential requirement is subject expertise. So when novices are making decisions they tend to be more comparative analysis based than RPD. Similarly, when the decision needs to be justified, e.g., to a higher authority, comparative analysis based decisions are more common. There are several other interesting statistics in the book regarding how the contribution of different decision making approaches varies by scenario.

Once the plenitude of RPD is established, the book delves into the details of how RPD works and what are the various components of the RPD process. Probably the most significant model the book introduces is that of simulation. Simulation is useful in two scenarios:

1. In the scenario recongnition phase where the available data is matched with past experience to decide which scenario we are in. Simulation helps by arranging and explaning a set of sequence of events such that the end result is the current scenario. This knowledge of the past, or what brought us here, is often critical in deciding where we are headed in the future. The author also introduces the notion of "expectancies" - once a simulation has been made to arrive at our current position, the decision maker can generate a set of expectancies and watch out for them in the future. If certain expectancies do not happen, or certain unexpected things keep happening, then that might be a good reason to worry that the simulation (and hence our perception of the current scenario and future) may be incorrect. The author amply illustrates this point using the example of the Libyan passenger airliner whose pilots failed to verify the expectancies, the fire fighter who figured that something was not right and pulled his team out of the house just before the entire first floor went crashing into the basement (he was not told that the house had a basement), etc.
   
2. Simulation is also fundamental in predicting and analyzing the effect of the decision. The power to do useful and realistic simulations can be very useful in making important decisions. Future simulation, like other aspects of RPD (like scenario recognition) require a good deal of experience. However, in most cases creative ideas can play an important role in the simulation - coming up with a creative insight into a problem and being able to simulate its effect can be very valuable in solving difficult problems. The author gives the example of the newborn baby with a blocked throat, the fire fighter who chose to make a rescue by removing the car's roof, etc.
   

The second half of the chapter on simulation is very interesting. Here the author makes some summary observations based on experiences drawn from different experiments. One of the topics covered here is about expertise. Who is an expert ? How do experts use and leverage simulation, etc. Here are some points:

• Experts are constantly improving themselves by doing simulations, mental or aided by paper, computer, etc.
• Pre-mortem (crystal ball). The author defines pre-mortem as the process of assuming that something failed even before actually doing it and then trying to figure out how the failure might have happened. In their experience, they found that pre-mortem often generates new/interesting insight into the problem. It's called the crystall ball approach also since a powerful analogy is that of looking at the future in a crystal ball and finding that something failed.
• Post-mortem. The author uses this concept in a more general sense. They do a postmortem of a task after the task but before results are out and then after results are out.
  
• An important trait of experts is the gut to doubt the data. This is highlighted using numerous examples throughout the book. The data available for making decisions may not always be accurate or timely. In such scenarios, the decision maker has to leverage his past experience not only for decision making, but also for weeding out inconsistencies in the data or outright doubting the data. In some ways, this is a higher form of expertise. There are several examples of this, e.g., the firefighter doubting their knowledge of the fire and pulling out the entire team before the floor collapsed into the basement, or the Naval ship crew not doubting the fact that a passenger airliner was emitting millitary frequencies making them believe that it's a millitary aircraft, etc.

The Vincennes shootdown is one of the classic examples of decision making going wrong under complex scenarios. The incident is but a combination of multiple smaller incidents and provides valuable insight into decision making. For one, half of the ship crew had already made up their mind that the object they are handling is really a missile and they were looking for reasons to justify it. This shows how individuals often make gut decisions subconsiously and then attempt to justify them by contorting evidence. Secondly, the ship crew did not doubt inconsistent, unlikely data, most importantly the millitary frequency coming from the passenger airliner was due to an error in placing the instrument, it was not double checked. Thirdly, it shows that under severe time pressure, better decision support systems are needed in order to avoid making wrong decisions, e.g., in this case better visualization and analysis tools.

Moments of genius

Dixie [sitting at front passenger's seat in SS's car talking to Rai sitting on back seat, the seat next to Rai is empty]: You know, many other people exist in higher dimensions, like the 11th dimension. For example, someone could be sitting right next to you at this very moment. [Looking at the empty seat next to Rai] Hello hi.

Dixie: Maybe you will run so fast, that you will walk on water.

Dixie: Let's discuss some new topics, like keeping quiet.

Dixie: You want to get high... eventually.

Dixie: You are wasting my _valuable_ time.

Pande: If you fly perpendicular to time, you'll find Floyd somewhere.

Dixie: We have three options, and the fourth option is ...

SS: Beauty lies in the eye of the upholder.

"Dixie: Kya khaun, heart attack khaun ki blood pressure khaun.
SS: Liver disease khao."

Dixie: Use your muscles... dead.

Rai: Dixie equals Airport Blvd equals Dixie.

Rai: Where is whose car ?

NLP based search

I am getting increasingly interested in Natural Language Processing (NLP) these days. NLP can enable better human computer interfaces, powerful search engines, etc. One of the search startups in this area that I have been following is www.powerset.com which was recently acquired by Microsoft. A good source to learn about powerset and a rought technical overview is at http://www.slate.com/id/2193837/.

Powerset's NLP technology breaks a sentence into smaller entities (nouns, verbs, adjectives, etc.) and establishes relationships between them, e.g., "eiffel tower was built in 1889" gets recorded as "eiffel tower" (noun) "built" (verb) 1889 (noun). Each such relationship (called "fact") is recorded and comprises a single quantum of information derived from the web page. A search query is translated into a similar, but incomplete fact, e.g., "when was eiffel tower constructed?" would become "eiffel tower" (noun), "constructed" (verb), and "when/year/time/date" (noun/adjective). The search algorithm then matches the "factualized" query to the closest resembling fact and fills in the missing details (the year 1889 in this case).

The cool thing about converting content and queries to facts is that the search engine can identify and return relationships not explicitly stated in the contents, unlike keyword based search. However, most popular content on the web is actually explicitly stated in a single sentence, so NLP seems less useful for searching popular content since Google search would already do a pretty good job here.

However, the real promise of NLP based search seems to be in the context of the "long tail" of search - which are frequently searches not explicity answered on any single web page. As the web continues to grow and many different kinds of contents come online (blogs, books, emails, etc.), the long tail of web search will continue to increase its share of the total search volume. Most of us have experienced that the unpopular searches often are not explicitly found in any single web page, instead they require the user to scan multiple web pages before they find what they want. Keyword based searching cannot make things any better here since the keywords may either be spread out across webpages or they may simply be absent (e.g., "dog" and "tommy" can be related if tommy is the name of a dog - a fact that keyword based search cannot discover). This is where NLP can really make a difference. It can identify facts from across web pages and save users valuable time spent scanning different web pages trying to forge an answer to their search queries.

So, very roughly speaking, if you can find the answer to your query in one Google search and after scanning 1-2 returned web pages, then NLP will not make things any better for you. If it takes more than one search and visiting 5+ search results to answer a given query, and if your query and its potential response can be formed into a fact, then NLP might be useful.

Another analogy for the applicability of NLP may be the information density of a web page. NLP will be more useful finding content in web pages with low information density. By converting the text to facts, NLP is in a way converting "semantic compression" of the contents. "NLP compressed facts", owing to their increased information density, are better suited to answer user queries. These "low information density" web pages may be web pages with lower page ranks on Google. Other examples of low density content might be casual chat sessions, email threads, etc.

Unfortunately, in my experience Powerset doesn't seem to be doing a good job in identifying complex facts. They do a decent job at identifying obvious or simple facts but based on some examples I saw, not so well for complex facts. For examle, if you search for "who was the author of the godfather", you get the answer "Mario Puzo". But Google also fairly easily gives you the same answer when you search for "Godfather author" or "Godfather writer". But if you query, "how many years did Mario Puzo take to write the godfather", Powerset doesn't seem to offer any useful results.

Also, I wonder if their algorithm can really connect information from across different websites, different paragraphs in the same web page (should be there I think), etc.

I'd conclude that for NLP search to be really useful, it should target the long tail of searches - searches which individually are an insignificant part of the total search volume but put together comprise a major chunk. Powerset NLP search doesn't seem to be there yet and quite likely neither do other existing NLP based searche engines.

Digital Planet May 20th

Not a very interesting episode except for the part on "Predicate Encryption". I think the seminal work in this area is http://eprint.iacr.org/2007/404

I don't understand how this is any different from general access control lists. True, since the data is encrypted, even if someone gets access to the entire data, they can only access the part they are authorized to access, but a software layer enforcing access control lists also essentially enforces the same semantics.

Digital Planet May 27

Listening to Digital Planet podcast for May 27th, I learned a few things:

1. Virtual worlds are more pervasive than I thought. Previously, I used to consider only Second Life as a virtual world and not social networking websites. But coming to think of it, there is significant overlap between the two, and for many reasons, people are creating new virtual worlds, often targeted to specific class of users, like young children, students, teens, etc. E.g., Lego Corp. has a virtual world where you can play with legos. BBC has one for kids, and so on. In fact there was a whole "Children in Virtual Worlds" conference that this edition focussed on. The podcast mainly discussed safety, "active moderation" (moderator is a character in the VW himself), "CCTV moderation" (moderators is outside but silently watching - considered a bad thing).

2. Another interesting item was the psychological analysis of friendships and relationships in the virtual world. The conclusion was that in a VW, like in a real world, friendships happen based on shared experiences. So, to create a "tighter" social network, you need more shared experiences - yes, it's all about the experience, shared ones.

The Far Away Tree Andaman Islands

Akshay Rawat, who is like a brother to me, has started a new venture in the place we both grew up and spent some of the most memorable years of our lives, Andamans. Check out his website at http://www.thefarawaytree.in

One week in Japan

I was in Tokyo for a week from March 23rd, 2008 afternoon to March 30th, 2008 afternoon. I stayed in Shibuya-ku (or simply Shibuya), which is located in the south western part of the city on the JR Yamanote line. Shibuya demographic is mostly young people and so it's not surprising that you'll find people on the streets very late in the night (2-3 am). My hotel, Hotel Cerulean Tower was hardly 200m from Shibuya station's west exit and offered a great view of the western part of the city from the window.

Train stations in Tokyo are quite big and there are many shops within the station complex. Sometimes it appears more like a mall where you can catch trains as well. Each station is shared by multiple train companies and often they share tracks too. Fortunately, it's easy to find your way around the train stations without knowing Japanese as all directions are written in English as well.

The Yamanote line is considered the single busiest train line in the world. This is partly because it's a giant loop connecting most of the key parts of Tokyo city (I think it has more than 30 stations), and partly because Tokyo itself is (probably) the most populous city in the whole world where statistically speaking, almost everyone commutes by train. As a tourist, most of the common attractions can be reached using the Yamanote line. It's advisable to purchase a "Suica" card, so that you don't have to buy a ticket for every trip. Perhaps the only annoying thing about Tokyo train system is that all trains stop at 12 midnight. Coupled with the extremely high taxi cab fares in Tokyo, it makes staying out late effectively infeasible, unless you only visit places in your neighborhood.

I spent the first few days of my stay totally engrossed in work. My breakfast was mostly pineapples served in our office every morning at 10 AM. I was told that fruits in Japan are quite expensive, just like beef and some other meat. Pork is cheap and fish is more so. Anyhow, I really enjoyed the pineapples which were quite tasty like the pineapples I have had in India (pineapples that you get in the U.S. are not as good).

Talking about food, Japanese don't really have much dessert of their own, you mostly get western style cakes and cookies. The funny part however is that the cake and other dessert are served in very tiny quantities. In our office, I ate probably the world's smallest cake. One might argue that it's healthy to eat less dessert, but not so much for most people as we simply ended up having five of those tiny pieces.

Japanese food is quite close to the nature, with very little processing. Fish is usually boiled and served along with rice and soup, and probably constitutes bulk of what Japanese eat. Probably this is why they didn't originally come up with lot of good dessert like Indians and French did because the latter two spend a lot of time processing food, so are more likely to produce great dessert.

Japanese restaurants are the symbol of efficiency. In a typical restaurant, several tables are joined together to complete a circle or rectangle. Customers sit on the outside of the tables. The kitchen may be located in the inside part where the chef cooks food right in front of everyone's eyes (which is good). If the circle is small, the chef can directly drop off the food into the customer's plate. Some places have a conveyor belt constantly running over all tables and the chef may simply drop the food in the conveyor belt for the appropriate customer to pick it up. Of course, if the restaurant doesn't receive enough customers to justify this elaborate affair, the kitchen may be kept separate and only the waiter walks in the space enclosed by the tables, serving each customer. The waiter ends up walking less which is probably good for him and for overall efficiency.

Enough about food. My first visit outside was to the Ebisu Garden Place which is a mall located close the Ebisu station on Yamanote line and is well known for its architecture. It was a brief lunch-time visit with colleagues. I spent a few evenings wandering around Shibuya and Shinjuku which is three stops from Shibuya on the Yamanote line, both places are known for having plenty of dining places. Once at Shinjuku, I asked for authentic Japanese food and was served live shrimps in my plate! Since then I stopped asking for authentic Japanese food.

At a Shinjuku restaurant, I also made friends with three cool Japanese people. Keiju Suzuki is an IT professional and a passionate motorcyclist (like myself) who enjoys long rides on weekends. Anna is the chef cum waitress who is a huge fan of Julia Roberts, and Hida who owns the place is an accomplished football player and is a pretty cool fellow.

On Thursday evening we all went to a nearby park [fill in name] for celebrating Hanami. Hanami is a traditional Japanese festival celebrating the arrival of spring marked by cherry blossoms. Typically, you get together with family and friends and spend time out eating and drinking at a park or other such location where you can spot some cherry blossoms. It was a great evening and I got some great shots of the cherry blossoms in the moonlight.

On Friday, I took off early from office and visited Yoyogi Park and the Meiji Jingu shrine. Yoyogi park is located near Harajuku station on Yamanote line (and not near the Yoyogi station as I first thought). Meiji Jingu was a highly regarded Japanese emperor (reign 1868 to 1912) who is credited to have ushered in the modern era in Japan. The Yoyogi park is quite big and one has to walk quite a bit to get to the shrine. The walk is quite enjoyable though, as it's lined with trees and Buddhist structures. There are also many narrow trails that you can take.

The shrine itself is very calm and serene. I spent about an hour relaxing there. It's a great feeling to sit on one of the benches close to the entrance and admire the shrine and its rich cultural history. There is a huge tree in the shrine premises and on a nice breezy day, it can all feel a little bit like heaven.

From Meiji Jingu I set off for Akihabara, which is the diagonally opposite end of the Yamanote line (Yamanote circle would be more appropriate). Akihabara is the electronic town in Tokyo. As such places usually go, it's somewhat crowded and haphazard. Nevertheless, I was quite intrigued by the many cellular phone and computer shops. For example, a simple looking cell phone with a touch senstive keypad, another one on which you can watch live television, pay for travel using an embedded chip which can be programmed to pay for many different services, and so on. Later during the week, going over my colleague and friend Frederic Beal's cell phone, I realized how far ahead Japan is in its mobile phone technology. Other examples include an amazingly useful transit app for cell phones, [try to remember more] etc. I noticed that most laptops and computers for sale came with a TV like remote control which make your laptop look indistinguishable from a TV. Also, I didn't see any computers using CRT monitors, everything was LCD.

The next morning (Saturday) I woke up early (6 am) and left for Nikko National Park. Frederic joined me at the south exit of Ikebukero station which became our meeting point thereafter given that I didn't have a cell phone. Nikko is less than two hours from Tokyo. It is a very old town located in the mountains. Nikko is historically significant for Japan since it is one of the first few places where Buddhism arrived and thrived in the country. It has many old Buddhist temples dating as far back as 766 A.D. There is a giant statue of Amida Buddha. At this point Frederic also explained to me the two main Buddhist sects prevailing in Japan (Shoda Bukya and Joda Bukya) and how they differ from each other and other sects of Buddhism outside of Japan. The temples are built on a small hill, so it's a nice walk up and down. The architecture is quite interesting, quite typical of a Buddhist monastery but unique in its fine metal work all over the entrance gates.

We had lunch at a traditional Japanese place in the Nikko town and took an early train back to Tokyo in order to beat the rush as we had seen a lot of tourists pouring in as the day progressed. We were quite enamored by the snow capped mountains engulfing Nikko and it reminded Frederic of his visits to the Swiss Alps. Frederic told me that Nikko receives snow as well and on one of his visits to Nikko during winter, the whole ground was covered with snow. We had Japanese beer on the way back (Asahi and Kirin) and I was slightly drowsy by the time we got back to Tokyo. The train trips although long were quite entertaining as we discussed our different ideas of the kind of companies we'd like to create and other stuff about Japan, France, and India.

I bid goodbye to Frederic at Ueno and on his suggestion went to the Ueno Park which is close to the station. It turned out to be the climax of my trip and an absolutely memorable experience. Earlier in the day, Frederic was telling me how there was no Japan at the end of WWII and how the Japanese people have come so far since then through their hard work and perseverance. I found the perfect testimony of their progress in the park. The park was full of people who were having a nice day out with family and friends. But the most memorable experience was a 200m walk through a trail that was fully lined on both sides with cherry blossoms. I sat by a side and dozed off for sometime as it was a perfect sunny day for doing so. It occurred to me that all the hard work, discipline, and sacrifices have been totally worth it for Japanese people as they rebuilt their country from ruins and have lived to enjoy this amazing day.

I left the park with the conclusion that "No tragedy is big enough". I came to the hotel and overslept, waking up very early next morning, doing sundry chores and checked out at 11AM. I met Frederic again at south exit of Ikebukero station. After roaming around for a while, we ate at a Japenese-European restaurant and followed it up with ice cream at Coldstone. I've never seen such a long line at Coldstone, which makes the JFK immigration line look minuscule. We went to a Yamaha music store where Frederic bought sheet music and also convinced me to start taking Piano lessons. Frederic, who is French, is an expert Clarinet player himself. So with that in mind, I said goodbye to him and Tokyo and left for Narita Airport.

Call me via jaxtr

Get jaxtr | Login

I'm alive

Events unfold so unpredictably, so unfairly, human happiness does not seem to be included in the design of creation. It is only we, with our capacity to love that give meaning to the indifferent universe. And yet, most human beings seem to have the ability to keep trying and even try to find joy from simple things, like their family, their work, and from the hope that future generations might understand more.

--Woody Allen

Trust Issues With CellSwapper

CellSwapper is a new service (http://www.cellswapper.com) that allows one to get out of a cell phone contract they are stuck with, without having to pay the termination fee (only paying a much smaller service fee). This is a cool service and will certainly be found useful by many users stuck in their long contracts who are frustrated due to poor reception, etc. The owner of the contract (the "seller") gets out of the contract by transferring it to someone who wants a new contract (the "buyer"), the transfer being facilitated by CellSwapper. The seller gains by not having to pay the huge termination fee, and the buyer gains by not having to pay the activation fee on a new contract. However, I see one potential problem with the transfer process which can be exploited by malicious users.

This is how the contract transfer happens:

1. Seller posts his contract details on CellSwapper.
2. Buyer contacts seller through CellSwapper
3. Seller pays service fee to CellSwapper ($14-$19) to get buyer details.
   
4. Seller transfers contract to buyer through the cell phone service provider.
5. Seller ships the SIM card and/or phone to the buyer.

There are issues with this scheme mentioned on the CellSwapper website like if step 4 fails due to the buyer failing credit check, the seller loses his service fee, but I don't really consider it "malicious" on the buyer's part as he didn't gain anything. However, the seller can behave maliciously if he transfers the contract to the buyer in step 4 but doesn't immediately send the SIM card to the buyer. He could abuse the minutes on the contract before dispatching the SIM/phone and not have to worry about it since the financial responsibility is transferred already. Of course, this is possible only if step 4 happens without the seller and the buyer physically meeting each other, say doing the transfer of contract on the phone.

I don't see how the buyer can possibly protect himself from this unless the contract transfer process requires a re-activation by the buyer in which case the seller will not be able to use minutes on the contract anymore once the transfer is over. Although I haven't ever tried it myself, this kind of arrangement looks highly unlikely to me. So in the absence of this scheme, the buyer can only trust that the seller doesn't abuse the contract in this way.

IIT 2007 What Puts VCs Off

This post is going to be a short one as I only attended part of this session and now have to run for dinner. This was the gist of a panel discussion comprising of successful VCs and angel investors. Here are the two key points I noted:

Don't go to a VC expecting him to be your product manager, or sales guy, or market researcher, etc., i.e., don't expect for the VC to join hands with you in solving the problem you have and in bridging a serious gap in your argument. Go to them with a complete plan that works out of the box. Of course VCs ultimately do turn out to be very helpful for handling several aspects of a startup's functionality, but don't base your business plan on that.

Meeting a VC is like arranged marriage. You meet them twice or thrice and they tell you yes or nay. This is the fact of the matter since most VCs have many entrepreneurs meeting them all the time and they cannot dedicate too much time to one of them, if the chances of approval are so low. Most VCs make a decision early on in just 2-3 meetings. Consequently, all the usual concepts of arranged marriage apply here. E.g., the first impression really matters, and the VC must have heard really good things about you even before you went to meet them.

IIT 2007 From Engineer to Leader

This was a panel discussion I didn't spend much time at, but here are some interesting concepts that I grasped.

One speaker spoke on how a manager must be able to take complex ideas and present them as extremely simple concepts. He gave the example of his former boss (Larry Ellison) who does this really well.

One topic which dominated the discussion was risk-taking. Big companies, just like normal people, are averse to taking risks. If a business model works, or if something brings a steady supply of cash, employees are highly discouraged to change it in any way. When business is good, it is difficult to bring about change, which is why there is more risk on the manager/leader's part. When business is bad, the same decision is actually a low risk one as things are going southwards anyway. I agree that this is somewhat counter-intuitive to how we understand risks, but remember that we are talking about risks in the context of coming out of a comfort zone when it is strictly not necessary to do so.

To reinforce this point, one panelist gave an example of how he transitioned into a leadership role. There was some crisis situation in his company and a group of employees including managers used to hold meetings everyday to decide on a course of action to resolve the issue. Interestingly, the final decision was obvious to everyone from day one, but it was a tough decision to take due to the risk of not being able to fulfill it, and hence nobody wanted to actually make that decision for fear of being associated with a failed decision. But the speaker actually came out, made the decision, and set out to realize the goal (and the rest he said is history).

Two interesting points were raised about risk-taking during the course of this discussion:

The "F" words:

The most dangerous words for potential leaders are two "F" words: fear, and failure. You cannot hope to be a leader until you learn to convert these into a calculated risk.

Hedging of risk:

Risks can be hedged using two methods: PQ and EQ. PQ stands for Political Quotient and EQ stands for Emotional Quotient. The basic idea is that when you are taking a risk within an organization in a leadership role, make the right political and emotional connections in the organization, such that if you fail, the damage to your career is not much. For example, if the VP of engineering really loves you for the energy and ideas that you bring to the company, your failure is more likely to be ignored, which means you can take more risks :-)

IIT 2007 To MBA or not to MBA

This was one of the most interesting breakout sessions I attended. Although I'm not going through this dilemma myself, it gives me some amount of pleasure to sit back and watch others go through it, and make useless observations :-)

The four panelists for this session had impressive backgrounds with nearly a century worth of management experience under their belt. One of the panelists did not have an MBA (Soni Jiandani) while all others had (HBS, UTA, U of Iowa). All the panelists were highly successful people, e.g,. the non-MBA panelist once headed a $4B market in Cisco. I won't describe all the various points that were discussed, but will point out few salient topics which I found somewhat new or interesting.

• Overall, all panelists agreed that the answer to this million dollar question is actually a very short one: "depends". An opinion shared by most was that if you want to stay in a technology management role, then an MBA may not be useful/very-useful, but if you want to switch to a different industry, like media, finance, etc., then it is very useful.
• Another well known point that came up was how MBA is useful mainly for the networking aspect. The contacts you make in all the top business schools can serve you very well during the course of your career. However, one panelist did mention how some graduates fail to leverage this potential, so one needs to consider that possibility when making a decision.
• One panelist pointed out that Jeff Immelt once said that the professional network you build in your engineering job in 5-10 years time can be made in B school in three months time.
• Talking about networking, the panelists had widely different opinions about whether they learnt anything in B school apart from the professional network they made. The general consensus eventually though was that most of the knowledge you acquire in B school can be gotten through specific, short terms courses (e.g., executive MBAs) outside of B school.
• The non-MBA panelist on the panel made another interesting point: most business situations are unique, and school learning in general doesn't help for solving real world business problems. In other words, her emphasis was on experience.
• The last question was the killer question. Each of the panelists had to mention one mistake that they made when they were trying to decide whether to do an MBA or not do an MBA. The two serious answers were:
• The non-MBA panelist described how she underestimated the importance of short-specific courses to fill her knowledge gap during the course of her career - the knowledge that people usually get during their MBAs. She wished she could go back in her career and correct that. Still she was 100% positive that she didn't need to do an MBA.
• One panelist mentioned how he went for an MBA without getting any job experience first, due to which he made some terrible mistakes in his MBA, e.g., underestimating the importance of network building. He also mentioned that lot of the coursework didn't make any practical sense to him until he graduated and experienced the industry.