• Pareto Optimality and Computer Science

    I've been looking at resource allocation problems within data-centers lately. I think it's unlikely that someone working in this area does not come across the concept of Pareto optimality, so I thought I'd finally clear the cobwebs off this blog by writing about this.

    Pareto optimality is an economics concept developed by Vilfredo Pareto that has important applications in computer science.


    "You're welcome, computer nerds" - Vilfredo Pareto



    Simply said, in a Pareto optimal allocation of resources between multiple parties, no single party can be made better off without making at least another party worse off.

    Here's an example: if we have a pie and we divide it equally between Alice and Bob, it's impossible to improve the share for either one of them without negatively impacting the other. So if we divide the pie into two equal halves and give a half each to Alice and Bob, this is a Pareto optimal outcome.

    So is Pareto optimality always desirable? Heck no.

    This is because Pareto optimality doesn't tell you anything about fairness, which is also a very desirable property when it comes to resource allocation. In our Alice and Bob example, consider an allocation where the entire pie is given to Alice and Bob doesn't get any. Is it fair to Bob? Of course it isn't. Is it Pareto optimal? Yes, because you cannot increase Bob's share of the pie without taking an equivalent share away from Alice.

    So what exactly is optimal about a Pareto efficient allocation? To put it naively, it is an allocation where utilisation of available resources is the focus. This is quite natural considering the fact that the concept was designed within economic theory because in an economic system, it is not desirable that supply is under-utilised when there are still demands to be met.

    In most practical situations involving computer systems, resources are allocated incrementally between different individuals (as opposed to a one time allocation). As an example, in an IaaS setup like Amazon EC2, the system needs to provision resources on a continuous basis by keeping up with incoming demands by different tenants. In such a scenario, you're matching a pool of resources (like compute cores, disk, etc.) to an incoming demand vector from a tenant on the fly. Now if this tenant's demand is met such that all other tenants' allocations are at least as good as they were beforethen such an allocation is considered a Pareto improvement.

    Like the notion of Pareto optimality, Pareto improvements are also slightly weak. For instance, making a few allocations that aren't Pareto improvements as of now may allow the system to reach a much more desirable situation later.

    Going back to our pie example, assume we're in a scenario where Alice has been allocated the entire pie. Assuming the pie is big enough, it's unlikely that Alice would be able to eat the entire pie in one sitting without falling sick. Now if we take all that extra pie from Alice and give it to Bob, it isn't a Pareto improvement because Bob is now better off at the immediate cost of Alice, but Alice is eventually better off by not falling sick. This is now a much more desirable outcome, and is also Pareto optimal. Similarly, your operating system's scheduler may have to slow down your massive compilation process if you want to be able to watch a youtube video at the same time.

    The set of Pareto optimal choices in a system is called the Pareto frontier. Given a finite set of data-points, one can compute the Pareto frontier through skyline query algorithms.

    I'll stop here for now because my stomach's expressing its disgruntlement at being denied food for a longer period than usual. In a future post, I'll talk about Pareto optimality and its relation to Nash Equilibria.

  • Papers papers everywhere

    Last month, I officially began my PhD research. Not surprisingly, the difference from any prior research I've ever done is quite evident. Primarily because there is really no horizon at all when you embark on a PhD.

    The difficulty here essentially boils down to finding an answer to the following question: What problem is worth spending the next five years of your life trying to solve?

    I already have an idea of the broad area that I'd like to look into. Digging deeper and deciding which boundary to push at, however, is the tricky part.

    The workflow here is as follows:

    1) Read a paper. Creativity and optimism will immediately kick in, pointing you to potential opportunities and gaps, causing a rainbow of ideas to explode out of your brain. You shiver with excitement.

    2) Read another paper only to realise someone else has already done all of that and a little more.

    3) Repeat.

    Let's see how long it takes before I finally break from step 1.

    I'm not sure how I should end this post, so here's a picture of my desk.

    Many trees have died for the greater good here

     

  • Skyfall

    When you watch Skyfall with three fellow networking researchers, comments such as the following ensue:

    "Why is the list of all agents on a single file, on a single laptop hard drive, and encrypted so weakly that it's crackable in less than a week?"

    "Wait. How can you even trace someone after you strip the headers off the packet?"

    "That's a CISCO switch in that data center! ... Huh? What terrible wiring. Where's the cooling system? Is that a data center built with raspberry pies?"

    "I can see assembly code on that terminal."

    "Who the hell plugs-in a terrorist's laptop to your security sensitive internal network?"

    "From where does that little radio transmitter's antenna get that much power to transmit such a signal in the first place?"

    I love being around fellow nerds.

  • A note on education

    This talk from Seth Godin deeply resonates with my thoughts about education.

  • Mosquito love. Not.

    My two least favourite things about my hometown are mosquitoes and mosquitoes.

    A close third, would be load shedding. For those of you unfamiliar with the jargon, it's basically a daily state-wide planned powercut for saving unicorns. Or energy. Or something. I can't remember the details except that it's annoying. Especially that time it was scheduled to go off right in the middle of a Kung Fu Panda 2 airing on HBO. **Especially** when they seem to introduce the practice only when I'm home for vacations.

    So, let's say you're suffering from acute internetaddictionitis and the load-shedding kicks-in, leaving you hanging half-way through the Gangam Style video on Youtube, and also leaving you in the not-so-pleasant company of a squadron of mosquitoes. What do you do? Since there's no such thing as negotiation when it comes to these miniature vampires, the only option is battle.

    Now these aren't ordinary mosquitoes. These are mosquitoes that have been hardened in their craft through generations of exposure to mosquito repellents. I'm pretty sure that evolutionary processes have gifted them a gland that harvests these repellents and converts them into energy or some arthropod-adrenaline-equivalent.

    That said, mankind has had to resort to modern science in order to forge a weapon capable of taking on Satan's pets. Behold! The constant-voltage-electro-plasma-weave-scepter-3000. Or, for the less scientifically inclined, the mosquito bat.

    This is what Thor's hammer probably looked like

    Those of you who're from less threatened corners of the known universe might find this piece of technology rather overwhelmingly difficult to understand. But here's how it functions. The device works with the wielder holding the charge button, and swinging the device at a mosquito-monster, which upon successful contact, will deliver a very satisfyingly awesome spark thingy to the target. Sometimes, the target ends up stuck in the metal mesh, causing the mosquito to burn with the rather unpleasant odour of a burning mosquito.

    Whoever came up with this idea actually brought some fun into the endless and futile battle that routinely happens in most Indian households every evening.

    Anyhow, my entrepreneurial instincts tell me that there is room here for improvements.

    Enter gamification:

    • Turn these bats into Internet capable devices that can connect over WiFi, 3G, 4G, Parle-G, anything.
    • Users register their device(s) through an online account.
    • The device keeps track of the number of mosquitoes you pwn, and updates a score on a central server.
    • The more you kill, the more you gain experience.
    • As you gain experience, you level up. All users start at Lvl 1: Militia, and progress their way through to Lvl 100: Zeussian Mosquito Centurion Overlord. With each experience level, unlock features on your bat, like the anti-anthropod-plasma-cannon, and the zappa-mosquito-fragmentation-grenade-launcher.
    • Compete with friends, family, neighbours, or fellow countrymen to slay as many of these buggers as you can in mosquito zapping tournaments. Win exciting prizes!
    • Profit.

    See? No "???" in between.

    Unlike other capitalistic endeavours, this one is purely driven by a social angle which can be summed up by three words, "Kill. All. Mosquitoes." At the end of the day, we empower people with this device, and get rid of mosquitoes at the same time. Problem solved.

    Now to figure out how to solve the load-shedding problem.