Imagine you are a child pitted in a battle of wits against a malevolent Santa Claus. Santa has lined up 1,000 boxes on a table and has stipulated that you must consider each box, in the order they are lined up, exactly once and must either choose to open that box or pass on it to never return to it again. Santa has hidden presents in half of the boxes and tells you that you must play the game until you find a present and that further, you must play the game in such a way that you are guaranteed to find a present. Now here’s the terrible part, and if there are any kids in the room, you may want to send them out while you read this: every time you open a box, you receive a mild electric shock.
So your problem is to design an algorithm for opening the boxes that 1) always finds a present; and 2) opens the smallest number of expected boxes. Think you need to open 501 boxes? Think again! 32 boxes are actually possible in expectation. And no, it’s not as simple as opening a random sample of boxes of log size, because remember your algorithm must always find a prize.
Now comes the part in my blog where I need to justify the government paying me money to think up these twisted stories. Well this problem is actually related to robust communication in sensor networks. The boxes represent time steps; opening a box corresponds to listening on a channel in a given time step; a box with a present corresponds to a time step in which someone has sent a message; and the shocks represent power expenditure for being awake in a give step. And the bad Santa? Well that’s just a story we use to scare undergrads.
If you’re interested in the solution to this problem and some variants, take a look at our paper Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks from PODC ’08.
Addendum: The reason I find this problem interesting is not because of the sensor network application or even because of the cute puzzle. Rather the problem gives rise to an interesting model for security based on attacker-defender games. For example, a big goal of cryptography is to allow a defender to spend a polynomial time budget to defend the privacy of a message against an attacker that spends an exponential time budget. One implication of the above “bad santa” result that we’re currently working on is allowing a defender to spend a bandwidth budget of x to defend against a denial of service attack from an attacker spending a budget of x^2. I really think these types or games are the way we need to be thinking about security in general. More on this later.
4 Comments so far
Leave a comment