The Windows Browser Ballot, the browser selection screen that is being offered to Windows users in Europe starting this month, is already coming under fire. Slovakian IT news site DSL.sk decided to test the ballot and found that its distribution was very peculiar, with Internet Explorer appearing in the rightmost position almost 50 percent of the time when the ballot was viewed from within IE.
Notable ODF proponent and IBM employee Rob Weir took a closer look at the ballot to determine why it was acting in this way. It turns out that the problem is more likely than not a bad programming decision rather than some deliberate ploy by Microsoft to pick a particular spot.
What DSL.sk noticed, and Rob Weir confirmed, is that the distribution is not uniform. That is to say, different browsers have different probabilities of landing in a particular position. Chrome was more likely to occupy one of the first three slots than any other browser, and IE had a better than 50 percent chance of being in the fifth slot. Different browsers produced different results; DSL.sk's testing used Internet Explorer, and Rob Weir found Firefox also gave a nonunform distribution. A different distribution from Internet Explorer, but nonuniform all the same.
Technically, the decision only requires randomness, not a uniform distribution (that is, one in which each browser has the same likelihood of being placed in any given spot), but given that the European Commission rejected previous suggestions such as a fixed display order, it is likely that a uniform distribution is the one that was intended.
Sorting is a common task for programming languages, but there are many different ways to sort. At their heart, most sort functions work by comparing two objects, and deciding if one is "less than" the other. For simply sorting of numbers, the normal "less than" comparison is what they use. But programs don't just sort lists of numbers. A list of cars could be sorted by model year, miles on the odometer, or license plate number. To make the sorting flexible enough to handle all these many situations, programming languages allow developers to specify just how the comparison should be done.
For the browser ballot, the comparison that Microsoft specified was a random one. Instead of actually comparing the two web browsers, the script generated a random number between zero and one, and checked to see if it was less than 0.5. This kind of comparison turns a sorting function into something that doesn't sort at all; instead, it makes it randomize the list that it is supposed to be sorting.
This approach might seem a bit strange, but in truth it's not an uncommon mistake to make. At first glance it looks like it does the right thing, and a lot of developers don't have the statistics knowledge to examine the results and determine whether the distribution is uniform or not, meaning that something that looks "about right" will satisfy them.
Moreover, this approach can do something that actually works, if the search function is written in a particular way. A particularly useful and extremely widespread sorting function called Quicksort when used with a random comparison appears to provide a uniform distribution. This further explains why the approach is so appealing to developers—not only does it look right, some of the time it is right, and the fact that it depends on the use of Quicksort (rather than any other sorting method) is not obvious. After all, for most applications, one sort method is just as good as any other.
So there's a very good chance that the issue here is an honest error. What is remarkable, though, is that it exists. This browser ballot, as simple as it is, has been months in the making. The decision to do the randomization client-side, where it depends on the web browser, rather than server-side, where it would be consistent for all users, is a little surprising. But most remarkable at all is that no one responsible for signing off and saying "that's an acceptable response to the Competition Commission's complaint" bothered to do this testing. If this browser ballot is important then surely its implementation should be a high quality one?