Probably Approximately Correct

No, No. I am not referring to the English(Indian) Premiere League or Serie A. Those are the ones I am least concerned about these days. The past week or so has been very hectic for me. Hmm…..Hmm….. So, after an indecision/dilemma for about an year or so - its finally decided and fixed.

I will be graduating this convocation with a B.Tech (Hons) and a Masters by Research in Computer Sciences. The last week was spent in writing and compiling the first draft of this thing.

The title of the work will be “Agreement can be Easier than Point-to-Point Communication”. Informally, it is about the following — Given a network of computers, it may be possible that the computers will not be able to reliably communicate/route messages to each other but they can agree on something. Per se, agree on whether a database operation has aborted or been committed. In this work, we characterize the networks over which agreement is possible but Point-to-Point Communication is not (that is, we give the give the connectivity requirements of the network and the ratio of faults to non-faulty computers).

The result sounds both baffling and fishy at the first look as we generally expect any sort of agreement/consensus measures to have reliable communication as a prerequisite or may be even a sub-routine call in the process of reaching a consensus. Our results, however, prove otherwise - Consensus/agreement protocols seem to be more fundamental to network/distributed computing than Point-to-Point Communication!

I am nearly done with my burden and hence, hope to get back to blogging on things I left behind. A couple of drafts have been lying on the hard disk for sometime now :-)

[Esc]:wq