James Hamilton studies some failures

Regular readers of my blog will know that I'm an enthusiastic proponent of the study of failure. When something unexpectedly goes wrong, there is always something to learn.

Thankfully, James Hamilton is a big supporter of that point of view as well, and happens to have written several wonderful essays over the past few weeks on the topic.

Firstly, Hamilton wrote about the Costa Concordia grounding, and then followed that up with a second essay responding to some of the feedback he got. This is obviously still an active investigation and we are continuing to learn a lot from it. Hamilton's essay has some wonderful visual charts illustrating the accident, and speculating on some of what was occurring, together with a massive amount of supporting information discussing what is currently known.

My favorite part of Hamilton's essay, though, is his conclusion:

What I take away from the data points presented here is that experience, ironically, can be our biggest enemy. As we get increasingly proficient at a task, we often stop paying as much attention. And, with less dedicated focus on a task, over time, we run the risk of a crucial mistake that we probably wouldn’t have made when we were effectively less experienced and perhaps less skilled. There is danger in becoming comfortable.

Very true, and very important words. Not to reduce it to the overly-mundane, but I recently got a traffic ticket for rolling through a stop sign and I had my opportunity for that once-a-decade visit to Traffic School. Although the fines and wasted time were an annoyance, it was clear by the end of Traffic School that in fact my 35 years of driving experience have become somewhat of an enemy; there were many specific details about how to drive safely and legally that I was no longer paying attention to, which the course materials recalled to the front of my mind.

There is, indeed, danger in becoming comfortable.

Secondly, Hamilton wrote about another fascinating incident: the loss of the Russian space mission Phobos-Grunt.

As Hamilton notes, there is a very interesting report on this incident in the IEEE Spectrum magazine: Did Bad Memory Chips Down Russia’s Mars Probe?.

But, as Hamilton observes, although the analysis of memory chips and radiation effects and system faults is fascinating and valuable, there is a further, deeper sort of failure:

Upon double failure of the flight control systems, the spacecraft autonomously goes into “safe mode” where the vehicle attempts to stay stable in low-earth orbit and orients its solar cells towards the sun so that it continues to have sufficient power.

...

Unfortunately there was still one more failure, this one a design fault. When the spacecraft goes into safe mode, it is incapable of communicating with earth stations, probably due to spacecraft orientation. Essentially if the system needs to go into safe mode while it is still in earth orbit, the mission is lost because ground control will never be able to command it out of safe mode.

...

Systems sufficiently complex enough to require deep vertical technical specialization risk complexity blindness. Each vertical team knows their component well but nobody understands the interactions of all the components.

Kudos to Hamilton for the well-researched and thoughtful observations, and for providing all the great pointers for those of us who, like him, love studying failures and their causes.

What failure will we be studying next? Well, it sure looks like there's a lot to learn from this one: The Air Force Still Doesn’t Know What’s Choking Its Stealth Fighter Pilots.

America’s newest stealth fighters have a major problem: their pilots can’t breathe, due to some sort of malfunction in the planes’ oxygen-generation systems. For months, the Air Force has been studying the problem, which temporarily grounded the entire fleet of F-22 Raptors and may have contributed to a pilot’s death. Today, the Air Force admitted they still don’t know exactly what’s causing the issue.

It looks like this question has been under study for several years, and may still take some time to resolve. The Wired article has a number of pointers to previous articles about the problem. I'll keep an eye on this one, eager to learn from the detailed analysis of the failures.

Online cryptography class delayed again

Prof. Boneh's online cryptography class has been delayed again. The announcement says "We now expect that the course will start either late in February or early in March," further explaining that "There have naturally been legal and administrative issues to be sorted out in offering Stanford classes freely to the outside world, and it's just been taking time. "

Still keeping my fingers crossed...

Download the Universe

What a wonderful idea!

How do we peer-review code?

There's a fascinating article in the current issue of Nature magazine online: The case for open computer programs, by Darrel C. Ince, Leslie Hatton & John Graham-Cumming.

The article deals with the problem of successfully and adequately peer-reviewing scientific research in this age of experiments which are supported by extensive computation.

However, there is the difficulty of reproducibility, by which we mean the reproduction of a scientific paper’s central finding, rather than exact replication of each specific numerical result down to several decimal places.

There are some philosophy-of-science issues that are debated in the article, but in addition one of the core questions is this: when attempting to reproduce the results of another's experiment, the reviewers may need to reproduce the computational aspects as well as the data-collection aspects. Is the reproduction of the computational aspects of the experiment best performed by:

1. taking the original experiment's literal program source code, possibly code-reviewing it, and then re-building and re-running it on the new data set, or
2. taking a verbal specification of the original experiment's computations, possibly design-reviewing that specification, and then re-implementing and re-running it on the new data set?

Hidden within the discussion is the challenge that, in order for the first approach to be possible, the original experiment must disclose and share its source code, which is currently not a common practice. The authors catalog a variety of current positions on the question, noting specifically that “Nature does not require authors to make code available, but we do expect a description detailed enough to allow others to write their own code to do similar analysis.”

The authors find pros and cons to both approaches. Regarding the question of trying to reproduce a computation from a verbal specification, they observe that:

Ambiguity in program descriptions leads to the possibility, if not the certainty, that a given natural language description can be converted into computer code in various ways, each of which may lead to different numerical outcomes. Innumerable potential issues exist, but might include mistaken order of operations, reference to different model versions, or unclear calculations of uncertainties. The problem of ambiguity has haunted software development from its earliest days.

which is certainly true. It is very, very hard to reproduce a computation given only a verbal description of it.

Meanwhile, they observe that computer programming is also very hard, and there may be errors in the original experiment's source code, which could be detected by code review:

First, there are programming errors. Over the years, researchers have quantified the occurrence rate of such defects to be approximately one to ten errors per thousand lines of source code.

Second, there are errors associated with the numerical properties of scientific software. The execution of a program that manipulates the floating point numbers used by scientists is dependent on many factors outside the consideration of a program as a mathematical object.

...

Third, there are well-known ambiguities in some of the internationally standardized versions of commonly used programming languages in scientific computation.

which is also certainly true.

The authors conclude that high-quality science would be best-served by encouraging, even requiring, published experimental science to disclose and share the code that the experimenters use for the computational aspects of their finding.

Seems like a pretty compelling argument to me.

One worry I have, which doesn't seem to be explicitly discussed in the article, is that programming is hard, so if experimenters routinely disclose their source code, then others who are attempting to reproduce those results might generally just take the existing source code and re-use it, without thoroughly studying it. Then, a worse outcome might arise: an undetected bug in the original program would propagate into the second reproduction, and might gain further validity. Whereas, if the second team had re-written the source from first principles, this independent approach might very well have not contained the same bug, and the likelihood of finding the problem might be greater.

Anyway, it's a great discussion and I'm glad to see it going on!

Time for the next generation

My daughter, who is studying computer programming using the Processing language, happened to be home (briefly) over the weekend, and one of her requests was about how she could start learning about Linux.

So off we went to the Ubuntu site, where a quick click on "Run it alongside Windows" took us to the Wubi installer.

Forty five minutes later, she was up and running Linux, poking about, asking questions, and generally online.

Make way, world, here comes the next generation!

ABC follows up on the NYT Foxconn story

Remember that New York Times article on the Foxconn factories that I blogged about last month?

Well, the ABC Nightline staff have followed up on that story, and David Pogue of the New York Times covers the ABC Nightline findings in a follow-up article on the New York Times website.

Sounds like there's still a lot to learn; I'm pleased that the media organizations are really devoting some resources to trying to do some serious journalism here.

UPDATE: Mike Daisey, the reporter who broke the original Foxconn story in the NYT, follows up some more, on his personal blog.

Pricing strategies and bots

From an intriguing post by Carlos Bueno: How Bots Seized Control of My Pricing Strategy:

we have a delightful futuristic absurdity: a computer program, pretending to be human, hawking a book about computers pretending to be human, while other computer programs pretend to have used copies of it. A book that was never actually written, much less printed and read.

The mind reels.

If this happens to be the first time that you've thought about pricing bots, drop everything else you're doing and go read Michael Eisen's great essay: Amazon’s $23,698,655.93 book about flies.

Code Reviews

Matt Welsh writes a great essay about all the wonderful aspects of code reviews.

I thoroughly agree. Code reviews are just about the best tool available to teams trying to improve their software.

Matt's essay discusses the many benefits of code reviews (yes, there are lots of benefits, for the reviewers, the reviewee, and for the overall organization), and suggests a number of useful tools and techniques for accomplishing them effectively.

What Matt doesn't discuss, unfortunately, is why it's so hard to get good code review practices established in an organization.

I've been in a lot of software development situations, with a lot of phenomenally great programmers. Sometimes there is a healthy code review culture, sometimes there isn't. And I still, after 30 years, don't understand why that is.

Invariably, executives will sing the praises of code reviews, teams will experience their benefits, but in practice it is very hard to consistently and thoroughly employ them.

Kudos to Google for making it happen, somehow; Welsh's article doesn't really say why Google has succeeded at this when so many other organizations fail.

Of course, there are many things at which Google succeeds while other organizations fail, so this result is neither surprising nor particularly illuminating in that respect.

Still, I suspect I'll wonder til the day I retire why it is that organizations will seem to grasp at so many other aspects of the software development process (team structures, agile methods, scrums and Kanban walls and burndown charts, IDEs, CI systems, project management automation, etc.) yet don't perform the basic and incredibly powerful technique of universally employing code review.

Does your organization have a code review culture? If so, how did it come about and how is it sustained?

Crowdsourcing the forecast

Here's a great story by Farhad Manjoo on Slate about how Weather Underground are rolling out their new locally-aware weather forecasting system.

Weather Underground’s system takes most of this NWS data into account, and then it adds even more. In particular, the site has assembled a huge network of constantly updating automated weather stations. These stations are owned and maintained by weather enthusiasts—people who love to track precipitation in their own backyards. They agree to share their data with Weather Underground because the site offers free archiving; you can see what your station was reporting months or years ago, easily, from anywhere.

Yeah, I know how that feels

Just when you think you've really found something significant this time...

It's not just a game ...

... It's a fully-customizable and extensible world inside your computer.

The Creation Kit has proved instantly popular. Bethesda said that gamers downloaded two million mods in the first three days of the service. As of this writing, there are over 3,636 mods available. Bethesda says it is not surprised by the speed with which both modders and players have integrated the new tools.

Meanwhile, have video games replaced movies as the art masterpieces of our time? Kevin Kelly discusses the question, inspired by Kyle Munttrick's enthusiastic essay: Why Mass Effect is the Most Important Science Fiction Universe of Our Generation.

Whether it is realistic science explaining humanoid life throughout the galaxy, or dealing with FTL travel, or the ethical ambiguity of progress, or even the very purpose of the human race in our universe, Mass Effect has got it. By virtue of three simple traits – its medium, its message, and its philosophy – Mass Effect eclipses and engulfs all of science fiction’s greatest universes.

Predictive analytics

Like many others, I was fascinated by the article in this Sunday's New York Times Magazine: Psst, you in aisle 5. (Curiously, in the online version of the article, the title is: How Companies Learn Your Secrets, which is more accurate if not as colorful.)

Although the juicy tidbits about the effectiveness of modern advertising and marketing campaigns were quite intriguing, I was mostly interested in the underlying computing aspects, but the article was rather limited in its discussion of those areas. Perhaps I was attracted by the sweet words:

“It’s like an arms race to hire statisticians nowadays,” said Andreas Weigend, the former chief scientist at Amazon.com. “Mathematicians are suddenly sexy.”

The basic idea, of course, is to start with simply massive amounts of data:

Whenever possible, Target assigns each shopper a unique code — known internally as the Guest ID number — that keeps tabs on everything they buy. “If you use a credit card or a coupon, or fill out a survey, or mail in a refund, or call the customer help line, or open an e-mail we’ve sent you or visit our Web site, we’ll record it and link it to your Guest ID,” Pole said. “We want to know everything we can.”

This sort of data can be collected by the retailer itself, but then it extends that data with other related data it acquires externally:

Target can buy data about your ethnicity, job history, the magazines you read, if you’ve ever declared bankruptcy or got divorced, the year you bought (or lost) your house, where you went to college, what kinds of topics you talk about online, whether you prefer certain brands of coffee, paper towels, cereal or applesauce, your political leanings, reading habits, charitable giving and the number of cars you own.

Once you have all that data, however, the trick is to figure out how to use it successfully. Since essentially all retailers have access to similar data, the primary differentiator is how effectively they can figure out how to locate patterns in the data and successfully deduce what they mean.

In Target's case, one technique is to identify correlations, which they can do in a broadly statistical manner, similar to the "signals" that search engines use to deduce your intent from your actions:

Target has a baby-shower registry, and Pole started there, observing how shopping habits changed as a woman approached her due date, which women on the registry had willingly disclosed. He ran test after test, analyzing the data, and before long some useful patterns emerged. Lotions, for example. Lots of people buy lotion, but one of Pole’s colleagues noticed that women on the baby registry were buying larger quantities of unscented lotion around the beginning of their second trimester. Another analyst noted that sometime in the first 20 weeks, pregnant women loaded up on supplements like calcium, magnesium and zinc. Many shoppers purchase soap and cotton balls, but when someone suddenly starts buying lots of scent-free soap and extra-big bags of cotton balls, in addition to hand sanitizers and washcloths, it signals they could be getting close to their delivery date.

As Pole’s computers crawled through the data, he was able to identify about 25 products that, when analyzed together, allowed him to assign each shopper a “pregnancy prediction” score. More important, he could also estimate her due date to within a small window, so Target could send coupons timed to very specific stages of her pregnancy.

These analyses are very sophisticated, and quite successful at separating false patterns from true ones:

I stopped at a Target to pick up some deodorant, then also bought some T-shirts and a fancy hair gel. On a whim, I threw in some pacifiers, to see how the computers would react. Besides, our baby is now 9 months old. You can’t have too many pacifiers.

When I paid, I didn’t receive any sudden deals on diapers or formula, to my slight disappointment. It made sense, though: I was shopping in a city I never previously visited, at 9:45 p.m. on a weeknight, buying a random assortment of items. I was using a corporate credit card, and besides the pacifiers, hadn’t purchased any of the things that a parent needs. It was clear to Target’s computers that I was on a business trip. Pole’s prediction calculator took one look at me, ran the numbers and decided to bide its time.

But as many people, including the marketing departments at Target, realized, this sort of analysis can get rather disturbing:

Pole applied his program to every regular female shopper in Target’s national database and soon had a list of tens of thousands of women who were most likely pregnant.

...

At which point someone asked an important question: How are women going to react when they figure out how much Target knows?

Indeed, that is a very important question, and it's not clear how well Target is dealing with it. The article describes one attempt, which involved camouflaging their results to try to fool their customers:

“With the pregnancy products, though, we learned that some women react badly,” the executive said. “Then we started mixing in all these ads for things we knew pregnant women would never buy, so the baby ads looked random. We’d put an ad for a lawn mower next to diapers. We’d put a coupon for wineglasses next to infant clothes. That way, it looked like all the products were chosen by chance.

“And we found out that as long as a pregnant woman thinks she hasn’t been spied on, she’ll use the coupons. She just assumes that everyone else on her block got the same mailer for diapers and cribs. As long as we don’t spook her, it works.”

This "fool your own customers" technique is a poor one, and hopefully the company quickly learns that this is the wrong direction to be heading, and instead moves in a direction of greater transparency, greater honesty, and learns to trust its customers and work with them, rather than manipulating them.

Unlikely, I suppose, but we can hope!

It's not just a game ...

... it's the tragically-young death of Adam Adamowicz, a brilliant artist who found his niche creating concept art for role playing games.

Mr. Adamowicz worked with a fellow concept artist, Ray Lederer, on Skyrim, but came up with the look and feel of the game’s marquee monster, fearsome dragons that would intimidate Smaug, the venerable wyrm from “The Hobbit.” Skyrim is the first of the Elder Scrolls series to let players battle them.

In a video interview at vg247.com, Adamowicz and some of his colleagues talk about what it is that a concept artist does for a video game:

“I love Lord of the Rings,” said Adamowicz. “It’s gorgeous. And so how do you beat that? That’s kind of what it came down to. How do you do something really cool in this genre, and have it be original and not ape all of these things?”

In order to find outside inspiration, Adamowicz and Lederer looked to works by Joseph Campbell, and ancient Japanese tradition among others and found a way to put their “own spin on it.”

...

In order to get things moving, Todd Howard provided the team with a general vision of how Skyrim should appear, with its Viking overtones, and once the team had created enough concept art, everyone would sit down and sort through it.

“It was completely blue sky,” said Adamowicz. “Todd said, ‘Sit down and draw a bunch of cool, weird [stuff], and we’ll look at it and decide what’s worthwhile and what’s really stupid.’ We want bad-ass Vikings versus Conan, classic Frank Frazetta, and it’s going to be set in Skyrim, and this is a place that’s going to be a lot more brutal and gritty: draw a bunch of stuff."

In another interview, Adamowicz described the role that he played in the early work on Fallout 3:

Establishing the big picture for the Fallout universe as a pictorial diary, was my first task. Myself and the rest of the team poured over the lore, related our experiences playing the original, and researched everything 50’s we felt enhanced the drama, black comedy, and rich vintage sci fi that make this a truly unique game. At the end of these jams, as I liked to think of our discussions and debates, I did my best to put on paper what we had reached as a consensus.

This wonderful eulogy over on the Awesome Robo! site has some great examples of his art.

And there's more of his Skyrim art in this great article on the Bethesda site, focusing specifically on his critical contributions to the dragons of Skyrim:

The early task of conceptualizing dragons fell to Adamowicz, who was faced with sketching a new take on a classic fantasy beast that could also function as a believable creature in the world of Tamriel. “It was mostly in the treatment of the face and the scales,” he explained. “I based it more on a heron, the chest-plates [being] kind of like a ship’s prow, so that it looked like it was aerodynamic, and kind of like a fighter jet – a little more dangerous.”

A heron, a ship's prow, and a fighter jet! Combine all that in the artist's imagination, and what results is spectacular.

If you want to see how the finished product turned out, have a look!.

Thank you Adam, for all that beautiful and creative work.

Perforce 2012.1 enters Beta testing

The latest release of the Perforce server and tools, Release 2012.1, has now entered public beta testing.

This is the third major release that I've contributed to at Perforce, and I'm very excited about it.

If you've got a medium-to-large sized Perforce installation (say, 100+ users), you'll find a lot to attract your interest in this release. We've put tremendous effort into dealing with the scalability, performance, availability, and reliability issues that matter to large sites, and I think that this effort is really starting to pay off.

Have a look, read the release notes, download it and give it a try, and let us know what you think!

A thousand words

Stare at this picture for just a second or two, and the location of the Hayward Fault will just jump out at you!

Mountain Lion speculations

No, not the animal! John Gruber has a teaser article on his blog with some speculation about the next release of Mac OS X, "Mountain Lion".

Now that Apple has become the top tech company, it's worth spending time keeping track of what they're thinking and where they're going, and Gruber has always been one of the top Apple-watchers.

The recurring theme: Apple is fighting against cruft — inconsistencies and oddities that have accumulated over the years, which made sense at one point but no longer — like managing to-dos in iCal (because CalDAV was being used to sync them to a server) or notes in Mail (because IMAP was the syncing back-end). The changes and additions in Mountain Lion are in a consistent vein: making things simpler and more obvious, closer to how things should be rather than simply how they always have been.

And while you're thinking and musing about all things Apple, you might want to have a look at Danny O'Brien's recent article about Apple's design philosophy, Bret Victor's presentation, and how design philosophies are playing a much larger part in areas of computer software that used to be all-about-technology, nothing-about-design, such as operating systems, file systems, networking, etc.

Twenty years ago, it was about getting it done at all.

Now it's about getting it done elegantly and in a fashion that anyone can use.

Tall Tales from the Ozarks

I'm really enjoying Donald Harington's peculiar, but delightful, book: The Architecture of the Arkansas Ozarks.

The book tells the story of Jacob Ingledew, a settler in the Arkansas Ozarks in the 1850's (I think). Jacob, his brother Noah, and a whole collection of other colorful characters, have adventure after adventure, all the while commenting on their lives in humorous and entertaining ways.

Somehow, I had never heard of Harington, nor of this series of books. I stumbled across them on Amazon, bought the book for the Kindle, and am looking forward to reading more of Harington's work.

Harington passed away in 2009, which is a shame (by the way, somebody should update his personal website, since it doesn't seem to acknowledge this fact). This observation from his obituary seems quite accurate to me:

Mr. Harington moved elusively among fictional categories, making him hard to place and hard to sell, which is one reason he taught history at the University of Arkansas from 1986 until 2008. His work seemed regional and in some respects traditional, but his narratives unfolded in a magical-realist haze with metafictional twists and turns and excursions into nonfiction territory.

My observation about The Architecture of the Arkansas Ozarks is that it seems like fiction, like history, and like several other things all at once (architectural criticism, social commentary, etc.). Apparently Harington himself did the drawings that head each chapter, and which come through quite nicely in the Kindle edition, actually.

If you're looking for a new author, and haven't ever tried Donald Harington, I recommend him highly. Give one of his books a try, and let me know what you think!

Haswell TSX

One of the significant research areas of the last decade has been "transactional memory", which in concept involves the use of DBMS transaction paradigms (the "ACID" mnemonic: Atomic Consistent Isolated and Durable actions) in the microprocessor's memory model.

Slowly, that work has been emerging from the lab and into viability.

There's a lot of interest in Intel's recently announced TSX extensions for their new Haswell processor architecture, described in Transactional Synchronization in Haswell.

And here are two additional perspectives:

• David Kanter covers the topic in detail over at Real World Technologies: Analysis of Haswell's Transactional Memory
• And Jeremy Manson has a shorter but very informative essay on his blog: Transactional Hardware on x86

This work is going to take a long time to evolve: it's complicated and not easy to use.

But as Moore's Law continues to grind to a halt, and multi-code programming continues to expand, this sort of technique is the way of the future.

Skyrim 1.4

Our PS3 is now freshly updated with the 94 megabyte Skyrim 1.4 patch. It looks like (warning, mild spoilers if you click the link) it contains a lot of fine fixes!

Now I just have to find time to (a) clear Morvath's Lair with the team that the Jarl of Morthal has assembled, (b) clear the Brood Cavern as requested by the Companions, (c) go visit Haemar's Shame with Barbas, and (d) head back to Riverwood for my long-overdue meeting with Delphine.

Hmmm... why am I wasting time blogging? I need to be adventuring!

Why software is different from hardware

I enjoyed reading through this programmer's diary discussing the work that Art Cabral is doing to try to update an old application so that it runs on more modern systems.

Now, Seahaven Towers is an amazing piece of software; I remember running it back in 1991 or so, and being amazed that, year after year, the program "just worked" on each new Mac and each new version of Mac OS that I tried it on.

And Cabral's diary contains some great information about how he got the program to that level of quality, describing his attention to detail in areas such as string handling, graphics, and character sets.

But it's a fine example of why software can't just be put in a box and declared 'done'. As Cabral observes:

A lot of 3rd party tools were used to create Seahaven Towers 2.0. Robust, stable tools they were, certain to be around for a very long time. Let's see - CodeWarrior for Windows (gone), CodeWarrior for Mac (gone), Adobe GoLive (gone). There were others that disappeared as well. Now Apple takes away Rosetta for no technical reason I've been able to fathom. It's been said (and I can't recall the attribution) that hardware architectures last a maximum of 3 years and software architectures last around 30 years. Apparently that last part is no longer true.

Well, 30 years is a long time. Even 20 years is a long time. I remember using CodeWarrior myself, in 1996, and it was indeed a nice programming tool.

Operating Systems change, compilers change, APIs change, frameworks change, and there's no standing still on the treadmill of software progress. If you aren't routinely attending to your program(s), building them and running their tests and keeping up with changes in their environment and staying alert for upcoming shifts in the underlying foundations upon which they are built, you'll end up with a program that no longer works, and no idea about how much work it's going to be to get it to run again.

I don't know a way to eliminate pain, but I do believe that Continuous Integration systems can make this pain substantially less. By automating robots to do this boring testing for you, you can spend less time discovering and cataloging these sorts of things, and more time planning how to deal with them.

At my day job, I work on the maintenance and upkeep of a 17-year-old piece of software, and I'm also involved with a 15-year-old open source project. In both cases, there are substantial bodies of test suites that are nearly as old as the product itself, and ongoing investments in tools and laboratories of robotic computers slaving away, verifying over and over again that "things still work" (yes, we have to check this, all the time!)

There's great value in working on old software: it's survived the test of time, it's demonstrated enduring value, it's acquired a lasting community of adherents. We know the value of such software, and so we work hard to keep it alive.

Best of luck to the Longwood Wizards Guild!

There is no 16 clue Sudoku

Nature magazine is carrying a story reporting on the recent work of Gary McGuire of University College Dublin. McGuire's team have been studying the question of the minimal number of clues that must be present in a valid Sudoku puzzle, and recently announced their findings.

What's particularly interesting about their technique is that it combines Mathematics and Computer Science, using techniques from both disciplines:

A potential way to demonstrate that could be to check all possible completed grids for every 16-clue puzzle, but that would take too much computing time. So McGuire simplified the problem by designing a 'hitting-set algorithm'. The idea behind this was to search for what he calls unavoidable sets, or arrangements of numbers within the completed puzzle that are interchangeable and so could result in multiple solutions. To prevent the unavoidable sets from causing multiple solutions, the clues must overlap, or 'hit', the unavoidable sets. Once the unavoidable sets are found, it is a much smaller—although still non-trivial—computing task to show that no 16-clue puzzle can hit them all.

Having spent two years testing the algorithm, McGuire and his team used about 7 million CPU hours at the Irish Centre for High-End Computing in Dublin, searching through possible grids with the hitting-set algorithm. “The only realistic way to do it was the brute force approach,” says Gordon Royle, a mathematician at the University of Western Australian in Perth who had been working on the problem of counting 17 clue puzzles using different algorithms. “It’s a challenging problem that inspires people to push computing and mathematical techniques to the limit. It’s like climbing the highest mountain.”

I've been reading through the paper and enjoying it, even if parts of it are beyond my skill (hey, Sudoku plus Mathematics plus Computer Science -- this is nerd heaven in my view!).

The authors note that their "hitting set" approach could have a number of applications beyond this Sudoku question:

This new algorithm has many other potential applications than just sudoku. To begin with, it is applicable to any instance of the hitting set problem, and such situations frequently occur in Bioinformatics (e.g., gene expression analysis), Computer Networks and Software Testing [11]. We note that the vertex cover problem from graph theory can be reduced to the hitting set problem, and so can the set cover problem, so both of these are actually equivalent to the hitting set problem. The set cover problem has applications to interference in cellular networks.

In case you find that the paper is a bit much to digest, let me also recommend this wonderful video, produced by Brady Haran, in which James Grime walks us through the solution, explaining the overall technique, and using some nifty illustrations to make it clear.

I wish they had had videos like this when I was studying Maths in school!

Of course, if they had, I might never have switched to Computer Science.

While wandering around reading about all of this, I came across this book: Taking Sudoku Seriously: The Math Behind the World's Most Popular Pencil Puzzle. It looks pretty interesting; I might give it a try (once I finish some of my back-logged books. And the Kindle edition is actually reasonably priced!

Oh, and lastly: thanks Maggie Koerth-Baker for throwing a pointer to this work up on Boing Boing; you are quickly becoming one of my favorite writers!

Speculation on whistle-blowers

The Sunday New York Times carried this interesting opinion piece: A High-Tech War on Leaks.

Much of the discussion recently has been on how modern technology has enabled leaks, as in wikileaks, etc.

But this article focuses on how modern technology is having the opposite effect, by enabling governments to deter and punish leaks:

It used to be that journalists had a sporting chance of protecting their sources. The best and sometimes only way to identify a leaker was to pressure the reporter or news organization that received the leak, but even subpoenas tended to be resisted. Today, advances in surveillance technology allow the government to keep a perpetual eye on those with security clearances, and give prosecutors the ability to punish officials for disclosing secrets without provoking a clash with the press.

The author of the essay wonders whether the outcome of this will be a return to older, more personal methods of reporting:

The solution for reporters, Ms. Dalglish said, is to adopt Mr. Woodward’s methods from the 1970s. “For God’s sake, get off of e-mail,” she said. “Get off of your cellphone. Watch your credit cards. Watch your plane tickets. These guys in the N.S.A. know everything.”

Mr. Corallo, the former Justice Department spokesman, provided corresponding advice to government officials. “Don’t be stupid and use e-mail,” he said. “You have to meet a reporter face to face, hand him an envelope and walk away quickly.”

What the article doesn't discuss, in my opinion, is whether there is any value in having all this secrecy in the first place. Remember all the excitement about Transparency, Open Government, and the Sunlight Initiative four years ago? Well, surprise surprise, things didn't seem to come to pass:

"Some agencies have really embraced the new direction and the new policies," said Sean Moulton, director of federal information policy at OMB Watch, singling out the Environmental Protection Agency as an example. Others, such as the intelligence agencies, seem to be continuing with "business as usual," Moulton said.

Well, fancy that.

What I'm doing at work

I often have trouble explaining just what it is that I do at my day job, so it's great that my colleague Randy DeFauw, who is an excellent writer, took the time recently to explain things in some detail. My team is mid-way through a multi-year project to provide a family of scalability, performance, and availability features that together go under the label: "replication."

Here's Randy's article: The Replication Train is Rolling.

I'm wicked excited about the features we're rolling out this spring, and I'm really looking forward to getting feedback from people who take advantage of them!

Jeff Atwood works to keep it in perspective

Amazingly, it's been 4 months since Steve Jobs died.

Jeff Atwood has been thinking about it a lot, and actually credits Jobs with inspiring a major life change for Jeff.

Jason Kotke picked up on Atwood's revelation, and offers a few thoughts of his own: The lessons of Steve Jobs:

Four is hardly a trend but it is interesting that the death and biography of the greatest businessman of our generation -- someone who was responsible for so many world-changing products and ideas, who shaped our world through sheer force of will & imagination, etc. etc. -- is inspiring some people to turn away from the lifestyle & choices that made Jobs so successful & inspiring in the public sphere and to attempt the path that Jobs did not.

Completely removing yourself from a company you co-founded, especially one that has been as successful and widely-adopted as StackOverflow/StackExchange, is an enormous decision and a very uncommon one; Atwood is a very interesting guy, and I'll look forward to learning what he does next.

I'm lucky, myself: I found my work-life balance early, when I was young; perhaps it would be more accurate to note that she found me! I've never felt the urge to change the world, like Steve Jobs felt every second of his life, though I can't deny the thrill of knowing that software I've written is in the hands of millions.

I was thinking about all of this as I read Leslie Chang's fascinating article in The New Yorker about reading habits in China: Working Titles. Chang quotes the famous author Lao Kang:

His wife's sister and her husband have lived and worked in the United States for years. "They don't focus on money," he said. "All they care about is living a pleasant life. Every weekend, they drive somewhere on an outing."

I suggested that he could also spend weekends this way.

"Yes," he said. "But every time I think about doing it I immediately think I should be doing something more meaningful. Like working."

I'm reminded of a (apocryphal?) story that was told to us freshmen at the University of Chicago about Robert Maynard Hutchins, the chancellor under whose leadership the university decided to resign from the Big 10 athletic conference, tear down the football stadium, and build the Joseph Regenstein Library in its place. When asked why he felt a library was a better use of the space than a football stadium, Hutchins is said to have responded:

Whenever I feel the urge to exercise, I sit down and read a book until it passes.

I'm off now; time to go finish the weekend house-cleaning :)

Dungeons and Dragons retrospective

Although it could use some copy-editing, this series of articles on the original Dungeons & Dragons history is a quick and interesting read:

1. The Ghosts of D&D: Past
2. The State of D&D: Present
3. The State of Dungeons & Dragons: Future
4. 4 Hours with Ryan Dancey

History is written by the victors, as they say, and so the articles have an unavoidable slant and perspective, but there's lots of interesting material about: the evolution of D&D; about the trials and errors; about how the authors, the players, and the whole community grew and learned to work together on D&D; about experiments in open licensing and alternate business models; and about how the pressures of commercialism forced decisions and approaches that were appealing to some and appalling to others.

One controversial aspect was the simplification or streamlining of the rules:

Collins told The Escapist back in 2010 that the changes he and Heinsoo implemented in D&D were meant to catch the game up with the way that people played modern games. Collins believed players have a short attention span, and were, perhaps, "less likely [to be] interested in reading the rules of the game before playing." "I'm not just talking about younger players now, but anybody. We've been working to adapt to that, the changing expectations of the new gamer."

and the divisions that arose in the community during these experiments:

The Old School Renaissance is the name given to what can only be called a movement among gamers to return to an older style of play. "I think Gary Gygax's death [in 2008] had a profound impact on a lot of the old schoolers. Many of them were grudgingly going along with modern game design conventions simply because they had no other choice," said Erik Mona.

Gaming systems are interesting because they evolve. Iterative refinements introduce new behaviors while altering old ones, and the results can take some time to comprehend.

In this way, it is much like computer software!

Six interesting papers

Here's some brief observations about some papers. The topics are broadly related, but the actual papers aren't really related; I just happened to be reading them around the same time. The papers in question are:

1. Optimistic Replication Algorithms, by Yasushi Saito. This paper is more than a decade old, but I just came across it recently. It's a survey of overall replication strategies, with a categorization of the various approaches to help compare and contrast them.

   Optimistic replication algorithms allow data presented to users to be stale but in a controlled way. A key feature that separates optimistic replication algorithms from pessimistic counterparts is the way object updates are handled: whereas pessimistic algorithms update all the replicas at once and possibly block read requests during the update application, optimistic algorithms propagate updates in background and allow any replica to be read directly most of the time.

   According to the paper's taxonomy, the implementation that I've been working on at my day job is a single-master log-transfer system with eventual consistency.
2. Btrfs: The Swiss Army Knife of Storage by Josef Bacik. This is a filesystems paper:

   Btrfs is a new file system for Linux that has been under development for four years now and is based on Ohad Rodeh’s copy-on-write B-tree . Its aim is to bring more efficient storage management and better data integrity features to Linux . It has been designed to offer advanced features such as built-in RAID support, snapshotting, compression, and encryption . Btrfs also checksums all metadata and will checksum data with the option to turn off data checksumming .

   This is a great example of the sort of paper that I often call a "principles and techniques" paper: rather than diving into low-level details, the paper describes the high-level principles that the btrfs implementation is using to build a production quality filesystem. It's extremely readable while also being very informative. One of the major differentiators of btrfs from other recent filesystems has to do with how they ensure consistency. For the past 10-20 years, the primary technique has been journaling, but btrfs has a new approach:

   Traditional Linux file systems have used journals to ensure metadata consistency after crashes or power failures . In the case of ext this means all metadata is written twice, once to the journal and then to its final destination . In the case of XFS this usually means that a small record of what has changed is written to the journal, and eventually the changed block is written to disk . If the machine crashes or experiences a power failure, these journals have to be read on mount and re-run onto the file system to make sure nothing was lost . With Btrfs everything is copied on write . That means whenever we modify a block, we allocate a new location on disk for it, make our modification, write it to the new location, and then free the old location . You either get the change or you don’t, so you don’t have to log the change or replay anything the next time you mount the file system after a failure—the file system will always be consistent .

3. RemusDB: Transparent High Availability for Database Systems by Minhas, Rajagopalan, Cully, Aboulnaga, Salem, and Warfield. This paper presents a very interesting approach to providing a high-availability database, using the technology of modern cloud-computing-style server virtualization:

   Two servers are used to provide HA for a DBMS. One server hosts the active VM, which handles all client requests during normal operation. As the active VM runs, its entire state including memory, disk, and active network connections are continuously checkpointed to a standby VM on a second physical server.

   ...

   Remus’s checkpoints capture the entire state of the active VM, which includes disk, memory, CPU, and network device state. Thus, this captures both the state of the database and the internal execution state of the DBMS, e.g., the contents of the buffer pool, lock tables, and client connection state. After failover, the DBMS in the standby VM begins execution with a completely warmed up buffer pool, picking up exactly where the active VM was as of the most recent checkpoint, with all session state, TCP state, and transaction state intact. This fast failover to a warm backup and no loss of client connections is an important advantage of our approach.

4. Fast Crash Recovery in RAMCloud, by Ongaro, Rumble, Stutsman, Ousterhout, and Rosenblum. This paper is also concerned with high availability and crash recovery, but this team takes a different approach:

   RAMCloud keeps only a single copy of data in DRAM; redundant copies are kept on disk or flash, which is both cheaper and more durable than DRAM. However, this means that a server crash will leave some of the system’s data unavailable until it can be reconstructed from secondary storage.

   RAMCloud’s solution to the availability problem is fast crash recovery: the system reconstructs the entire contents of a lost server’s memory (64 GB or more) from disk and resumes full service in 1-2 seconds. We believe this is fast enough to be considered “continuous availability” for most applications.

   In order to accomplish their recovery-time objective, they have a massively-parallel recovery algorithm:

   Each server scatters its backup data across all of the other servers, allowing thousands of disks to participate in recovery. Hundreds of recovery masters work together to avoid network and CPU bottlenecks while recovering data. RAMCloud uses both data parallelism and pipelining to speed up recovery.

5. Modular Data Storage with Anvil, by Mammarella, Hovsepian, and Kohler. This paper discusses an experimental database system which is designed to allow researchers and system builders to experiment with various storage systems by showing how a database storage system can be constructed in a component-based fashion, based on a small set of carefully-designed storage system modules:

   Two basic goals guided the design of Anvil. First, we want Anvil modules to be fine-grained and easy to write. Implementing behaviors optimized for specific workloads should be a matter of rearranging existing modules (or possibly writing new ones). Second, we want to use storage media effectively by minimizing seeks, instead aiming for large contiguous accesses. Anvil achieves these goals by explicitly separating read-only and write-mostly components, using stacked data storage modules to combine them into read/write stores. Although the Anvil design accommodates monolithic read/write stores, separating these functions makes the individual parts easier to write and easier to extend through module layering.

   The basic Anvil component is an object called a dTable; the paper shows a number of details about dTables and also gives some good examples of how they can be composed, layered, and extended.
6. Interval Tree Clocks: A Logical Clock for Dynamic Systems, by Almeida, Baquero, and Fonte. This paper discusses the nearly 40 year old problem of trying to reason about the ordering of events in distributed systems.

   This paper addresses causality tracking in dynamic settings and introduces Interval Tree Clocks (ITC), a novel causality tracking mechanism that generalizes both Version Vectors and Vector Clocks. It does not require global ids but is able to create, retire and reuse them autonomously, with no need for global coordination; any entity can fork a new one and the number of participants can be reduced by joining arbitrary pairs of entities; stamps tend to grow or shrink adapting to the dynamic nature of the system. Contrary to some previous approaches, ITC is suitable for practical uses, as the space requirement scales well with the number of entities and grows modestly over time.

   The paper is very carefully and clearly written, and I enjoyed this paper the most out of the whole set. The best thing about the paper is its use of examples and illustrations: the examples are carefully chosen to be complex enough to capture the power of their approach, while still being small enough to fit in a terse paper.

   But more importantly, the paper uses a simply brilliant graphical notation to allow you to visualize the tree-manipulation techniques. The essence of the ITC approach is to use tree data structures to encode event histories, but standard notation for describing the technique is very hard to follow. The diagrammatic approach that the paper uses is beautiful and very elegantly conveys the essence of the technique.

   By the way, it appears that the authors have subsequently contributed a running implementation of their approach in multiple languages as open source. Very nice!

Who knows if any of these papers are of interest to you. I found them all interesting, well-written, and worth the time. If the subject matter of any of them appeals to you, I think you won't be disappointed by studying them.

Chrome is dropping CRL checking

Google's Adam Langley explains why, and this Ars Technica article adds some more context.

As Langley says:

So soft-fail revocation checks are like a seat-belt that snaps when you crash. Even though it works 99% of the time, it's worthless because it only works when you don't need it.

While the benefits of online revocation checking are hard to find, the costs are clear: online revocation checks are slow and compromise privacy. The median time for a successful OCSP check is ~300ms and the mean is nearly a second. This delays page loading and discourages sites from using HTTPS. They are also a privacy concern because the CA learns the IP address of users and which sites they're visiting.

Seems like pretty good reasoning to me.

Needing/Getting

I absolutely cannot stop watching OK Go's newest video: Needing/Getting.

Is it music? Is it art? Is it advertising? Is it promotional marketing (for the band, for the car)? Why, yes, it is! It is all those things.

Most importantly, though, it's a great video!

OK Go set up over 1000 instruments over two miles of desert outside Los Angeles. A Chevy Sonic was outfitted with retractable pneumatic arms designed to play the instruments, and the band recorded this version of Needing/Getting, singing as they played the instrument array with the car. The video took 4 months of preparation and 4 days of shooting and recording. There are no ringers or stand-ins; Damian took stunt driving lessons. Each piano had the lowest octaves tuned to the same note so that they'd play the right note no matter where they were struck. For more information and behind-the-scenes footage, see http://www.LetsDoThis.com and http://www.okgo.net.

There were a number of automobile commercials during the Super Bowl; I loved some (the OK Go commercial, the Fiat Abarth, the Audi vampires) and hated others (post-apocalyptic Chevy pickup trucks, Chrysler's "halftime in America").

What ones did you like, and why?

Winter weather

It appears that winter never came to the U.S.A. this year, but now we know where winter went instead: Europe.

Julian Sanchez reacts to Cory Doctorow's speech

(If you haven't already read or watched or listened to Cory Doctorow's speech yet, well, what are you waiting for?)

Julian Sanchez is a very interesting author. He works for the Cato Institute and writes for Reason magazine. I don't always agree with everything he says but I find his essays to be well-considered, well-written, and thought-provoking.

Sanchez has written an excellent follow-up article to Doctorow's speech: On the Enforcement Fantasy.

What is "the enforcement fantasy", according to Sanchez?

The misapprehension that technology is going to stay still long enough for traditional, targeted law enforcement approaches to effectively limit the scope and scale of copying.

Sanchez's main point, I believe, is to support Doctorow's observation that regulation must be rooted in the practical and the realistic, and to try to re-direct the discussion toward effective regulation of desired behavior in a context that comprehends the onward march of technology:

We have a legal structure for incentivizing creativity that makes copying and public performance the key points of regulatory intervention. There isn’t some deep moral reason that it’s these points and not others. There are lots of other ways to enjoy creative works without paying the creator, after all

...

We decided to regulate copying instead, because copying was a lot easier and cheaper to regulate when we wrote the copyright statutes.

...

But the thing we decided to regulate because it was rare and expensive is now as cheap and ubiquitous as all the other stuff we didn’t regulate because it was cheap and ubiquitous. The good news is, most people are still glad to pay for the content they really like, if it’s provided in a convenient form and at a reasonable price, even when they can (or did!) easily copy it free.

I'm pleased to see people continuing to study and discuss the issues, and trying to advance the debate in useful ways.

Fabs and their toys

Here's a fun little story in Wired about the friendly competition between two Intel chip fabrication plants regarding which facility has "the world's largest crane" at their construction site.

The Lampson Transi-Lift is operating at a construction site in Oregon, while the Sarens SGC-120 is operating at a construction site in Arizona.

I've heard it said that chip fabrication plans (and Intel's fabs in particular) are the most sophisticated buildings on earth, so it's no surprise that it takes the most powerful cranes to build them.

Of course, they said "land-based", so I guess the Left Coast Lifter is in its own category.

The S-1 is out

No, I didn't read all 200+ pages, and I don't intend to.

But the LETTER FROM MARK ZUCKERBERG is interesting:

Personal relationships are the fundamental unit of our society. Relationships are how we discover new ideas, understand our world and ultimately derive long-term happiness.

At Facebook, we build tools to help people connect with the people they want and share what they want, and by doing this we are extending people’s capacity to build and maintain relationships.

People sharing more — even if just with their close friends or families — creates a more open culture and leads to a better understanding of the lives and perspectives of others. We believe that this creates a greater number of stronger relationships between people, and that it helps people get exposed to a greater number of diverse perspectives.

By helping people form these connections, we hope to rewire the way people spread and consume information. We think the world’s information infrastructure should resemble the social graph — a network built from the bottom up or peer-to-peer, rather than the monolithic, top-down structure that has existed to date.

I'm still not sure I buy into that last paragraph, but, as I said, I think it's an interesting letter, and they certainly have an interesting point of view.

Beautiful Day at the Dog Park

My daughter sent me this beautiful video of the dogs having fun at the dog park.

The camera was apparently attached directly to the dog's harness.

If you're into dogs, you'll like the movie :)