Resolving total-order using partial-orders

Resolving a total-order using partial-orders can be a tricky code to write. For an example, sorting can not be used because every pair can not be compared directly and doing it by enumerating through the list is also tricky. This is a common problem–among examples are Axis2 handler order resolution, build orders in ant/maven etc, and AI planning based use cases etc.

However, there is a standard way to solve this problem. The solution is creating a graph assigning dependencies as edges in a graph–which is a directed acyclic graph–and then doing a topology sort . The algorithm takes O(n) time and space where n is number of entities + number of rules, which is pretty reasonable.

Theoretical Computer Science Cheat Sheet

This is a nice cheat sheet on what they call “Theoretical Computer Science Cheat Sheet”, I have not heard of half of them–some we touched in the algo class. Once thing I learned there was, representing simple phenomenon—like the expected number of throws before getting N heads in a coin toss—very often lead to very complex math . So once in a while, when we–system guys–try to explain things we saw, those things could come handy.

Live sessions @ E-Science 2008

There is e-science 2008 conference going on these days, in Indianapolis. However, what I wanted to note is that they are streaming all sessions live ( , in real web2 fashion, with chat rooms for every sessions etc. Great to see the state of art is in real use, in addition to the fact that people can listen to interesting sessions even when they can not afford to be there in person.

Here Comes Everybody: The Power of Organizing Without Organizations is a free worldwide travel guide, and it look pretty nice. One nice thing is that it is created using so called crowd sourcing, just like Open source software or wikipedia. It is an example of many efforts that create high quality outputs by aggregating small outputs of a large group. I read a book called Here Comes Everybody: The Power of Organizing Without Organizations written by Clay Shirky ( Penguin Group 2008) and it discusses many interesting aspects of the power of collective wisdom and it dynamics.

One thing it says is that the reason for organizations to exists is that the communication overhead of arriving at agreements in a group (which needs Cn2 (combination) agreements with peer to peer negotiations that grow very fast with n), and typically organizations reduce the overhead by organization hierarchy or chain of command. However, Internet has changes the communications patterns (e.g. asynchronous messages, broadcasting, posting without knowing recipients) ; therefore, some tasks can be handled without formal organizations. There is lot more interesting stuff there.