Fixed-point algorithms often find the wrong fixed point, an essay argues

The essay starts from a common task in compilation and program analysis: solving systems of the form x = f(x). The author's complaint is that when people are asked to design an algorithm for such fixed points, they rarely stop to ask which fixed point they want.

In practice the functions of interest are monotone: given a partial order, a smaller input never gives a larger output. Under that condition Tarski's fixed point theorem usually applies. If the domain forms a complete lattice, so does the set of fixed points, so there is exactly one least and one greatest fixed point. For a power set, the author notes, subset can serve as the order, union as join and intersection as meet.

The author's observation is that when people do not pay attention to which fixed point they need, they consistently write algorithms that converge to the least or the greatest one, depending on the problem. In the author's words, it is as though everyone has a common blind spot covering one of the extreme fixed points.

The first example is dead value (useless variable) elimination. The naive routines start with every value marked live and prune away values that are only used to compute other useless values, until nothing is left to remove. The results are correct but suboptimal, except for cycle-free code. They miss obviously useless values, such as x in a loop whose body is x = x. The author says special cases could be added forever; the simplest correct fix is to look for live values instead. Return values and writes to memory are always live, and a value is live if it is used to compute a live value. The routine starts with only the always-live values and adds live values as it finds them, until nothing more can be added. Here the intuitive solution converges to the greatest fixed point, but the least is wanted, and choosing the right initial value gets the right one. The author names two other common instances of the pattern: reference counting instead of marking, and type propagation that starts by assigning the top type to all values (like SBCL).

The second example is outside computer science. Most university and CEGEP student unions in Quebec will vote, or already have voted, on strike mandates to organize protests against rising tuition fees this winter and spring. The author says there are hundreds of such unions, representing around four hundred thousand students in total. Most have a couple hundred students or fewer, and many members feel a strike by a tiny number of students would be counter-productive. So mandates commonly require a minimum number of other students who also hold strike mandates, plus lower bounds on the number of unions and of universities or colleges involved. As far as the author knows, all mandates adopted so far are monotone: if a set of striking unions satisfies one, so does every superset. Tarski's theorem therefore applies, with subset, union and intersection on the power set of the unions.

The author argues the wanted fixed point is the one with the largest set of striking unions. The least fixed point could trivially be the empty set, or just the unions that set no lower bound. Mandates are also usually presented as a promise that if unions representing at least n0 students adopt the same mandate, all of them strike simultaneously.

The author asked fellow computer science graduate students to sketch an algorithm to decide which unions should strike. They began with the unions currently on strike and added unions whose conditions were all met. That converges to the least fixed point. In a hypothetical case, two unions of 5,000 students each share a strike floor of 10,000 students, and such an algorithm leaves both deadlocked, each waiting for the other. The author's alternative is to assume every union with a strike mandate is on strike, then repeatedly remove unions whose conditions are not all met, until the greatest fixed point is reached. The author is fairly sure this will stay a purely theoretical concern, but calls it a neat case of abstract mathematics helping interpret a real situation.

The closing point is general. Converging to a suboptimal solution seems to come up often with fixed points, and it is not necessarily a bad choice. Conservative initial values tend to converge faster and often keep intermediate solutions correct (feasible). When results are needed quickly, settling for a suboptimal answer may make sense. But it should be a deliberate choice, not a result of never considering the alternatives.

Key facts

Under Tarski's fixed point theorem, a monotone function on a complete lattice has exactly one least and one greatest fixed point, and the author says people often write algorithms that reach the wrong one.
Naive dead value elimination starts with every value live and prunes; it converges to the greatest fixed point, but the least is wanted. Starting from return values and memory writes, which are always live, fixes it.
Quebec student strike mandates are the second example: the author argues the wanted outcome is the largest set of striking unions, so the algorithm should start with all unions on strike and remove those whose conditions fail.
A bottom-up approach would deadlock two hypothetical 5,000-student unions that each need 10,000 students on strike, each waiting for the other.
The author adds that conservative initial values converge faster and often keep intermediate solutions feasible, so a suboptimal result can be a fine but deliberate choice.

Why it matters

Fixed-point computations sit under many tasks in compilation and program analysis, and the essay's point is that the choice of starting value decides which solution you get. The author shows the same mistake in two unrelated settings: compiler dead value elimination, where starting from the wrong extreme misses useless values, and strike coordination, where it produces a deadlock. Reference counting instead of marking and type propagation from the top type are named as further instances of the pattern.

Who it affects

Mainly people who write compilers, program analyses and similar iterative solvers, since the author frames the issue around those tasks. The strike example speaks to anyone designing a rule system where groups commit conditionally on each other, such as the Quebec student unions the author describes, which number in the hundreds and represent around four hundred thousand students.

How to use it

Before coding an iterative solver for x = f(x), ask which fixed point you want: the least or the greatest. Then pick the initial value that leads there. For dead value elimination, start with only return values and memory writes live and add values that feed live ones. For the strike mandates, start with all unions with a mandate on strike and remove those whose conditions are not met. If you deliberately start from a conservative value for speed or because intermediate solutions stay feasible, make that a conscious choice.

How solid is it

This is one author's essay built on a standard result, Tarski's fixed point theorem, and on reasoning about two examples. The dead value example is described in words only; no code, formal algorithm or benchmark is given. The claim that humans consistently pick the wrong extreme rests on the author's own observation and on asking fellow computer science graduate students, with no wider study. The author is not named in the source text.

Risks and caveats

The strike example is hypothetical: no real union or real deadlock is named, and the 5,000 and 10,000 student figures are an illustration. The author assumes all current mandates are monotone, qualified with 'as far as I know', and is fairly sure the issue will be only a theoretical concern. The source does not say any union or organizer adopted the proposed algorithm. The author also notes that settling for a suboptimal fixed point can be reasonable when quick results are needed.

“It’s as though we all have a common blind spot covering one of the extreme fixed points.”

— the essay's author