Various players in the industry disagree over whether software patents should be granted. Every now and then, a software patent is granted that is just so unbelievably ridiculous that it's not worth the paper that it's printed on.
Linked lists are a common data structure, learned in every basic computer programming data structures class across the nation. So when the USPTO granted the
patent for linked lists, the programming community was shocked.
..:: Prior Art
Even though the patent was applied for in September of 2002, the linked list (including variants) has been showing up in textbooks since at least 1994 (
Taming C++, by Jiri Soukup). That's roughly 8 years before this patent was even applied for.
My own data structures professor actually wrote
his textbook in 1999. Professor Sartaj Sahni's data structure course still remains on the web, with the
1999 Copyright notice. The
syllabus from 1999 even shows both regular linked lists and doubly linked lists in the basic course material. The worst part is that this is merely a junior level course. Professor Sahni has gone on to publish a second edition of his textbook in 2005.
More
linked list modifications and enhancements date back to the 1980s. This 1991 paper even discusses the methods covered by the patent to cut the implementation's complexity to O(log n).
The problem is that prior art means nothing until litigation unless it's prior art from a patented work. Unpatented material (like open source software, and basic public domain material as shown here) cannot be used as prior art. The PTO has policies against the patent examiner searching the internet for prior art. The rationale is that should a patent examiner go searching the web, that searching could reveal confidential information that would be disclosed to numerous other third parties. Any time someone uses a search engine to reach my site, I can see exactly what the visitor put into the search engine (and sadly, we actually license some of these people to operate motor vehicles). The PTO's rationale is very strong, but the cost of not weighing in all that public domain and otherwise unpatented material is so huge. Undoubtedly, LSI, the assignee to this patent, will use this bogus patent in litigation, thus waisting the resources of other diligent programmers.
..:: Obviousness
Various implementations of multiply linked lists are covered in basic college programming courses. If that is not fact enough to prove that this concept is obvious (seeing as it's a foundation of computer science), look at what the textbook authors are saying. Amusingly, Jiri Soukup advertised regarding his 1994 data structures book:
While some commentators to this patent argue that this patent is aimed and backed at multiply linked lists with unconventional sorting methods, the basic implementation of the doubly linked list can be described by the patent's first claim:
The standard in obviousness is whether the invention would have been obvious to one reasonably skilled in the art. How linked lists of unspecified multiplicity, but including singularly and doubly linked lists, can exist as a foundation of computer science since at least the 1980s, yet also be non-obvious in 2002 is ridiculous. Unfortunately, the
Supreme Court won't rule on obviousness until July.
..:: Why this is Important
Steve Ballmer has been shouting about how Linux violates multiple patent's owned by Microsoft. The allegations have become so numerous, but Ballmer has refused to back a single one. It has become so commonplace for Ballmer to spout off these allegations that a
show us the code movement has begun. Open source advocates are requesting that Ballmer stand up to his threats, or quiet himself.
Notably, the basic linux kernel seems to employ LSI's "patented" technology in
/usr/src/Linux/include/scsi/scsi_cmnd.h. The
struct scsi_cmnd happens to be called for two different doubly linked lists. The fact that this patent exists just goes to show that even if Linux does have technology covered by Microsoft's patents, there's not necessarily any merit to any of those claims. Should Ballmer actually pursue action against Linux developers or users, Microsoft stands to lose a significant portion of their patent portfolio, which is undoubtedly licensed to numerous other companies, including the free-sharing of IP agreements with the likes of Siemens.
Post Last Updated: Mar 20, 2007 6:27 am
