A holiday puzzle: solution

I now discuss two solutions to the puzzle described in the last post — one for the special case of a linear grid, and the other for the general 2D grid.  I thank Johan Ugander and Shiva Navabi for very useful pointers (see the Comment in the last post, and a funny nerd snipe comic) — I will return to them below.  But first, here is a simple heuristic solution.

Continue reading


A holiday puzzle

I am afraid of gifts, both receiving and giving.  Luckily, I have been largely spared having to confront this challenge.  I am often (rightly) criticized that in rare occasions when I give, the gifts are often what I like, not what the receivers would.  People say gifting is an art — no wonder I’m bad at it.   It is therefore a pleasant surprise that I received a holiday gift a few days ago, and it is a fun puzzle.

Consider an infinite grid where each branch (solid blue line segment) has a resistance of 1 ohm, as shown in the figure below. fig-grid

What is the equivalent resistance between any pair of adjacent nodes?   In other words, take an arbitrary pair of adjacent nodes, labeled + and − in the figure, and apply an 1-volt voltage source to the pair (the dotted line connecting the voltage source to the grid is idealized and has zero resistance). Denote the current through the voltage source by I_0.  What is the value of the equivalent resistance R := 1/I_0?

Chances are such an interesting problem must have been solved.  But instead of researching on prior work and its history, why not have some fun with it.  We don’t have to worry about (nor claim any) credits or novelty with a holiday puzzle!

…. But I would appreciate any pointer to its history or solution methods if you do know.  Even a random guess of the answer will be welcome.

In the next post, I’d describe two methods: one is a simple symmetry argument for a special case, and the other a numerical solution for the general case.   Meanwhile, have fun and happy holidays!

A tale of two metrics: competitive ratio and regret

Throughout our work on data center workload management over the past few years, one common theme that emerged was that of online convex optimization. Whether we were looking at load shifting, dynamic right-sizing, geographical load balancing, or data center demand response, we consistently ended up with an online convex optimization problem that we needed to solve. So, I wanted to do a short post here highlighting something particularly surprising (at least to us) that we uncovered last year.

Continue reading

Residual Lives, Hazard Rates, and Long Tails (Part II)

This is part II in a series on residual life, hazard rates, and long-tailed distributions. If you haven’t read part I yet, read that first! The previous post in this series highlighted that one must be careful in connecting “heavy-tailed” with the concepts of “increasing mean residual life” and “decreasing hazard rate.”

In particular, there are many examples of light-tailed distributions that are IMRL and DHR. However, if we think again about the informal examples that we discussed in the previous post, it becomes clear that IMRL and DHR are too “precise” to capture the phenomena that we were describing. For example, if we return to the case of waiting for a response to an email, it is not that we expect our remaining waiting time to be monotonically increasing as we wait. If fact, we are very likely to get a response quickly, so the expected waiting time should drop initially (and the hazard rate should increase initially). It is only after we have waited a “long” time already, in this case a few days, that we expect to see a dramatic increase in our residual life. Further, in the extreme, if we have not received a response in a month, we can reasonably expect that we may never receive a response, and so the mean residual life is, in some sense, growing unboundedly, or equivalently, the hazard rate is decreasing to zero. The example of waiting for a subway train highlights the same issues. Initially, we expect that the mean residual life should decrease, because if the train is on schedule, things are very predictable. However, once we have waited a long time beyond when the train was supposed to arrive, it likely means something went wrong, and could mean the train has had some sort of mechanical problem and will never arrive.

Continue reading

Residual Lives, Hazard Rates, and Long Tails (Part I)

This is the third series of posts I’m writing on topics related to what we are covering in our book on heavy-tails (which I discussed in an earlier post). The first two were on the catastrohphe principle (subexponential distributions) and power laws (regularly varying distributions). This time I’ll focus on connections between residual life, hazard rate, and long tailed distributions.

Residual life in our daily lives

Over the course of our days we spend a lot of our time waiting for things — we wait for a table at restaurants, we wait for a subway train to show up, we wait for people to respond to our emails, etc. In such scenarios, we hold on to the belief that, as we wait, the likely amount of remaining time we will need to wait is getting smaller. For example, we believe that, if we have waited ten minutes for a table at a restaurant, the expected time we have left to wait should be smaller than it was when we arrived and that, if we have waited five minutes for the subway, then our expected remaining wait time should be less than it was when we arrived.

In many cases this belief holds true. For example, as other diners finish eating, our expected waiting time for a table at a restaurant drops. Similarly, subway trains follow a schedule with (nearly) deterministic gaps between trains and thus, as long as the train is on schedule, our expected remaining waiting time decreases as we wait. However, a startling aspect of heavy-tailed distributions is that this is not always true. For example, if you have waited a very long time past the scheduled arrival time for a subway train, then it is very likely that there was some failure and the train may take an extremely long time to arrive, and so your expected remaining waiting time has actually increased while you waited. Similarly, if you are waiting for a response to an email and have not heard for a few days, it is likely to be a very long time until a response comes (if it ever does).

Continue reading

Data centers & Energy: Did we get it backwards?

The typical story surrounding data centers and energy is an extremely negative one: Data centers are energy hogs.  This message is pervasive in the media, and it certainly rings true.  However, we have come a long way in the last decade, and though we certainly still need to “get our house in order” by improving things further, the most advanced data centers are quite energy-efficient at this point.  (Note that we’ve done a lot of work in this area at Caltech and, thanks to HP, we are certainly glad to see it moving into industry deployments.)

But, the view of data centers as energy hogs is too simplistic.  Yes, they use a lot of energy, but energy usage is not a bad thing in and of itself.  In the case of data centers, energy usage typically leads to energy savings.  In particular, moving things to the cloud is most often a big win in terms of energy usage…

More importantly, though, the goal of this post is to highlight that, in fact, data centers can be a huge benefit in terms of integrating renewable energy into the grid, and thus play a crucial role in improving the sustainability of our energy landscape.

In particular, in my mind, a powerful alternative view is that data centers are batteries.  That is, a key consequence of energy efficiency improvements in data centers is that their electricity demands are very flexible.  They can shed 10%, 20%, even 30% of their electricity usage in as little as 10 minutes by doing things such as precooling, adjusting the temperature, demand shifting, quality degradation, geographical load balancing, etc.  These techniques have all been tested at this point in industry data centers, and can be done with almost no performance impact for interactive workloads!

Continue reading

The Community Seismic Network: Citizen Science and the Cloud

We almost missed the chance to highlight that the cover story of the July, 2014 issue of the Communications of the ACM (CACM) is a paper by a Caltech group on the Community Seismic Network (CSN). This note is about CSN as an example of system in a growing, important nexus: citizen science, inexpensive sensors, and cloud computing.

CSN uses inexpensive MEMS accelerometers or accelerometers in phones to detect shaking from earthquakes. The CSN project builds accelerometer “boxes” that contain an accelerometer, a Sheevaplug, and cables. A citizen scientist merely affixes the small box to the floor with double-sided sticky tape, and connects cables from the box to power and to a router. Installation takes minutes.

Analytics in the Sheevaplug or some other computer connected to the accelerometer analyzes the raw data streaming in from the sensor. This analytics engine detects local anomalous acceleration. Local anomalies could be due to somebody banging on a door, or a big dog jumping off the couch (frequent occurrence in my house), or due to an earthquake. The plug computer or phone sends messages to the cloud when it detects a local anomaly. An accelerometer may measure at 200 samples per second, but messages get sent to the cloud at rates that range from one per minute, to one every 20 minutes. The local anomaly message includes the sensor id, location (because phones move), and magnitude.

There are four critical differences between community networks and traditional seismic networks:

  •  Community sensor fidelity is much poorer than that of expensive instruments.
  •  The quality of deployment of community sensors by ordinary citizens is much more varied than that of sensors deployed by professional organizations.
  • Community sensors can be deployed more densely than expensive sensors. Think about the relative density of phones versus seismometers in earthquake-prone regions of the world such as Peru, India, China, Pakistan, Iran and Indonesia.
  • Community sensors are deployed where communities are located, and these locations may not be the most valuable for scientists.

Research questions investigated by the Caltech CSN team include: Are community sensor networks useful? Does the lower-fidelity, varied installation practices, and relatively random deployment result in networks that don’t provide value to the community and don’t provide value to science? Can community networks add value to other networks operated by government agencies and companies? Can inexpensive cloud computing services be used to fuse data from hundreds of sensors to detect earthquakes within seconds?

Continue reading