Survey of IP issues in 3D printing technology

Here's a great video to watch: http://www.youtube.com/watch?v=EMhNapObKQk. It's only 30 seconds long, so have a go. ... OK, you're back?

Now go have a look at this detailed writeup of the story behind that video, and the hornet's nest of who-invented-what and how-do-you-control-an-idea debates that have arisen over the past few days.

I know very little about 3D printers; I've never seen one in person, just read about them. I found this background paper by Michael Weinberg to be very well-written and interesting, though:
It Will Be Awesome If They Don't Screw It Up: 3D Printing, Intellectual Property, and the Fight Over the Next Great Disruptive Technology

Cory Doctorow is also doing a great job of covering this story, over at the BoingBoing blog.

NYT article on Dennis Montgomery's software career

Today's New York Times features a front-page investigative article titled Hiding Details of Dubious Deal, U.S. Invokes National Security. The article, together with an accompanying interactive timeline, provide evidence and make the assertion that:

Mr. Montgomery and his associates received more than $20 million in government contracts by claiming that software he had developed could help stop Al Qaeda's next attack on the United States. But the technology appears to have been a hoax, and a series of government agencies, including the Central Intelligence Agency and the Air Force, repeatedly missed the warning signs, the records and interviews show.

During the heyday of the anti-terrorist hysteria, Montgomery realized that he could capitalize on the activity:

the company won the attention of intelligence officials in Washington. It did so with a remarkable claim: Mr. Montgomery had found coded messages hidden in broadcasts by Al Jazeera, and his technology would decipher them to identify specific threats.

I remember the media reporting on such "messages", and it indeed had just enough plausibility that I can see how people were willing to believe it. There was, according to the article, just one problem: there were no messages; there was no such technology; Montgomery had simply made it all up.

Much more significant than the wasted money, which in truth is minute in the long litany of Homeland Security waste over the last decade, is the truly shocking realization that, based just on this, foolish, even tragic actions were almost taken:

In December 2003, Mr. Montgomery reported alarming news: hidden in the crawl bars broadcast by Al Jazeera, someone had planted information about specific American-bound flights from Britain, France and Mexico that were hijacking targets.

C.I.A. officials rushed the information to Mr. Bush, who ordered those flights to be turned around or grounded before they could enter American airspace.

Senior administration officials even talked about shooting down planes identified as targets because they feared that supposed hijackers would use the planes to attack the United States.

You should read the entire article: it's chilling and infuriating.

UPDATE As several people have pointed out, you should also read the excellent article by Aram Roston, written 18 months ago: The Man Who Conned The Pentagon, published in (yes) Playboy Magazine. Separately, Mike Masnick points out that not only did the government spend millions of taxpayer dollars on this non-existent software, they also allowed Montgomery to patent it!

Sadly, this last decade has been one tragic story after another along these lines. The gigantic money trough that is the Homeland Security Administration has resulted in all too many fraudsters and con-men showing up to siphon off what they could. Just last month we learned that what appeared to be a respectable security consulting company was in fact headed by a CEO who faked his evidence and manufactured claims that he knew would excite interest and therefore lucrative contracts. Wired's Threat Level blog, together with Ars Technica, another well-respected technology site, did a wonderful job of reporting on the scandal in a pair of articles:

• Spy Games: Inside the Convoluted Plot to Bring Down WikiLeaks


• How one man tracked down Anonymous—and paid a heavy price

Of course, charlatans are nothing new in the security field -- there's a reason that Bruce Schneier never seems to lack for material to fill the "Doghouse" section of his monthly security newsletter.

But it's certainly dispiriting to have it once again confirmed that even the people who really truly ought to know better, such as the CIA and the Air Force, fall victim to these scams again and again. Here's a big "thank you" to the New York Times, to Ars Technica, to Wired, to people like Brian Krebs and Bruce Schneier, and to all those hard-working and dedicated journalists who refuse to be bluffed by the schemers and fakers and work to educate us about what is real and what is not.

Reputation comes slowly at StackOverflow

I've been a user of StackOverflow for 18 months now; it's an interesting and useful site, and I enjoy participating.

I don't put a lot of time into the site, but I do visit almost every day, and generally interact in one way or another.

But after 18 months, my reputation is only slightly more than 500.

And yet, though StackOverflow as a institution is only a few years old, there are users with hundreds of thousands of reputation!

According to the privileges list, I have about 60% of the privileges, so I guess I'm making progress.

I'm not sure why it matters; I'm just sort of noticing it.

But, anytime there's a measurement, and I'm one of the people being measured, I'm always intrigued...

Progress in logging systems, redux

As you recall, late last year I was reading a paper on transactional logging system implementations by a team from Carnegie Mellon.

And last month I was digging my way through Google's paper on their Megastore system.

Well, this month I've been continuing to work my way through the papers from this winter's Conference on Innovative Data Systems Research (CIDR), and this year the Best Paper award went to another logging systems implementation paper: Hyder - A Transactional Record Manager for Shared Flash, from a team at Microsoft Research, headed by Philip Bernstein, who literally wrote the book on transaction logging systems many years ago (I still have my copy!).

The three projects all look at similar problems, but all are pointed in different directions:

• Aether is concerned with single-system multi-core parallelism, and proposes the use of sophisticated high-concurrency non-blocking data structures and algorithms.


• Megastore is concerned with offering traditional transaction-processing ACID guarantees on top of a massively-replicated infrastructure, and proposes a Paxos algorithm using timestamping for implementing a single logical log across the many-node systems.


• Hyder, like Megastore is concerned with multi-system scale-out, but proposes the use of multi-version database concurrency control and a melding protocol to merge the individual system transaction histories into a totally ordered outcome.

The melding protocol proposed by Hyder is the heart of the work, and is described in great detail. Here's the overview of the idea, from the abstract:

Each transaction executes on a snapshot, logs its updates in one record, and broadcasts the log record to all servers. Each server rolls forward the log against its locally-cached partial-copy of the last committed state, using optimistic concurrency control to determine whether each transaction commits.

Another very interesting aspect of the Hyder work is the tradeoff between traditional BTree architecture and replication protocols, and in particular that there can be significant benefit in minimizing log record size:

An updated tree is logged in a transaction's intention. For good performance, it is important to minimize its size. For this reason, binary trees are a good choice. A binary tree over a billion keys has depth 30. A similar number of keys can be indexed by a four-layer B-tree with 200-key pages. But an update of that Btree creates a new version of four pages comprising the root-to-leaf path, which consumes much more space than a 30-node path.

The paper is somewhat indefinite with regards to this, observing that: "A comparative evaluation of these tradeoffs would be a worthwhile investigation." Sort of a details-are-left-as-an-exercise observation, unfortunately. However, this is active research and I'm pleased that they are sharing their thoughts and ideas; I'd always rather read about the road not taken, and why, then get everything all nicely wrapped up in a package, without the background information that helps understand how they arrived at these conclusions and what other ideas they considered.

All three papers are fascinating and worth reading, and I'm certainly enjoying this renaissance in transactional processing implementation of late. All of a sudden, the only thing I'm short of is time to read all these ideas!

NYT article on "black-hat" SEO activity

The lead article in the Business section of today's New York Times is titled The Dirty Little Secrets of Search. It discusses some of the various techniques that web site operators use to try to influence the algorithms that Google's search engine uses to rank results.

Sadly, the article's headline promises much more than the story actually delivers; I thought the article was interesting, but ultimately frustrating.

Although the writer is able to secure interviews with Matt Cutts of Google, and with a mysterious "Mark Stevens" of an unnamed company (neither the company's name, nor "Mr. Stevens"'s name is revealed in the article, though it's hard to see why), the article ends up mostly teasing, and exposing very little about this seamy under-belly of the web search world.

We never find out exactly which company was gaming the Google results, nor exactly how.

We never find out whether Penney was aware of that company's techniques, or how they selected that company, or much of anything about Penney's relationship with the unnamed vendor that they used.

We never find out exactly what Google did about the situation, other than that "manual action" was taken.

The only concrete and specific piece of evidence that the article seems able to unearth is a bit about a web site in Switzerland which posted a strange and completely unrelated link to the Penney's web site, apparently via a company called TNX.net, but, as the article says: "Efforts to reach TNX itself last week via e-mail were not successful."

Clearly there is a thick curtain here, and the Times apparently decided that they needed to publish what they had, now, even though they had very little to actually write about, because the story, such as it was, was nearly over: "On Feb. 1, the average Penney position for 59 search terms was 1.3. On Feb. 8, when the algorithm was changing, it was 4. By Feb. 10, it was 52." The Times writer ultimately fails to provoke either Google or Penney to talk about the details of what happened; Google's Cutts flat-out refuses to say: "Mr. Cutts said he did not plan to write about the situation ... because Google's goal is to preserve the integrity of results, not to embarrass people." So, instead, the article wanders around, venturing into what the author himself notes is just "another hypothesis, this time for the conspiracy-minded."

This is clearly an important topic, and serious. There is real money at stake, and real questions about legality, and ethics, and transparency. It's frustrating that even as powerful an institution as the New York Times can't break through and bring some real sunlight into these hidden corners.

Code coverage isn't everything. But it's not nothing, either.

Recently I've been spending a lot of time writing tests.

I'm not a fanatic Test First Development developer, though I think there's a lot of value in that practice. I'd say I:

• occasionally write my tests first,


• usually write my tests simultaneously with my code (often with two windows open on the same screen), jumping back-and-forth, adding each new test case as soon as I think of it,


• rarely write my tests afterwards.

I'm comfortable with that distribution; it feels about right to me.

Interestingly, my behavior changes dramatically when I'm fixing a bug, as opposed to working on new feature development. When I embark on a bug fix, I nearly always write the test first; I think the proportion may be as high as 95% of the time. I do this because:

• it's extremely comforting to make a bug fix, and watch the test case flip from "failing" to "passing", while all the other test cases continue to pass,


• but more importantly, I've found, over the years, that writing and refining the test case for the bug is just about the best process for isolating and refining my ideas about what precisely is wrong with the code, and how exactly the code should be fixed.

So, anyway, I've been writing a lot of tests recently, and as part of that effort I've been spending some time studying code coverage reports. I've been using the built-in gcov toolset that is part of the GNU Compiler Collection, and also using the nifty lcov tools that build upon gcov to provide useful and easy-to-read reports and displays.

I take a very pragmatic view when it comes to tests:

• Testing is a tool; writing and running tests is one way to help ensure that you are building great software, which should be the only sort you even try to build.


• Code coverage is a tool for helping you write tests. If you care about writing tests (and you should), then you should care about writing the best tests you can. Code coverage is something that can help you improve your tests.

I don't have any sort of religion about code coverage. I don't think that tests with higher coverage are mandatory; I don't think that there is some magic level of coverage that you must achieve. I think that anybody who is spending any time thinking about code coverage should immediately go read Brian Marick's excellent essay on how to use code coverage appropriately: How To Misuse Code Coverage.

However, I do think that, all things being equal, higher code coverage is better than lower code coverage, to wit:

• If I add a new test case, or suite of cases, and overall code coverage goes up, I am pleased. The test suite is more comprehensive, and therefore more useful.


• If, however, code coverage tells me that I've already got a lot of coverage in this area, then I need to think about other ways to improve my tests.

In my experience, there are often large gaps in test coverage, and there is often a lot of low-hanging fruit: writing a small number of simple cheap-to-run tests can quickly ensure that your tests are covering a much larger portion of your code.

Furthermore, studying your code coverage tests can help you think about new test cases to write. A good coverage tool (like lcov) will show you not just line coverage, but branch coverage, function coverage, and many other ways to think about how your tests are driving your code. Just sitting down and staring at code coverage reports, I always find that ideas for new tests just seem to leap off the screen.

And that's what I'm really looking for when I pull up the code coverage tool: inspiration. Writing tests is hard, but there are always more tests to write, and always ways to make my tests better, so any tool which helps me do that is a tool which will have a prominent place on my shelf.

So, no: code coverage isn't everything. But it's not nothing, either.

No Bryan, there is not a global conspiracy against you

I had a great time this morning; or, at least, about as much fun as a programmer can have.

I was debugging some new code I'd written, in a networked server process which contains a master loop that more-or-less looks something like the following:

... various code to set up variables ...

do {

    ... accept a new connection from a client ...

    ... fork a new process to handle that client ...

} while ( ! done );

The code is massively simplified, but for the purposes of this article it doesn't matter.

What does matter is the behavior that I saw, which was most puzzling:

I placed a printf() statement above the top of the do ... while loop, in the "set up variables" section.

That printf was executed each time I accepted a new connection!

Well, OK, I've sort of given it away, but I admit I was sorely puzzled: how could the printf statement be executed on each new connection, when that code wasn't even inside the loop?

OK, here is a reasonable place to stop and think for a second, to avoid spoiling the fun too much.

Have you figured out the answer?

Here it is: the printf statement actually wasn't executed each time through the loop. It was only executed once. But, the printf statement was buffering its output, and the buffered output was present in the process's memory space, and when the process forked a new child process, the fork system call naturally duplicated the buffered printf output, and then when the child process executed a completely unrelated printf call of its own, it also flushed (and hence apparently re-executed) the buffered output from the parent!

So, everything was fine, it was just that the interaction of a buffered and un-flushed bit of printf output, and the thorough duplication of process state by the fork API, made me think that the code was being run twice, when in fact it was just the data that was being duplicated.

As the wonderful Raymond Chen says:

When something stops working, you begin developing theories for why it doesn't work, and normally, you start with simple theories that involve things close to you, and only after you exhaust those possibilities do you expand your scope. Typically, you don't consider that there is a global conspiracy against you, or at least that's not usually your first theory.

When programming, and debugging, it's so easy to convince yourself that your theory is correct, and to find ways to force the evidence to match your theory. So when something seems impossible, stop and think: it's unlikely there is a global conspiracy against you, you're just looking in the wrong place!