Do you think that open standards, data portability and questions of online identity are important? We do; we think these issues are the foundation upon which many of the most exciting and important online innovations are being built.

That's only going to be more true in the future, so if you'd like to have a say in how it all goes down - now's the time to get involved. The OpenID Foundation is one of the leading organizations in the new standards world and it's having its first ever election of community board members this month. Nominations close Monday and the voting begins on Wednesday.

Sponsor

There are big issues on the table right now and the outcome of the election is going to make a big difference in the future of the internet. The Foundation has had incredible success in the past year but it needs your help to determine its direction in the future.

Individuals will have to pay a $25 Foundation membership fee in order to vote, but this author just paid his and is looking forward to pulling the virtual voter's lever. Nominees so far are listed below.

What Are the Issues?

OpenID usability, getting major players to respect incoming OpenID and not just authenticate their own users elsewhere with OpenID, the personal data payload that travels with OpenID and many other difficult questions remain unanswered, despite all the progress the Foundation and other organizations have made in the last year.

A year ago this week we wrote a post saying that OpenID was in serious trouble. One year later, the situation seems to have improved quite a lot. That's thanks not just to the work of the OpenID Foundation, but they deserve a large part of the credit.

The protocol is far from out of the woods, though, and so this election is going to be an important one.

Who's Been Nominated?

So far twelve people have been nominated. Once you register as a Foundation member, you can see the nominees and their position statements. More nominations will likely occur before this weekend is over. Seven of the following twelve total number of people nominated by Monday will get positions on the board. Here's who's been nominated so far.

Johannes Ernst - founder and CEO of startup Netmesh
David Recordon - is from SixApart and is one of the most publicly visible members of the OpenID community
Mike Kirkwood - CEO of iPhone-centric medical patient data service Polka
Eric Sachs - Product Manager at Google
Snorri Giorgetti - OpenID Foundation's European Representative
Eran Hammer-Lahav - Open Web Evangelist at Yahoo! and OAuth lover
Allen Tom - Architect, Yahoo! Membership
Scott Kveton - Current OpenID Foundation Chair and VP Open Platforms at Vidoop
Nat Sakimura - Identity tech wonk from Japan
Brian Kissel - CEO of JanRain, makers of MyOpenID.com
John Bradley - OpenID security wonk
Martin Atkins - an OpenSocial and identity developer

Which seven of those people do you want driving the future of the OpenID Foundation? Register as a member, read their policy statements and you can have your hopes for this important technology paradigm recognized.

Distributed social networking - where users can connect their profile, friends and other data across multiple sites - is still a relatively new concept and not fully developed. There are plenty of companies and projects vying to be a major piece of the distributed social networking puzzle. The big Internet companies have initiatives such as OpenSocial (Google), Facebook Connect, MySpace Data Availability, Yahoo! Open Strategy. There are also smaller company and open source projects such as DiSo and Noserub (we explain these below).

Sponsor

For users the following scenario explains the end goal, albeit too simplistically: in a distributed social networking world you would be able to access your Facebook friends in MySpace, and vice versa. Of course, it's far from a perfect world and the Facebook-MySpace sharing scenario in particular is unlikely to happen any time soon. But slowly social networking is beginning to open up - and not just in the major social networks either.

We spotted an interesting screencast in the ReadWriteWeb Friendfeed room, The Future of Tech, that explains distributed social networking more.

Distributed Social Networking - An Introduction from pixelsebi on Vimeo.

The screencast was created by Sebastian Küpers, an Open Web and Virtual Worlds Evangelist from Germany. He starts by explaining that profiles are a building block of social networks - for example there's a lot of useful profile data in his Facebook account that he'd like to use elsewhere. Friends/contacts, messaging, groups, and activity streams are other building blocks of social networks, explained Sebastian.

He mentioned two projects that are aiming to create distributed social networks by using open standards - DiSo Project (our coverage here and here) and Noserub (a German app). DiSo is basically an umbrella project for many of the leading open standards in the social Web currently - microformats, OpenID, OAuth and more. Noserub describes itself as a "protocol" and uses standards like OpenID, RSS and FOAF.

Sebastian outlined the following use case: if you are a MySpace user and want to add someone who isn't a MySpace user to your friends list, right now you can't. But if MySpace supported the open standards that Noserub, DiSo and others are advocating (microformats, OpenID, etc), then it would be possible for MySpace to support that scenario.

Key Differences Between DiSo/Noserub and OpenSocial/fbConnect

One question that people have about distributed social networks, which Sebastian might like to address in a future screencast, is what is the relation between open source projects like DiSo and Noserub, and 'open data' projects of the bigcos such as Google's OpenSocial and Facebook Connect? Chris Messina, one of the founders of DiSo, pointed out one key difference in DiSo's Google Group in June:

"Our model is rather different than OpenSocial as I understand it, as we're trying to architect this in such a way that anyone can host their own friends list (for example) and not necessarily defer to Google, MySpace, etc... for starters."

So for DiSo, they are using the Wordpress blogging platform as their main vehicle for now. However in the same message, Chris mentioned that he's "personally very interested in the overlap between DiSo and fbConnect and OpenSocial." See also Marc Canter's comments on DiSo, because Marc's "open mesh" theories are very relevant here.

If Everything is So Open, Why Can't We Connect Yet?

There is confusion right now because all the commercial vendors are positioning themselves as open - yet they don't necessarily connect to each other! For example Google has been using the term "Open Stack" to explain what OpenSocial is doing. OpenSocial is still in development and it's important to point out that Google doesn't 'own' it, although it is obviously driving it. But OpenSocial isn't being used by key players like Facebook and Microsoft; and when it is being used by bigcos it can be buggy - a RWW commenter recently remarked that MySpace's OpenSocial implementation is "incredibly buggy". So the fact that all of the main pieces of the distributed social networking puzzle are still in beta, goes some way to explaining why ordinary people can't connect many of their profiles just yet.

We'd like to get some more feedback on distributed social networks in the comments - how would you explain the key differences between DiSo/Noserub and OpenSocial/fbConnect to people? How do you see all the different projects connecting together eventually?

Note: the idea for this post came from the ReadWriteWeb Friendfeed room, The Future of Tech. Thanks to Sebastian Küpers for posting it. If you're want to inspire the RWW crew to write posts on certain topics, our Friendfeed room is a great place to let us know! Thanks also Zee for managing that room for us.

Doesn’t that title just get the blood pumping?  Proof verification has a reputation for being an inordinately academic subject.  In fact, even within scholarly (otherwise known as “unrealistically intelligent“) circles, the automated verification of proofs is known mainly as a complex, ugly and difficult task often not worth the effort.  This is a shame really, because rigorous proofs are at the very core of both mathematics and computer science.  We are nothing without logic (paraphrased contrapositive from Descartes).  Believe it or not, understanding basic proof techniques will be of tremendous aid to your cognitive process, even when working on slightly less ethereal problems such as how to get the freakin’ login page to work properly.

Well, if you made it all the way to the second paragraph, then you either believe me when I say that this is legitimately useful (and cool!) stuff, or you’re just plain bored.  Either way, read on as we commence our exciting journey into the land of rigorous proofs!

SASyLF Crash Course

If you’re at all familiar with the somewhat-specialized field of proof verification, you probably know that SASyLF (pronounced “sassy elf”) is not the most widely used tool for the job.  In fact, it may very well be the least well-known.  More commonly, proofs that require automatic verification are written in Twelf or Coq.  Both of these are fine tools and capable of a lot more than SASyLF, but they can also be extremely difficult to use.  One of the primary motivations behind SASyLF was to produce a tool which was easier to learn, had a higher level syntax (easier to read) and which gave more helpful error messages than Twelf.  The main idea behind these convolutions was to produce a tool which was more suitable for use in the classroom.

The main design decision which sets SASyLF apart from Twelf is the way in which proofs are expressed.  As I understand it, Twelf exploits Curry-Howard correspondence to represent proofs implicitly in the types of a functional program (disclaimer: I’ve never used Twelf, this is just coming from what little I have read about it).  While this can be very powerful, it’s not the most intuitive way to think about a proof.  Eschewing this approach, SASyLF expresses proofs using unification (very similar to Prolog) and defines inference rules explicitly in a natural-language style.

There are three main components to a SASyLF proof:

• Syntax
• Judgments
• Theorems/Lemmas

Intuitively enough, the syntax section is where we express the grammar for the language used throughout our proof.  This grammar is expressed very naturally using BNF, just as if we were defining the language mathematically for a hand-written proof.  Left-recursion is allowed, as is right-recursion, arbitrary symbols, ambiguity and so on.  SASyLF’s parser is mind bogglingly powerful, capable of chewing threw just about any syntax you throw at it.  The main restriction is that you cannot use parentheses, square brackets ([]), pipes (|) or periods (.) in your syntax.  The pure-untyped lambda calculus defined in SASyLF would look something like this:

t ::= fn x => t[x]
    | t t
    | x

I said we couldn’t use brackets, but that’s only because SASyLF assigns some special magic to these operators.  In a nutshell, they allow the above definition of lambda calculus to ignore all of the issues associated with variable name freshness and context.  For simplicity’s sake, that’s about as far as I’m going to go into these mysterious little thingies.

The judgments section is where we define our inference rules.  Just as if we were defining these rules by hand, the syntax has the conditionals above a line of hyphens with the conclusion below.  The label for the rule goes to the right of the “line”.  What could be more natural?

judgment eval: t -> t

t1 -> t1′
--------------- E-Beta1
t1 t2 -> t1′ t2

The judgment syntax is what defines the syntax for the -> “operator”.  Once SASyLF sees this, it knows that we may define rules of the form t -> t, where t is defined by the syntax section.  Further on down, SASyLF sees our E-Beta1 rule.  Each of the tokens within this rule (aside from ->) begins with “t“.  From this, SASyLF is able to infer that we mean “a term as defined previously”.  Thus, this rule is syntactically valid according to our evaluation judgment and the syntax given above.

Of course, theorems are where you will find the real meat of any proof (I’m using the word “proof” very loosely to mean the collection of proven theorems and lemmas which indicates some fact(s) about a language).  SASyLF wouldn’t be a very complete proof verification system without support for some form of proving.  Once again, the syntax is extremely natural language, almost to the point of being overly-verbose.  A simple theorem given the rules above plus a little would be to show that values cannot evaluate:

theorem eval-value-implies-contradiction:
    forall e: t -> t’
    forall v: t value
    exists contradiction .

    _: contradiction by unproved
end theorem

Note that contradiction is not more SASyLF magic.  We can actually define what it means to have a contradiction by adding the following lines to our judgment section:

judgment absurd: contradiction

In other words, we can have a contradiction, but there are no rules which allow us to get it.  In fact, the only way to have a contradiction is to somehow get SASyLF to the point where it sees that there are no cases which satisfy some set of proven facts (given the forall assumptions).  If SASyLF cannot find any cases to satisfy some rules, it allows us to derive anything at all, including judgments which have no corresponding rules.

Readers who have yet to fall asleep will notice that I cleverly elided a portion of the “theorem” code snippet.  That’s because there wasn’t really a way to prove that contradiction given the drastically abbreviated rules given in earlier samples.  Instead of proving anything, I used a special SASyLF justification, unproved, which allows the derivation of any fact given no input (very useful for testing incomplete proofs).  Lambda calculus isn’t much more complicated than what I showed, but it does require more than just an application context rule in its evaluation semantics.  In order to get a taste for SASyLF’s proof syntax, we’re going to need to look at a much simpler language.

Case Study: Integer Comparison

For this case study, we’re going to be working with simple counting numbers which start with 0 and then proceed upwards, each value expressed as the successor of its previous value.  Thus, the logical number 3 would be s s s 0.  Not a very useful language in the real world, but much easier to deal with in the field of proof verification.  The syntax for our natural numbers looks like this:

n ::= 0
    | s n

With this humble definition for n, we can go on to define the mathematical greater-than comparison using two rules under a single judgment:

judgment gt: n > n

------- gt-one
s n > n

n1 > n2
--------- gt-more
s n1 > n2

Believe it or not, this is all we need to do in terms of definition.  The first rule says that the successor of any number is greater than that same number (3 > 2).  The second rule states that if we already have two numbers, one greater than the other (12 > 4), then the successor of the greater number will still be greater than the lesser (13 > 4).  All very intuitive, but the real question is whether or not we can prove anything with these definitions.

An Easy Lemma

For openers, we can try something reasonably simple: prove that all non-zero numbers are greater than zero.  This is such a simple proof that we won’t even bother calling it a theorem, we will give it the lesser rank of “lemma”:

lemma all-gt-zero:
    forall n
    exists s n > 0 .

    _: s n > 0 by induction on n:
        case 0 is
            _: s 0 > 0 by rule gt-one
        end case

        case s n1 is
            g: s n1 > 0 by induction hypothesis on n1
            _: s s n1 > 0 by rule gt-more on g
        end case
    end induction
end lemma

In order to prove anything about n, we first need to “pull it apart” and find out what it’s made of.  To do that, we’re going to use induction.  We could also use case analysis, but that would only work if our proof didn’t require “recursion” (we’ll get to this in a minute).  There are two cases as given by the syntax for n: when n is “0“, and when n is “s n1“, where n1 is some other number.  We must prove that s n > 0 for both of these cases individually, otherwise our proof is not valid.

The first case is easy.  When n is 0, the proof is trivial using the rule gt-one.  Notice that within this case we are no longer proving s n > 0, but rather s 0 > 0.  This is the huge win brought by SASyLF’s unification: n is “0” within this case.  Anything we already know about n, we also know about 0.  When we apply the rule gt-one, SASyLF sees that we are attempting to prove s n > n where n is “0“.  This is valid by the rule, so the verification passes.

The second case is where things get interesting.  We have that n is actually s n1, but that doesn’t really get us too much closer to proving s s n1 > 0 (remember, unification).  Fortunately, we can prove that s n1 > 0 because we’re writing a lemma at this very moment which prove that.  This is like writing a function to sum all the values in a list: when the list is empty, the result is trivial; but when the list has contents, we must take the head and then add it to the sum of the tail as computed by…ourself.  Induction is literally just recursion in logic.  Interestingly enough, SASyLF is smart enough to look at all of the inductive cases in your proof and verify that they are valid.  This is sort-of the equivalent of a compiler looking at your code and telling you whether or not it will lead to an infinite loop.

To get that s n1 > 0, we use the induction hypothesis, passing n1 as the “parameter”.  However, we’re not quite done yet.  We need to prove that s s n1 > 0 in order to unify with our original target (s n > 0).  Fortunately, we already have a rule that allows us to prove the successor of a number retains its greater-than status: gt-more.

However, gt-more has a condition in our definition.  It requires that we already have some fact n1 > n2 in order to obtain s n1 > n2.  In our case, we already have this fact (s n1 > 0), but we need to “pass” it to the rule.  SASyLF allows us to do this by giving our facts labels.  In this case, we have labeled the s n1 > 0 fact as “g“.  We take this fact, pack it up and send it to gt-more and it gives us back our final goal.

A Slightly Harder Theorem

A slightly more difficult task would be to prove that the successors of two numbers preserves their greater-than relationship.  Thus, if we know that 4 > 3, we can prove that 5 > 4.  More formally:

theorem gt-implies-gt-succ:
    forall g: n1 > n2
    exists s n1 > s n2 .

    _: s n1 > s n2 by unproved
end theorem

At first glance, this looks impossible since we don’t really have a rule dealing with s n on the right-hand side of the >-sign.  We can try to prove this one step at a time to see whether or not this intuition is correct.

Almost any lemma of interest is going to require induction, so immediately we jump to inducting on the only fact we have available: g.  Note that this is different from what we had in the earlier example.  Instead of getting the different syntactic cases, we’re looking at the the rules which would have allowed the input to be constructed.  After all, whoever “called” our theorem will have needed to somehow prove that n1 > n2, it would be helpful to know what facts they used to do that.  SASyLF allows this using the case rule syntax.  We start with the easy base case:

_: s n1 > s n2 by induction on g:
    case rule
        ------------ gt-one
        _: s n2 > n2
    is
        _: s s n2 > s n2 by rule gt-one
    end case
end induction

In this case, the term _: s n2 > n2 is unified with n1 > n2.  Thus, n1 is actually “s n2“.  This means that by unification, we are actually trying to prove s s n2 > s n2.  Fortunately, we have a rule for that.  If we let “n” be “s n2“, we can easily apply the rule gt-one to produce the desired result.

The second case is a bit trickier.  We start out by defining the case rule according to the inference rules given in the judgment section.  The only case left is gt-more, so we mindlessly copy/paste and correct the variables to suit our needs:

case rule
    g1: n11 > n2
    ------------- gt-more
    _: s n11 > n2
is
    _: s s n11 > s n2 by unproved
end case

In this case, n1 actually unifies with “s n11“.  This is probably the most annoying aspect of SASyLF: all of the syntax is determined by token prefix, so every number has to start with n, occasionally making proofs a little difficult to follow.

At this point, we need to derive s s n11 > s n2.  Since the left and right side of the > “operator” do not share a common sub-term, the only rule which could possibly help us is gt-more.  In order to apply this rule, we will somehow need to derive s n11 > s n2 (remember, gt-more takes a known greater-than relationship and then tells us something about how the left-successor relates to the right).  We can reflect this “bottom-up” step towards a proof in the following way:

case rule
    g1: n11 > n2
    ------------- gt-more
    _: s n11 > n2
is
    g: s n11 > s n2 by unproved
    _: s s n11 > s n2 by rule gt-more on g
end case

At this point, SASyLF will warn us about the unproved, but it will happily pass the rest of our theorem.  This technique for proof development is extremely handy in more complicated theorems.  The ability to find out whether or not your logic is sound even before it is complete can be very reassuring (in this way you can avoid chasing entirely down the wrong logical path).

In order to make this whole thing work, we need to somehow prove s n11 > s n2.  Fortunately, we just so happen to be working on a theorem which could prove this if we could supply n11 > n2.  This fact is conveniently available with the label of “g1“.  We feed this into the induction hypothesis to achieve our goal.  The final theorem looks like this:

theorem gt-implies-gt-succ:
    forall g: n1 > n2
    exists s n1 > s n2 .

    _: s n1 > s n2 by induction on g:
        case rule
            ------------ gt-one
            _: s n2 > n2
        is
            _: s s n2 > s n2 by rule gt-one
        end case

        case rule
            g1: n11 > n2
            ------------- gt-more
            _: s n11 > n2
        is
            g2: s n11 > s n2 by induction hypothesis on g1
            _: s s n11 > s n2 by rule gt-more on g2
        end case
    end induction
end theorem

Conclusion

I realize this was a bit of a deviation from my normal semi-practical posts, but I think it was still a journey well worth taking.  If you’re working as a serious developer in this industry, I strongly suggest that you find yourself a good formal language and/or type theory textbook (might I recommend?) and follow it through the best that you can.  The understanding of how languages are formally constructed and the mental circuits to create those proofs yourself will have a surprisingly powerful impact on your day-to-day programming.  Knowing how the properties of a language are proven provides tremendous illumination into why that language is the way it is and somtimes how it can be made better.

Credit: Examples in this post drawn rather unimaginatively from Dr. John Boyland’s excellent course in type theory.

• SASyLF Main Page at Carnegie Mellon University
• Download math.slf (the full greater-than example)
• Further reading…

This is the tenth post in an article series about MIT’s lecture course “Introduction to Algorithms.” In this post I will review lecture fifteen, which introduces the concept of Dynamic Programming and applies it to the Longest Common Subsequence problem.

Dynamic programming is a design technique similar to divide and conquer. Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. Dynamic programming is applicable when the subproblems are not independent, that is, when subproblems share subsubproblems. A dynamic-programming algorithm solves every subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time the subsubproblem is encountered.

Dynamic programming was systematized by Richard E. Bellman. He began the systematic study of dynamic programming in 1955. The word “programming,” both here and in linear programming, refers to the use of a tabular solution method and not to writing computer code.

Dynamic programming is typically applied to optimization problems. In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

Dynamic programming can be effectively applied to solve the longest common subsequence (LCS) problem. The problem is stated as following: given two sequences (or strings) x and y find a maximum-length common subsequence (substring) of x and y.

For example, given two sequences x = “ABCBDAB” and y = “BDCABA”, the LCS(x, y) = { “BCBA”, “BDAB”, “BCAB” }. As you can see there are several optimal solutions.

Lecture fifteen introduces dynamic programming via this longest common subsequence problem. It first gives a brute-force, exponential time algorithm for solving it. The idea of algorithm is to check every subequence of x[1..m] (m is the length of sequence x) to see if it is also a subsequence of y[1..n] (n is the length of sequence y). Checking takes O(n) time, and there are 2^m subsequences of x. The running time thus is exponential O(n·2^m). It is no good for large sequences and the lecture continues with a simplification - let’s look at the length of a longest-common subseq and then extend this algorithm to find the LCS itself. The simplified algorithm is recursive in nature and computes the same subproblems. At this moment two dynamic programming hallmarks are stated:

• 1. Optimal substructure: an optimal solution to a problem contains optimal solutions to subproblems.
• 2. Overlapping subproblems: a recursive solution contains a “small” number of distinct subproblems repeated many times.

As the subproblems are overlapping, the lecture introduces concept of memoization algorithm (note that it’s not memorization). A better known word for memoization is caching. The subproblems are cached (memoized) so that they are not recomputed over and over again.

The lecture ends with constructing a dynamic programming table for LCS problem and explains how to find a LCS from this table.

You’re welcome to watch lecture fifteen:

Topics covered in lecture fifteen:

• [00:20] Dynamic programming.
• [01:47] Longest common subsequence (LCS) problem.
• [03:55] Example of LCS on sequences “ABCBDAB” and “BDCABA”.
• [06:55] Brute force algorithm for LCS.
• [07:50] Analysis of brute force algorithm.
• [11:40] Simplification of LCS problem.
• [16:20] Theorem about LCS length.
• [18:25] Proof of the theorem.
• [30:40] Dynamic programming hallmark #1: Optimal substructure.
• [32:25] Example of hallmark #1 on LCS.
• [34:15] Recursive algorithm for longest common subseq.
• [36:40] Worst case analysis of the algorithm.
• [38:10] Recursion tree of algorithm.
• [42:40] Dynamic programming hallmark #2: Overlapping subproblems.
• [44:40] Example of hallmark #2 on LCS.
• [45:50] Memoization algorithm for LCS.
• [48:45] Time and space analysis of memoized algorithm.
• [54:30] Dynamic programming algorithm for LCS.
• [01:01:15] Analysis of dynamic programming algorithm.

Lecture fifteen notes:

Lecture 15, page 1 of 2.
Lecture 15, page 2 of 2.

Have fun with programming dynamically! The next post will be about graphs, greedy algorithms and minimum spanning trees.

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”). Chapter 15 is called “Dynamic Programming” and covers the topics in this lecture. It also explains the assembly-line scheduling problem, matrix-chain multiplication problem, elements of dynamic programming and optimal binary search trees.

Plus tu as de connaissances et d'expérience pour faire des trucs géniaux et moins tu as de temps pour les réaliser.

Monde cruel.

The winners of the SIOC (pronounced "shock") data competition being run by DERI at the National University of Ireland, Galway have been announced. The competition ran from September to October 2008, and the brief was to produce an interesting creation based on a data set of discussion posts reflecting ten years of Irish online life from boards.ie, Ireland's largest community website.

read more

Julian Bilcke, membre officieux de web-mining.fr et néanmoins très actif sur les projets Gephi et CodeMiner, avait réalisé un travail expérimental au printemps dernier sur la cartographie du dépôt logiciel de la communauté Perl, appelé CPAN.

L’objectif de ce projet consistait à mettre en place un système de visualisation des dépendances logicielles de CPAN, contenant environ 53 000 modules répartis dans plus de 14 000 packages, chaque module pouvant en utiliser plusieurs autres. Ce système permettait de voir les dépendances d'un module ou un package donné, c’est à dire les composants également issus de CPAN nécessaires à son fonctionnement.

Voici une maquette :

Il s’agit du graphe des dépendances d’un package pris au hasard sur CPAN, App-Context. Il donne à voir tous les packages nécessaires à son installation automatique. L'affichage est basé sur des méta-données pour rendre le graphe utile à explorer, et permet ainsi de voir les résultats des tests officiels, le faisant un outil d’aide à la décision.

Présentation :

Page du projet : http://uxmal.paradisia.net/sigl-cpan/
Billet de blog attenant : http://uxmal.paradisia.net/2008/04/27/dependances-logicielles-entre-pack...
Présentation : Voir le ppt sur slideshare
Rapport : Télécharger
Captures d’écran : galerie d’images

Et pour finir, quelques captures d'écran du système, d'abord la visualisation par modules :

Un graphe de dépendances, les boules rouges représentent les modules.

Un graphe de dépendances en cours de visualisation sous Gephi.

Page d'interrogation en ligne avec applet Gephi intégré.

Et la vue sur le dépôt entier :

En cours de spatialisation sous Gephi.

Après un premier "éclatement" du graphe où l'on distingue un coeur, des composantes non connexes et des éléments isolés formant des "anneaux" en périphérie.

Le plugin Gephi permettant d'explorer le graphe en recherchant des modules et en ajustant la profondeur des dépendances à afficher.

Le projet est actuellement arrêté mais j'espère vivement que Julian trouvera le temps ou quelqu'un d'autre pour le poursuivre !

A little more than two weeks ago I had an on-site interview at Google in Mountain View, California! The job interview with Google was an interesting experience and I want to tell you about it. (I got the green light from Google to publish this article).

The position I was interviewing for was a Google SRE. SRE stands for Site Reliability Engineering. Site reliability engineers (SREs) are both software engineers and systems administrators, responsible for Google’s production services from end-to-end.

There were eight separate interviews total. The first three were over the phone (phone interviews) and the remaining five were on-site. The first interview was with the recruiter and was not very technical but the other seven were very technical.

All interviews went very well but I just got to know that I did not get hired! Oh well… I personally think that I did really well. I answered all the questions but it seems they were not satisfied! The recruiter told me that I did not have enough experience to work in a mission critical team and that I should get more experience and try again.

Here is how it all happened.

Shortly after I published the “Code Reuse in Google Chrome” post I was contacted by a recruiter at Google. The email said:

I recruit top notch Software Engineering talent at Google. I recently came across your name as a possible world class Engineer and am intrigued to know more about you. I promise to exchange some detailed info about us as well.

Interested to hear more? Want to be an impact player at Google? Then please respond with a current (English) copy of your resume and I’ll be happy to call you and discuss.

At first I thought I would be applying for a software developer position, but after we went through my skillset, the recruiter concluded that I would better fit as an SRE. I agreed with him. This seemed like a perfect position for me. I love systems administration as much as I love programming.

First Interview (phone)

The first interview was on the 10th of September with the recruiter. He explained the Google recruitment process to me and we went through my skill set. I had to rank myself from 0 - 10 in a bunch of areas such as C programming, C++ programming, Python programming, networking, algorithms and data structures, distributed systems, Linux systems administration, and others.

As I said, based on my answers we concluded that SRE was the best position for me. An SRE basically has to know everything: algorithms, data structures, programming, networking, distributed systems, scalable architecture, troubleshooting. It’s a great hacker position!

After these questions he asked me where I would like to work - Google office in Ireland, Zurich, Mountain View or Australia. I said Mountain View as it’s the Googleplex! He explained that if the interviews went OK, I’d have to get an H-1B visa that allows non-US citizens to work in the US.

The second half of the interview had some basic technical questions, just to make sure I knew something. The questions were about Linux systems administration, algorithms, computer architecture and C programming. I can’t go into any details because I signed a non-disclosure agreement and my recruiter kindly asked me not to post the questions!

I made some factual mistakes but he was satisfied and we scheduled the next phone interview. He warned me that it will be very technical and I should do really good preps. I asked him to give me a plenty of time for the preparation and we scheduled the next interview on 22nd of September.

He also told me that each phone interview is going to be 45 minutes to 1 hour long.

I started preparing like crazy. I found three presentations on what SRE is all about:

• Engineering Reliability into Web Sites: Google SRE
• Google SRE: That Couldn’t Happen to US… Could It?
• Google SRE: Chasing Uptime

Then I found all the other blog posts about interviews and interview questions at Google:

• Corey Trager’s Google Interview
• Rod Hilton’s Google Interview
• Ben Watson’s Google Interview
• Shaun Boyd’s Google Interview
• How I Blew My Google Interview by Henry Blodget
• Get That Job at Google by Steve Yegge
• Tales from the Google’s interview room
• Google Interview Questions
• Google Interview Questions — Fun Brain Teasers!
• And some others…

I printed and read four Google research papers:

• The Google File System
• Bigtable: A Distributed Storage System for Structured Data
• MapReduce: Simplified Data Processing on Large Clusters
• and just for fun Failure Trends in a Large Disk Drive Population

I also went through several books:

• the best book on basics of networking “TCP/IP Illustrated“
• the best book on algorithms “MIT’s Introduction to Algorithms” + my notes on algorithms
• a book on scalability “Building Scalable Web Sites“

As I did not know if I might get specific programming language questions, I went through a few tens of receipts in C++ Cookbook, Python Cookbook, and Perl Cookbook.

Second Interview (phone)

The second phone interview was with an engineer from Google. He worked on the Ads team which is responsible for running AdSense, AdWords and other advertisement stuff.

The interview was very technical and started with an algorithmic problem which was too large to fit in computer memory. I had to tell him precisely how I would get around this problem and what data structures and algorithms I would use. He also asked me to think out loudly. The interview continued with questions about data structures, DNS, TCP protocol, a security vulnerability associated with TCP, networking in general, and Google itself. Sorry, but I can’t disclose anything in more details.

After the interview the engineer had to write feedback on me. It was positive and I could move on with the interviews.

Third Interview (phone)

I gave myself more time to prepare and the third interview was on the 1st of October. It was with an engineer from the Google traffic team.

In this interview I had a very simple programming question and I had to do coding over phone. I was free to choose the language and I chose Perl as it is my most favorite programming language. It was impossible to dictate Perl syntax over phone “for my dollar sign element open paren at data close paren open curly brace … close curly brace” so I submitted my Perl program over the email.

Then the same problem was taken to the next level, what if the data we are working on is gigabytes in size, terabytes in size. How would my program/solution change?

Finally I had a question about DNS again, then HTTP protocol, routing, and TCP data transfer.

The feedback was positive and I could prepare for the on-site interviews. In my conversation with my recruiter I got to know that there will be five on-site interviews, each exactly 45 minutes long. One on my previous work experience, one on algorithms and data structures, one on troubleshooting and networking, and two on software development with focus on C and C++.

My recruiter suggested that I read a few more documents:

• Google C++ Style Guide
• Web Search for a Planet: The Google Cluster Architecture
• Algorithm Tutorials on TopCoder

I flew out to USA on 24th of October at 1pm from Latvia and arrived in California at 8pm. The flight was actually 14 hours but it was nice that I flew in the same direction as the time flows. This saved me 7 hours. The on-site interview was scheduled on 27th of October so I had a good rest before the interview. It was also nice that Google paid for my trip, hotel, cab and food. I had zero expenses!

Fourth Interview (on-site)

The fourth interview was finally at Googleplex! At 10am I met my recruiter and we had a 15 minute discussion about the interviews. He told me I would have two interviews now, then one of Google engineers would take me to lunch to one of Google’s restaurants and then I would have three other interviews.

At 10:15am the first on-site interview began. It was about my previous job experience. I have had a lot of job experience in the past and I decided to tell about a physical security notification system that I coded in C on Linux a few years ago. The system would receive messages through the serial port and send out emails and SMS’es.

In the last minutes of the interview he asked me some basic Unix filesystem questions.

In all the on-site interviews I was writing and drawing on two big whiteboards. Fun!

Fifth Interview (on-site)

The fifth interview began at 11am. It was a coding session and began with a trick question and not a real coding problem. I was asked to implement the solution in C. The solution was a mathematical expression that was a one-line return statement. No big coding there. Then I was asked to write an implementation of a very well known data structure. While coding I made a mistake and forgot to initialize part of a data structure that I had malloc()’ed! The program would have segfault’ed in real life and I would have noticed the error, but Google engineers are very serious about it! If you have an interview don’t ever make any mistakes!

After this interview I was taken to lunch by the engineer who interviewed me on the second (phone) interview. She told me she was working at Google for two years and was very happy about it. We went to Asian food restaurant (located in Googleplex) and I had all kinds of delicious foods. All free!

Then she showed me around Googleplex. It was all amazing. Free drinks and candy everywhere, some arcade machines, a beach volleyball outside, and many other surprising things.

Sixth Interview (on-site)

The sixth interview began at 12:45pm. It was a troubleshooting and networking interview. The interviewer drew a network diagram on the whiteboard and had imagined a problem in there. I had to ask a bunch of specific networking questions to locate the problem. He was satisfied and in the last few minutes of the interview he asked me some specific networking device questions.

Seventh Interview (on-site)

The seventh interview began at 1:30pm. It was a coding session. I was asked to implement a simple string manipulation subroutine in either C or C++. I chose C. Unfortunately I made an off-by-one mistake there - the most common programming mistake in the history of mankind. The whole interview focused on this one problem.

Eighth Interview (on-site)

The last, eight, interview began at 2:15pm. It was algorithms and data structures interview. The problem presented here was similar to the problem in the 2nd interview. Not only was it a problem too large to fit in computer memory but it also was distributed. So I had to do all kinds of trickery to solve it. The interview was very free-style and we talked back and forth about the problem. I arrived at the correct solution near the end of the interview and he said that not many candidates get that far in the solution. I was happy.

After the interview the engineer escorted me out to the lobby and I took a cab back to my hotel. That’s it!

FIN

Overall the Google interviews were pure fun for me. The interview questions were technical but not very challenging or difficult.

Thanks for the opportunity Google!

J’ai eu l’occasion d’animer cette semaine un débat intéressant sur le web 2.0 et la Silicon Valley, le “SF Valley”. Il s’agissait d’une visioconférence avec d’un côté environ 200 personnes dans l’amphithéâtre des Jardins de l’Innovation de France Télécom à Issy les Moulineaux, et de l’autre, une demi douzaine d’entrepreneurs sis dans l’Orange Lab de San Francisco, animés par Laetitia Mailhes, correspondante permanente des Echos aux USA. La conférence était organisée sous l’égide du G9+ (qui rassemble les groupements informatiques des associations d’anciens élèves de grandes écoles d’ingénieur et de commerce) et pilotée par des anciens de Centrale Marseille.

Les intervenants côté US étaient Daniel Laury (de LSF Interactive, une agence web, également active en France), Béatrice Tarka (de Mobissimo, un site web de voyage), Renaud Laplanche (de Lending Club, un site de prêt en peer to peer), Marc Dangeard (d’Entrepreneur Commons, une association qui propose des prêts aux entrepreneurs) et JD Bergeron (de Kiva, une ONG de microcrédit pour les pays émergents). Nous avions sinon Thierry Bonhomme, Directeur de la R&D de FT ainsi que Georges Nahon, patron des Orange Labs de San Francisco.

On devait parler web 2.0. Mais la thématique de cette conférence de plus de deux heures a nettement penché sur l’impact de la crise financière dans le monde des startups. Et de comparer la résilience des nos économies respectives face à cette crise.

L’occasion m’en est donc donnée de faire ici le tour de la question en comparant l’impact de cette crise entre la Silicon Valley et la France. Et en mélangeant ce que j’ai pu entendre jeudi dernier et aussi via pas mal d’autres sources.

Le financement des startups

Est-ce que la crise du crédit impacte le financement des startups ? Certainement, mais pas de la même manière aux USA et en France.

Les montants investis par les VCs aux USA se sont ralentis sur le troisième trimestre ($7,4B sur 583 deals, une décroissance de 7,2% par rapport à 2007 sur 673 deals. Et on s’attend à un très mauvais Q4. La tendance des VCs est de financer des seconds et troisièmes tours de sociétés qui ont fait leurs preuves et beaucoup moins d’amorçage. C’est ainsi que les VCs utilisent les fonds qu’ils ont levés en 2007. Ils s’orientent aussi nettement sur des secteurs porteurs comme les greentechs, où la Silicon Valley est très active. La crise du financement a en tout cas refroidi les VCs qui finançaient encore beaucoup trop de startups web 2.0 fonctionnant sur un modèle publicitaire. Les VCs privilégient maintenant les modèles économiques capables de générer du revenu rapidement. La crise va sérieusement assainir le marché !

En France, nous n’avons pas encore de données sur Q3 2008. La loi TEPA a quelque peu gonflé le financement de FCPI, un véhicule privilégié pour de nombreux VCs. Ce qui donne un peu de mou aux VCs pour investir pendant 2008 et 2009. Mais Q3 et Q4 2008 ne devraient pas être bien brillants. On attend donc l’indicateur de Chausson Finance sur fin 2008 !

Autre impact : les valorisations des sociétés baissent avant les tours de financement. Les entrepreneurs peuvent s’attendre à des négociations difficiles sur ce point avec autant les VCs que les business angels. Bien entendu, il est bon d’avoir une valorisation qui limite la dilution à chaque tour de financement. Mais elle doit être justifiée par la création de valeur de la société, une combinaison de la valeur de l’équipe, du produit et des clients déjà captés. S’il y a bien une bulle web 2.0 qui se dégonflera, c’est sur les valos ! Evidemment, il y aura aussi moins de sorties (acquisitions et introductions en bourse) pendant quelques temps. Ce qui posera des problèmes pour cloturer les fonds des VCs.

Béatrice Tarka de Mobissimo signalait un autre phénomène dans le débat SF Valley : l’insécurité du cash levé par les startups. Placé dans le système bancaire, il est fragilisé car les banques peuvent faire faillite et leurs garanties sont faibles (<$250K). Il leur faut donc envisager un investissement “sûr”, par exemple en bons du trésor, les pays occidentaux en émettant des wagons en ce moment. Jusqu’au jour où ces pays subiront eux-aussi une crise de type Argentine !

La crise favorise sinon le développement de solutions alternatives de financement. Le prêt mutualisé est la formule proposée par Lending Club et Entrepreneur Commons, deux solutions présentées pendant le débat “SF Valley”. Mais en masse, cela semble bien marginal au regard des $30B que les VCs investissaient en 2007 et à peu près autant provenant des business angels. Aux USA, ces derniers sont en train de baisser la voilure où à chercher des rendements à court terme, incompatibles avec le risque du financement des startups qui ressemble plutôt à un jeu de casino… sur le Titanic.

Qu’avons-nous du côté de la France ?

• La loi TEPA et l’exonération d’ISF de 75% pour les investissements dans les PME innovantes va continuer à drainer un bon volant de business angels. Une bien rare exception qui fera de l’ISF un atout pour la France ! Le rôle des associations de business angels et des SIBA (sociétés d’investissement de business angels) va être critique pour réguler ce flot de financement assez “amateur” par les temps qui courent.
• Les financements publics, même s’ils s’assèchent rapidement, constituent une autre spécificité française qui soutient bien les startups en phase d’amorçage. Mais on entend dire qu’Oséo va réduire ses aides en phase d’amorçage et favoriser les aides au développement des gazelles, une priorité gouvernementale.
• On voit apparaitre quelques sites de désintermédiation entre investisseurs individuels (business angels) et entrepreneurs comme Investigo et FaisonsAffaires. Ils se rémunèrent au pourcentage des montants levés (environ 5%) mais le modèle n’est pas très scalable. Et puis, il est concurrencé par le site d’Oséo qui rapproche les investisseurs des PME innovantes (respectivement 3590 et 2297, tous secteurs confondus). Mais il est difficile d’y trouver les startups du numérique, catégorie qui n’existe pas dans leurs critères de sélection ! Toutes ces désintermédiations vont mettre de l’huile dans les rouages, sauf qu’il risque de ne plus y avoir beaucoup d’engrenages !

• Enfin, il y a l’appel aux dons, une méthode originale quoiqu’un peu déplacée. Elle est utilisée par exemple par Mobuzz.TV, une web TV spécialiste… du buzz ! Ils cherchent tout de même 150K€ par ce biais ! Pourquoi ? Levée de fonds difficile. Pourquoi ? Il suffit de voir le site et son modèle publicitaire…

Bref, en France, nous aurons un peu plus d’air sur le financement d’amorçage qu’aux USA. Mais cela n’améliorera pas pour autant les chances de réussite des startups.

La gestion des coûts

Réduire au maximum les coûts est le mot d’ordre. Les startups doivent durer avec les fonds qu’elles ont levé et réduire au maximum la voilure, surtout si elles ne génèrent pas encore de revenu.

D’où un gel des embauches voire des licenciements préventifs. Un phénomène qui a affecté aussi bien de grandes entreprises comme HP, Dell, Amdocs, Xerox et Yahoo que des sociétés du  web 2.0 comme Pandora, Technorati, Seesmic, Twitter, Hi5, Adbrite, Zivity, Mahalo (qui a maintenant du cash pour tenir sans revenus jusqu’à 2012 et avec 30 personnes après en avoir viré 10%…). Ce qui n’a pas empêché LinkedIn de lever $26m en octobre portant le total à $100m. Mais qui licencie tout de même ! Ces licenciements sont suivis par TechCrunch qui a créé un Layoffs Tracker et en a totalisé 78751 à ce jour dans la high-tech et particulièrement dans la Silicon Valley ! Ce qui a augmenté le chômage dans la Silicon Valley à 6,6%.

Mais où vont tous ces chômeurs dans la mesure où les grandes boites de la high-tech gèlent aussi plus ou moins leurs recrutements ? On pouvait apprendre dans le débat SF Valley que l’écosystème de la Silicon Valley bénéficie d’une grosse variable d’ajustement : les nombreux étrangers qui travaillent dans la SV avec un visa de travail H1B1. Plus de boulot, plus de visa, et ils doivent retourner dans leur pays. Ou devenir clandestins. Un ajustement qui fonctionne peut-être dans la Silicon Valley mais ne sera pas opérant à Détroit avec les difficultés de General Motors.

La grande flexibilité du travail aux USA créé cette fluidité qui simplifie la vie des entreprises lorsqu’il faut s’adapter et dégraisser. Les intervenants de SF Valley indiquaient que cela permettait de trouver des talents de qualité alors que c’était très difficile. Mais qui peut encore embaucher ? Peut-être quelques rares startups profitables ou les grandes entreprises qui ne licencient pas et gèrent leur turn-over.

Les modèles économiques

Quel est l’impact de la crise sur les modèles économiques des startups ?

Les modèles purement publicitaires (au CPM ou CPC) seront très affectés car ils ne permettent pas d’être rentables à moins d’avoir un trafic énorme, et encore. Daniel Laury de LSF Interactive confirmait cette tendance : les modèles attendus par les clients sont de plus en plus basés sur la performance : le CPA/CPL (coût à l’action, au lead). Ils déplacent le risque des annonceurs vers les sites et les régies publicitaires et rendent prédictibles les investissements publicitaires : un $ de pub génère x $ de revenu incrémental. Encore faut-il que la construction du site soit adaptée à ce besoin.

Le modèle « on créé de l’audience et on verra plus tard pour le modèle de revenu » va à mon sens battre de l’aile. C’en est presque devenu un mythe lié au cas de Google qui fait rêver. Mais Google est un cas particulier qui n’est pas facilement réplicable. Google a créé le modèle de revenu structurellement le meilleur du web : le search (qui permet de la publicité très contextuelle) et le volume (un outil pour tous utilisé tout le temps). La plupart des sites web 2.0 ne créent pas cette combinaison de contextualité et de volume. Seuls quelques réseaux sociaux gagnent leur vie car ils ont une forte part de contenu dans leur mix (MySpace, Skyblog). Une startup qui prévoit de se financer par la publicité devra avoir une stratégie très affinée de monétisation et la faire correspondre aux méthodes du marché (régies pubs, comportement des annonceurs, modes de segmentation dans les pratiques marketing des boites btob). Le business plan de la startup qui indique “financement par la pub” sans autre précision risque d’être poubellisé rapidement ! Même dans les instances de financement issues du secteur public.

Les modèles de commerce électronique sont plus sains mais peuvent aussi être affectés par la baisse de la consommation des ménages et des entreprises. Les modèles qui fonctionneront le mieux devront être en phase avec l’évolution des modes de consommation : prix plus bas, etc.

Seront donc (encore plus) favorisée par les investisseurs les entreprises qui :

• Proposent une « business value » claire et percutante, permettant par exemple aux entreprises de réaliser des économies substantielles. Avec un chiffrage précis de l’équation économique et sa relation avec le temps.
• Dont les modèles génèrent du revenu au gré de l’augmentation du volume, et pas après par effet de seuil. Par exemple dans la mobilité si le revenu peut être partagé avec les telcos.
• Qui ont déjà un produit et des clients et une évolution déjà bien lancée de leur CA.
• Ont éventuellement un bon portefeuille de propriété intellectuelle (potentiel ou existant) et monétisable assez rapidement.

C’est en tout cas la fin du financement des me-toos comme les innombrables réseaux sociaux voire de social shopping. Une fin qui avait déjà démarré avant septembre. La crise n’annonce pas la fin des grands principes du web 2.0 et notamment de l’UGC (User Generated Content). Mais ceux qui vont en profiter seront les plus gros acteurs, ou bien les activités « non-profit » (blogs, associations, ONG, éduc, etc).

Chose surprenante, la crise n’empêche aucunement les entrepreneurs de manifester une créativité débridée. J’ai récemment découvert un blog US, KillerStartups, qui décrit cinq nouvelles startups par jour. C’est à la fois varié et on y trouve un véritable bêtisier des startups “features companies” et sans modèle économique.

Plus de la moitié des startups survivent après quatre ans d’existence dans la Silicon Valley. Au vu de ce catalogue, c’est franchement surprenant !

Les marchés

La crise impacte les clients des startups et de différentes manières :

• Les cycles de vente s’allongent. La prise de risques s’amenuise. Les startups vont en souffrir et particulièrement en France qui ne brille pas par la culture du risque.
• Les budgets marketing sont souvent des variables d’ajustement. Depuis le début de 2008, les budgets publicitaire online étaient les seuls à augmenter alors que le offline baissait partout. Mais sur la fin 2008, il semblerait que même les budgets online soient en diminution aux USA. Et donc ailleurs.
• Des sponsors se désengagent d’opérations. Un diner-débat d’une association professionnelle auquel je devais participer en octobre a été annulé pour cette raison !
• Les cadres des grandes entreprises sont encore plus prudents, protègent leur place, et le stress au travail augmente en conséquence.
• Le poids de l’état est tel que la commande publique pourrait avoir un rôle clé chez certaines startups, notamment dans les organisations telles que la Mairie de Paris qui souhaitent promouvoir l’innovation.

Quelques business sont porteurs dans cette phase de récession : la vente de coffres forts, les matières premières (quoique sujettes à de fortes variations comme le pétrole), la grande distribution (Wallmart est l’une des rares valorisations boursières à avoir augmenté depuis le début de l’année, cf ci-dessous, le Mondrian de SmartMoney), les écrans plats (vs les vacances), les logiciels libres, la prévention dans la santé, les services de base, les anxiolytiques et les ventes de produits sucrés (qui ont un effet antidépresseur).

La crise a au moins du bon dans un domaine : la récession réduit semble-t-il la consommation d’énergie. Avec le recul,  la course à la croissance est dangereuse pour la survie de l’humanité à moyen terme du fait de l’épuisement des ressources de la planète et de son impact environnemental. Trouver le moyen de gérer une “décroissance positive” serait un beau projet pour la survie de l’humanité…. mais on s’éloigne.

Quelques conseils

Le tableau est bien sombre, et malgré tout, les créateurs d’entreprises n’ont jamais été aussi nombreux. C’est rassurant car cela montre l’énergie qui subsiste, notamment chez les jeunes. Alors, voici à leur intention quelques conseils basiques :

• Constituez une équipe très solide (interne, board, advisory board, …).
• Créez un service ou produit avec des facteurs différentiateurs clairs et forts par rapport à la concurrence ou aux solutions établies. Evitez la solution “nice to have”. Votre présentation doit générer chez le client le sentiment pressant du “je le veux tout de suite” !
• Travaillez finement la monétisation de votre offre. Ne la repoussez par au jour où vous ferez de l’audience. Soyez à la fois précis et souples dans votre modèle de monétisation.
• Trouvez des sources de financement diverses non dilutives pour créer le produit et attirer les premiers clients / consommateurs. Puis faites appel à des business angels en profitant de l’effet Loi TEPA qui, on l’espère, ne va pas entièrement disparaître du fait de la crise. Ne faites pas trop de plans sur la comète sur une levée de 3m€ dans 12 mois. Vos chances, certes non nulles, sont très faibles d’y parvenir (moins de 200 projets par an en France en tout et pour tout).
• Faites de la qualité : présentations, supports, produit/service, relations, fiabilité. Il y a encore trop de médiocrité, et la qualité, cela se remarque !

Et si vous en avez la possibilité, venez à la conférence Leweb pour vous remonter le moral avec son thème “Love”. Quitte, vu le prix, à être invité par l’un des sponsors, ou à y assister à distance par l’un des webcasts qui ne manqueront pas de la relayer !

This is the ninth post in an article series about MIT’s lecture course “Introduction to Algorithms.” In this post I will review lectures thirteen and fourteen. They are on theoretical topics of Amortized Analysis, Competitive Analysis and Self-Organizing Lists.

Amortized analysis is a tool for analyzing algorithms that perform a sequence of similar operations. It can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a single operation within the sequence might be expensive. Amortized analysis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the average performance of each operation in the worst case.

Lecture thirteen looks at three most common techniques used in amortized analysis - Aggregate Analysis, Accounting Method (also known as Taxation Method) and Potential Method.

Competitive analysis is a method that is used to show how an Online Algorithm compares to an Offline Algorithm. An algorithm is said to be online if it does not know the data it will be executing on beforehand. An offline algorithm may see all of the data in advance.

A self-organizing list is a list that reorders its elements based on some self-organizing heuristic to improve average access time.

Lecture fourteen gives a precise definition of what it means for an algorithm to be competitive and shows a heuristic for a self-organizing list that makes it 4-competitive.

Lecture 13: Amortized Algorithms

Lecture thirteen starts with a question - “How large should a hash table be?” Well, we could make it as large as possible to minimize the search time, but then it might take too much space. We could then try to make it as small as possible, but what if we don’t know the number of elements that will be hashed into it? The solution is to use a dynamic hash table that grows whenever it is about to overflow.

This creates a problem that at the moment of overflow the table must be grown and growing it might take a lot of time. Thus, we need a way to analyze the running time in a long run.

Lecture continues with three methods for this analysis, called amortized arguments - aggregate method, accounting method, and potential method.

In aggregate analysis, we determine an upper bound T(n) on the total cost of a sequence of n operations. The average cost per operation is then T(n)/n. We take the average cost as the amortized cost of each operation, so that all operations have the same amortized cost.

In accounting method we determine an amortized cost of each operation. When there is more than one type of operation, each type of operation may have a different amortized cost. The accounting method overcharges some operations early in the sequence, storing the overcharge as “prepaid credit” on specific objects in the data structure. The credit is used later in the sequence to pay for operations that are charged less than they actually cost.

Potential method is like the accounting method in that we determine the amortized cost of each operation and may overcharge operations early on to compensate for undercharges later. The potential method maintains the credit as the “potential energy” of the data structure as a whole instead of associating the credit with individual objects within the data structure.

Each method is applied to dynamic tables to show that average cost per insert is O(1).

You’re welcome to watch lecture thirteen:

Topics covered in lecture thirteen:

• [01:05] How large should a hash table be?
• [04:45] Dynamic tables.
• [06:15] Algorithm of dynamic hash tables.
• [07:10] Example of inserting elements in a dynamic array.
• [09:35] Wrong analysis of time needed for n insert operations.
• [12:15] Correct analysis of n insert operations using aggregate analysis method.
• [19:10] Definition of amortized analysis.
• [21:20] Types of amortized arguments.
• [23:55] Accounting method (taxation method) amortized analysis.
• [29:00] Dynamic table analysis with accounting (taxation) method.
• [40:45] Potential method amortized analysis.
• [54:15] Table doubling analysis with potential method.
• [01:13:10] Conclusions about amortized costs, methods and bounds.

Lecture thirteen notes:

Lecture 13, page 1 of 2.
Lecture 13, page 2 of 2.

Lecture 14: Competitive Analysis and Self-Organizing Lists

Lecture fourteen starts with the notion of self-organizing lists. A self-organizing list is a list that reorders itself to improve the average access time. The goal is to find a reordering that minimizes the total access time.

At this point the lecture steps away from this problem for a moment and defines online algorithms and offline algorithms: Given a sequence S of operations that algorithm must execute, an online algorithm must execute each operation immediately but an offline algorithm may see all of S in advance.

Now the lecture returns to the self-organizing list problem and looks at two heuristics how the list might reorganize itself to minimize the access time. The first way is to keep a count of the number of times each element in the list is accessed and reorder list in the order of decreasing count. The other is move-to-front heuristic (MTF) - after accessing the element, move it to the front of the list.

Next the lecture defines what it means for an algorithm to be competitive. It is said that an online algorithm is α-competitive if there is a constant k such that for any sequence of operations the (running time cost of online algorithm) <= α·(running time cost of an optimal offline algorithm (also called "God's algorithm")) + k.

Lecture continues with a theorem that move-to-front is 4-competitive for self-organizing lists. The proof of this theorem takes almost an hour!

Topics covered in lecture fourteen:

• [01:00] Definition of self-organizing lists.
• [03:00] Example of a self-organizing list (illustrates transpose cost and access cost).
• [05:00] Definition of on-line and off-line algorithms.
• [08:45] Worst case analysis of self-organizing lists.
• [11:40] Average case analysis of selforganizing lists.
• [17:05] Move-to-front heuristic.
• [20:35] Definition of competitive analysis.
• [23:35] Theorem: MTF is 4-competitive.
• [25:50] Proof of this theorem.

Lecture fourteen notes:

Lecture 14, page 1 of 2.
Lecture 14, page 2 of 2.

Have fun with amortized and competitive analysis! The next post will be about dynamic programming!

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”):

After porting our production application to Rails 2.2, we noticed a major memory leak.

Beforehand, monit would restart instances a handful of times a day. After Rails 2.2, monit restarted instances THOUSANDS of times a day.

This is a graph of one of our haproxy instances a couple days ago.

We looked at everything, including time spent rewriting Routes, thinking that was the culprit.

This morning, we all sat around and fought the issue old school style. binary debugging... and found it: AssetTagHelper. See the patch here.

The new thread-safe asset tag code keeps a static AssetTag::Cache = {} of all asset_tags created (css,jss, and all images).

Internally, each AssetTag object keeps a reference to the controller and template objects, and in turn all instance variables you created in your request.

What does that mean? Say you have a people controller, that loads a person and their stuff, and you show images of their stuff via image_tag().

 class PeopleController < ApplicationController
   def show
     @person = Person.find(params[:id])
     @stuff = @people.stuff.find(:all, :limit => 30)
   end
 end

When image_tag() is called, it does rails magic to append file extensions, asset_ids, and the like. To be smart, it caches those objects so it doesnt hit the file system to figure all that out on every request. The problem is it puts it in a static cache, AssetTag::Cache.

So each PeopleController instance has a reference to 1 person and 30 Stuffs. After 1000 people look at their pages, or better yet google crawls your site, you have 1k @controllers with a total of 1000 People Objects, and 1000*30 Stuff objects. This would normally be fine. The objects leave scope and get GC'ed. But, if you generate an image tag to an unique asset, AssetTag puts that into a cache, AssetTag::Cache, with a reference to the @controller of the request. So All People and their Stuff are kept around forever, unable to be GC'ed.... every time a unique image is rendered via AssetTag. Eventually monit has to kill the process.

The patch we just submitted does 2 things.

1) It now keeps a cache of just the modified path strings, caching the file access stuff. If you have tons of local images, reference them by fully qualified host. Thats better for lots of reasons. Cookie-less asset hosts with multiple subdomains FTW!

2) It stops caching absolute URL paths. You cant do anything on the filesystem to verify them, and keeping a cache of those would also grow unbounded. We have millions of items in our system, each with a reference to an image.

Here is a graph of that haproxy today... Sleeping.........

In order to do some testing of your own, here's a simplistic after_filter you can add to application.rb (or is it now application_controller.rb?). Make sure you run this in production mode or with cache_classes = true. As you click around your site, you should see that the cache retains references to controller instances, just to name a few. After you apply the patch, you'll see the cache is just strings.

 def assettag_cache
    puts "-"*80
    puts "[AssetTag::Cache] Now #{ActionView::Helpers::AssetTagHelper::AssetTag::Cache.size} items"
    ActionView::Helpers::AssetTagHelper::AssetTag::Cache.values.each do |asset_tag|
      if asset_tag === ActionView::Helpers::AssetTagHelper::AssetTag
        puts "   [Asset] #{asset_tag.instance_variable_get("@source")}  #{asset_tag.instance_variable_get("@controller").class.to_s}"  
      else
        puts "   [Asset] #{asset_tag}"  
      end
    end
  end

Ohh... and we havent given up on routes... Warren is working on some very interesting enhancements to rails routing. Looking forward to blogging about that soon.

Peter Nederlof of the infamous Dutch "Lost Boys" created a 3D engine in Canvas.

Straight from the horse's mouth:

I've been working on a 3D engine on canvas for some time, and as I was posting a message on our blog, I figured you guys might be interrested as well :)

The demo is over here: http://www.xs4all.nl/~peterned/3d/

Another (completely useless but fun to watch) one is over here (and
using chrome is strongly advised): http://www.xs4all.nl/~peterned/3d/psychedelic3D.html

Ultimately the purpose of this engine would be to provide an easy to
use platform/interface for creating 3D stuff, from degrading interface
elements for sites, to complete games. Collada support is en route,
and with squirrelfish hitting air, I'm considering trying that too :)

More details are available on the Lost Boys blog.

As I wrote in Daddy, Where's Your Phone?, it's time to start thinking of the phone as a first class device for accessing web services, not as a way of repurposing content or applications originally designed to be accessed on a keyboard and big screen. The release of speech recognition in Google Mobile App for iPhone continues the process begun with the iPhone itself, of building a new, phone-native way of delivering computing services. Here are two of the key elements:

1. Sensor-based interfaces. Apple wowed us with iPhone touch screen, but the inclusion of the accelerometer was almost as important, and now Google has shown us how it can be used as a key component of an application user interface. Put the phone to your ear, and the application starts listening, triggered by the natural gesture rather than by an artificial tap or click. Yes, the accelerometer has been used in games like tilt, parlor amusements like the iPint, but Google has pushed things further by integrating it into a kind of workflow with the phone's main sensor, the microphone.
   

   
   This is the future of mobile: to invent interfaces that throw away the assumptions of the previous generation. Point and click was a breakthrough for PCs, but it's a trap for mobile interface design. Right now, the iPhone (and other similar smartphones) have an array of sensors: the microphone, the camera, the touchscreen, the accelerometer, the location sensor (GPS or cell triangulation), and yes, on many, the keyboard and pointing device. Future applications will surprise us by using them in new ways, and in new combinations; future devices will provide richer and richer arrays of senses (yes, senses, not just sensors) for paying attention to what we want.
   

   
   Could a phone recognize the gesture of raising the camera up and then holding it steady to launch the camera application? Could we talk to the phone to adjust camera settings? (There's a constrained language around lighting and speed and focus that should be easy to recognize.) Could a phone recognize the motion of a car and switch automatically to voice dialing? And of course, there are all the Wii-like interactions with other devices that are possible when we think of the phone as a controller. Sensor based workflows are the future of UI design.
   

2. 
   Cloud integration. It's easy to forget that the speech recognition isn't happening on your phone. It's happening on Google's servers. It's Google's vast database of speech data that makes the speech recognition work so well. It would be hard to pack all that into a local device.
   

   
   And that of course is the future of mobile as well. A mobile phone is inherently a connected device with local memory and processing. But it's time we realized that the local compute power is a fraction of what's available in the cloud. Web applications take this for granted -- for example, when we request a map tile for our phone -- but it's surprising how many native applications settle themselves comfortably in their silos. (Consider my long-ago complaint that the phone address book cries out to be a connected application powered by my phone company's call-history database, annotated by data harvested from my online social networking applications as well as other online sources.)

This is an incredibly exciting time in mobile application design. There are breakthroughs waiting to happen. Voice and gesture recognition in the Google Mobile App is just the beginning.

In November 2007, we listed and reviewed 10 promising Semantic Web apps. A lot can happen in one year on the Internet, so we thought we'd check back in with each of the 10 products and see how they're progressing. What's changed over the past year and what are these companies working on now? The products are, in no particular order: Freebase, Powerset, Twine, AdaptiveBlue, Hakia, Talis, TrueKnowledge, TripIt, Calais (was ClearForest), Spock.

In our next post in this series, we're going to publish a completely new list of Semantic apps to watch! That's right, 10 more Semantic apps. Let us know your suggestions in the comments.

Sponsor

Freebase

Freebase is an open, semantically marked up database of information. It looks similar to Wikipedia, but Freebase is all about structured data and what you can do with it.

Freebase has been one of the more hyped companies in Semantic Web, leading to some skepticism that the product is too much like Wikipedia and offers nothing much new. In May '08, we attempted to dispel the Freebase skepticism. Our conclusion was that the structured database, API, creative commons licensing - among other things - all added up to a richer product than Wikipedia. Then in July, we reported that Freebase was about to hit 4 million topics in its collection - which at the time was 60% more than the English Wikipedia.

However, we noted some concerns with Freebase - "big gaps in the data" along with usability issues. In a follow-up article in August, we covered an interesting tool for browsing Freebase, called Freebase Parallax. Unfortunately, when we tried out a number of searches in Parallax, very few subjects were well populated.

RWW verdict one year later: still lots of work to do for Freebase, in terms of usability and useful data.

Calais (was ClearForest)

When we did our round-up one year ago, ClearForest had been recently acquired by Reuters and at that point it had a Web Service and a Firefox extension. What a change a year brings! ClearForest went on to release Calais, a toolkit of products that enable users to incorporate semantic functionality within their blog, content management system, website or application.

Since launching the Open Calais API early this year, over 6,000 developers have registered with it and the service is doing more than 1 million transactions a day. We wrote about the launch of Calais' easiest-to-use service yet, called SemanticProxy, at the end of September. Version 3.0 was released earlier this month and version 4 is expected by January 09.

RWW verdict one year later: