The k-server problem: some progress, still wide open

Aleksander Mądry gave a stellar talk at our ARC Theory Day a week ago Friday. He is an expert on algorithmic graph theory, among other areas of theory. Already he has multiple best-paper awards, including the paper of this talk from FOCS 2011, and I expect he will get more in the future. This is good going considering that basic LaTeX systems lack a macro for the Polish ogonek diacritic in his name—Ken installed a special package called tipa to get it while editing this post.

Today I would like to talk about his result and the open questions that remain.

He with Nikhil Bansal, Niv Buchbinder, and Seffi Naor (BBMN) have made a recent important contribution to our understanding of the complexity of on-line algorithms. Aleksander’s talk was wonderful and explained what is known, their new result, and what still remains to be done. As he said:

One of the remaining open questions is really annoying—it should be solved—but it continues to resist attacks.

Before I discuss their result I would like to thank the Theory Day organizers Prasad Tetali and Prasad Raghavendra. It was held on the magical day 11/11/11, which does not happen that often, and in fact Mądry’s talk spanned 11:11:11am. Ken wore a red shirt in Buffalo but could not find the WW I remembrance poppy pin he acquired during his sabbatical in Canada. The full scorecard of talks and titles was:

Thomas Dueholm Hansen: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm.

Aleksander Mądry: Online algorithms and the k-server conjecture.

Mohit Singh: A Randomized Rounding Approach for Symmetric TSP.

Ryan Williams: Algorithms for Circuits and Circuits for Algorithms.

The Problem

The problem he spoke about is the now classic on-line server problem. The simplest case is the problem of managing a computer $. Note that this is the way to tell a theory talk on computer caches from an architecture talk on computer caches—in architecture often $ is used to denote a cache. Perhaps this is changing, given the current economic turmoil, perhaps not.

The key is that there are pages in the cache and total pages. Each time a page is requested, if it is not in the cache the task is to decide which page to “evict” from the cache. If the strategy is deterministic, then as Danny Sleator and Bob Tarjan proved back in 1985, the best strategy is only -competitive. This means that the best deterministic strategy could be as bad as times the best off-line strategy which is allowed to see all the page requests at once.

Randomization comes to the rescue. If the strategy for eviction can be random, then it is known that an on-line random strategy exists that is competitive. This is due to Amos Fiat, Dick Karp, Mike Luby, Lyle McGeoch, Danny Sleator, and Neal Young in 1991.

The paging problem is just a special case of the general -server problem. In the general case the simple cache mechanism is replaced by one based on an arbitrary finite metric space. The servers at any step are located somewhere on the points of the metric space. The requests are to “serve” a point in the space: a server must move to that point, and it incurs a cost of the distance in the metric.

In the 1990′s this problem was very “hot,” and there was a stream of results that tried to get good deterministic server strategies. The first results were exponential in but independent of : recall there are servers and the space has points. Finally—in a famous paper—Elias Koutsoupias and Christos Papadimitriou 1994 showed that there is a strategy achieving , which remains today the best known result.

The BBMN Result

The new result is:

Theorem 1 There exists an -competitive on-line strategy for the -server problem.

This is a great improvement, but it also changes the rules. It is great since the competitiveness bound is poly-log in . However, all the previous results we discussed had competitiveness bounds that did not depend on the size of the metric space, . Their result does.

See their paper for the proof. The key idea is that they: Reduce the -server problem over arbitrary metric to a (more difficult) problem over a very simple metric The very simple metric is a type of tree-like metric. The proof relies on the fact that any metric space on points can be well approximated by such a metric space. The cost of the approximation grows roughly as , so it is not surprising that their theorem has factors of in the competitiveness bound.

Open Problems

The -server problem has the following bounds and gaps in those bounds:

If the strategy is deterministic it must take and can be done in . There is a small, but annoying gap of two here. Which is correct?

If the strategy is randomized it must take . There is a huge and annoying gap to the known upper bounds here. There is no known strategy for even the simple case of the real line that is randomized but beats linear in . What is going on?
Finally, are the polylog factors of in their result necessary? In particular can one get rid of the dependence on altogether?

[fixed typo in Fiat et al. to O(log k)]

The three meanings of complexity

Steven Nixon is an expert on national security policy. He has been recognized for distinguished work in the various fields of engineering, intelligence, Congressional staff advising, and space policy. He has worked for various government agencies in the past, and has now founded his own firm, Steven Nixon Consulting.

Today I want to report on a discussion of complexity theory—but not in our sense.

I just heard Nixon speak at a conference run by a group called TTI/Vanguard. They are a for-profit organization that organizes conferences at which their subscribers can interact with leading lights. They run five conferences each year on various aspects of advanced technology. It costs quite a bit to be able to go to even one of their meetings—an order of magnitude more than our meetings and sold in blocks of five—but my “seat” is currently paid for by the College of Computing, so I attend a few of them each year.

Their meetings are fun, with interesting speakers who give strong talks, and structured for lots of audience interaction. We are encouraged to jump in and ask questions—attendees have their own microphones, so it is not too difficult to ask whatever is on your mind. They do not publish proceedings—mainly you have to be there.

This meeting’s focus was on “taming complexity.” As a theorist that is something that I would like to be able to do—is this why it’s called the Complexity Zoo? But, as you might have guessed, their notion of complexity is not our notion of complexity. This caused me think about the various uses of the word “complexity,” and what they mean. I could think of at least three types of complexity.

Three Roads to Complexity

Two major technical fields I know have areas that call themselves “complexity”—ours and dynamical systems. Yet the meaning used at the conference and discussed directly by Nixon was neither of these. Instead it reflects the way we use “complex” in ordinary speech: big, involved, hard-to-describe, requiring much effort even to comprehend. It included a cool notion that I think you may like called wicked problems, which I will define and discuss in a moment. This is different from our notion of a problem being wickedly hard—it has to do with framing the problem itself.

One of best quotes of the meeting was from Nixon’s talk, where he quoted the late President Dwight Eisenhower as once saying:

If a problem cannot be solved, enlarge it.

I wonder how we could use that to attack some of our problems. What does that mean for ?

Note that already we use problem in two senses: is a research problem, and it is about particular computational problems such as . The former easily enlarges itself—with a few special exceptions, we do not even know how to prove super-linear lower bounds on time or circuit size for problems within the possible range of feasibility. What I’m asking is whether we should enlarge our notion of computational problem, with due formalism including what it means to be complex. First let’s try to categorize the three meanings of complexity.

Complexity: Resource Based

When we say “complexity” we almost always are referring to the resources needed to compute and solve some problem. The resources measured can be: time, space, randomness, nondeterminism, rounds, quantum operations, or other resources. Indeed sometimes we mix these together to get measures that limit two or more resources.

In our complexity theory we like two types of results: upper bounds and lower bounds. An upper, of course, shows that some problem X can be solved in a certain resource bound. A lower shows that some problem X cannot be solved in a certain resource bound. For example, one of the great upper bounds is that we can sort numbers in at most comparisons, and the corresponding lower bound that comparisons are needed.

It is a shame that we cannot prove more such results, especially more lower bounds. But as we have talked before, many times, showing a lower bound is very difficult. It amounts to showing that there is no way to be “clever” and avoid some “obviously” required computations. Even the sorting result must be examined carefully. The lower bound relies on the fact that only comparisons are allowed between numbers. It is possible to sort faster than this if one can violate the model and do more than just comparisons.

A good example of this is the bead sort created by Joshua Arulanandham, Cristian Calude and Michael Dinneen in 2002—see here. There are potential hardware implementations that allow this method to run in linear time, but they seem not to be practical.

Initially the integers to be sorted are represented as numbers of beads. The beads for each integer occupy a row, and importantly, are left-justified in that row (diagrams from Wikipedia).

After the “fall” the poles contain the sorted order. The surprising point is that the individual beads making up each integer have been scrambled, but owing to the left-justification, one can prove that each integer is preserved in the final output.

I raise this example just to remind us how hard it is to envision all possible ways that can be used to tackle a problem—that is why lower bounds are so difficult.

Complexity: Behavior Based

A Google search for the word complexity hits another notion of complexity first. It finds the notion of “a complex system.” We are not far behind, but we are not first. When people think of complexity, not theorists, they usually think of systems that look like this:

When many say complexity theory, they usually are referring to the type of behavior of a system. This type of complexity theory is all about behavior, about prediction, about chaos, about the tremendous forking of paths (bifurcations) that can arise from even simple systems that evolve over time.

I wish, sometimes, that they had called their area something else other than complexity theory. But there is not much we can do about it now, since their use is well established and well funded. For example, the the Sante Fe Institute has the motto:

Complexity theory research expanding the boundaries of science.

Great motto—wish we had a cool one like this. Oh well.

There are many potential connections between our notion of resource based complexity and their behavior based complexity theory. Some of them may come through the theory of complexity over the reals and other infinite fields, aspects of which we covered here. I will leave more on those for another time.

Complexity: Real-World Based

One of the foundational assumptions that I believe is bedrock, solid, unchangeable, cannot question, is that theory has made progress by its way of formulating problems as objects of analysis in themselves. I will not budge on this issue. But Nixon’s talk recently made me question the related assumption this this manner of stating problems encompasses all the ones we can rigorously attack.

The key is the notion of a wicked problem(WP). It is not that easy to define what they are, but here is the standard list of properties they have:

The problem is not understood until after the formulation of a solution.
Solutions to wicked problems are not right or wrong.
Every wicked problem is essentially novel and unique.
Every solution to a wicked problem is a “one shot operation.”
Wicked problems have no given alternative solutions.

The notion of a WP is not new. In 1967 West Churchman introduced the concept of wicked problems in a journal article, where he discussed the moral responsibility of Operations Research

to inform the manager in what respect our `solutions’ have failed to tame his wicked problems.

Horst Rittel and Melvin Webber formally described the concept of wicked problems later in 1973 where they contrasted WP’s from “trivial” problems such as those from mathematics, chess, or puzzle solving. Ouch. I believe that these problems are pretty “wicked,” but I do agree that they are not wicked in the sense used by Churchman, Rittel, and Webber.

I like the idea that some problems are inherently wicked. That they do not have precise statements of what is the problem. Therefore they may not have solutions, at least not in the usual sense. I wonder if it is possible to help develop a theory of WP’s? To develop a theory that addresses problems that are not well stated. Does this even make sense, or is this an impossible task?

I think it is not. Perhaps the start of a model could be based on algorithmic game theory. Imagine that a group of players have conflicting notions of what they want for a solution. Could notions from game theory help make sense of this? Is the very beauty of the the idea of a Nash Equilibrium a type of solution to a problem that at one time appeared to be wicked?

Open Problems

Can we help and formalize the notion of a wicked problem? What would such a theory look like?