Court rules Linux kernel infringes on patents. Lawsuit avalanche to follow.
zdnet.com
zdnet.com
Let's say Aunt Marge clips coupons. She clips a lot of coupons, so she keeps them in one of those index files with a slot for each letter of the alphabet, by product name. When she goes looking for a coupon, say for coca cola, she goes to the "C" slot and flips through the slot looking for a coca-cola coupon. If while flipping through she pitches out expired coupons then she has infringed this patent. (if she does it "with a computer")
Edit: This is just claim #1, there are more variations claimed.
And here's the reason: Aunt Marge isn't using a linked list. That is, each coupon doesn't point to the next coupon in the list. It's simply a collection (or array) of coupons.
Now, let's bring this back to a point that's somewhat more relevant. If you did implement something more analogous to Aunt Marge's coupon collection (say an array), and trimmed out items as the code noticed they were expired, would you infringe this patent? Maybe not. I haven't tried reading the details of the patent, but if the article is correct and if, as in every other case, every detail of the patent matters, then I'd wager your array-with-expiring-items would not infringe.
And that is what's wrong with software patents. Maybe we've been expiring items from collections, dictionaries and arrays for a long time. But suddenly, apply it to a linked list and you've infringed the patent. Nonsense.
[spelling edit]
The slot is not an array, it is not directly accessible by index number or key. It is close to a doubly linked list with a head and tail pointer, but it has more operations than a linked list though. You can flip through by "a bunch" and easily start at a randomish middle point which doesn't map back to linked lists, but also isn't important for this example.
First few that come to mind: conga line, necklace, bike chain and DNA. Tangentially, lines of people forming a queue or a push down stack of dishes or the number you pick at the deli counter for your turn forming a circular buffer. All of these are examples of physical world linked lists.
• The examples all seem to include back links as well.
• Most of them you can access an interior element in constant time.
• Most of them you can get a size estimate without traversing.
• The dishes are more stack like. Traversal is destructive, but it doesn't add operations. (I think)
• The deli numbers give you a constant time "distance between" operator (unless the deli has lost a lot of the tags), and require a global method dispatch to find "next". 37? 37?… 38?
[1] Somewhere in the '80s, Dr. Roman[2] was explaining binary search to a class of 'us' and started to use a phone book analogy, until he realized that people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. That's stuck with me as a caution of the difficulty of analogy.
[2] Oh look, he is department chair now. Well done! (Warning to students: if you are having trouble in CSE425S (formerly CS 455) with the programming-language-of-the-week being prolog, and you figure out how to build yourself variables, he will see through you and give you a bad grade, my poor little grid bugs.)
Perhaps a better analogy would be binary searching in a phone book or dictionary for a foreign language.
You can force it by not letting the person see the key, only the results of the comparison, but that is a little silly.
Maybe some of the mismatch comes from the human heuristic being so much faster than the physical turnpage-readname-compare operation. In a computer the compares are so fast that there isn't really a point to building a heuristic to optimize away the first few.
If the comparison finding were slow on a computer you would not use binary search, so in a sense you are forcing the human to use the wrong algorithm.
It turns out that interpolated binary searches are useful in computers, in cases where the structure being searched has a significant overhead for each read - for example, seeking in variable-bitrate-encoded video streams is such an application.
Project A contains a generic collection. Project B contains an abstraction of objects with expiry times. Project C instantiates A's collection for B's objects.
Now assuming A implements the collection using linked lists and C uses A and B as black box, linked libraries, does anyone infringe on the patent?
So unless Project A's generic collection implements an optional callback that is called on every object seen while searching the collection, project C uses that callback to delete expired objects, you'd seem to be in the clear.
It would be interesting to get the materials from the trial and see how both sides explained the patent to the judge and the jury. During pretrial both sides will have made a technology presentation to the judge to explain their take on the background of the patent and what it does, and then during the trial both sides will try to explain to the jury what the patent means.
Some of these presentations can be very good content-wise and very well produced and presented.
I think you went too far in the interests of dumbing things down.
> 7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program.
This, if left to stand, is game changing (and bad, imho).
>> Performing storage and retrieval that uses the hashing technique with the external chaining method for collision resolution.
Isnt this just describing a hash table?
>> In order to prevent performance deterioration due to the presence of automatically expiring data items, a garbage collection technique is used that removes all expired records stored in the system in the external chain targeted by a probe into the data storage system.
So the software doesn't run slowly, we're going to do something special to get rid of those pesky expired records.
I believe, "removes all expired records stored in the system in the external chain targeted by a probe into the data storage system." is just preparing you for the description of what they're going to do, without actually saying anything.
>> Each insertion, retrieval, or deletion of a record is an occasion to search an entire linked-list chain of records for expired items and then remove them.
Whenever an action is taken on a record, remove expired records near the record targeted by the action.
>> Because an expired data item will not remain in the system long term if the system is frequently probed, it is useful for large information storage systems that are heavily used, require the fast access provided by hashing, and cannot be taken off-line for removal of expired data.
Expired items don't stay long. System doesn't have to be taken offline to remove expired items... Because they remove expired items after CRUD of a record takes place, I guess.
Surely I'm missing something here. Or is it just that silly that you can get a patent on something like this?
What I imagine happened is some programmers at a now defunct company wanted to get their names on a patent because it's cool. They come up with the most generic algorithm ever, easily get it patented, and then they get to brag to their drinking buddies.
Then, the company they work for goes out of business/gets bought and the patent is transferred to a patent troll like this Bedrock company who then try to find where it 'infringes'.
That's all my imagination, but similar things have happened.
What I just learned with this article is the Bedrock company is no longer active...how can you win a case when you're not even an active company anymore!?
Note: I don't have a tremendous amount of sympathy for any large company like Google, Oracle, Apple, Amazon, etc. who get sued for silly patent 'infringements' because they would do the same in a heartbeat. ALL software patents should be abolished.
Google would?
One of these things is not like the others.
[1] http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec...
I put "novel" in quotes because the courts seem to use a hair-splitting definition of it. I honestly think that, when faced with a pile of Lego blocks, there are patent lawyers who could argue that it's non-obvious that one could combine them.
I have this (most likely irrational) fear that one day I'll be on trial related to some work I've done, and my fate will be decided by 12 average people, who are decidedly not my peers, and don't have the background (or capacity even) to understand the relevant concepts of the case.
Maybe the article itself is still good, but just FYI.
"Implications for Android: Concerning Android, I wouldn't rule out that maybe some of the hundreds of thousands of Android applications out there use the teachings of the infringed patent claims in one way or another."
Wow, developer FUD much? Let me propose a small fix for you Florian:
"...I wouldn't rule out that maybe some of the millions of software applications written since this patent was filed use the teachings of the infringed patent claims in one way or another."
Why single out Android on this? oh wait, I forgot, because it's Florian...
The real questions are things like what version of Linux infringed? Has that code been removed yet? I have to think it would be removed the minute people found out. Was the infringing code part of the main kernel, or something else? I seem to recall a mention of RHEL, so maybe it's specific to that.
That said, it's a real danger. Even if the patented code is removed, they can (and will) go after people for past damages. They're a patent troll, that's what they do. And you can expect all future cases to be filed in East Texas. There's also no more escape clause, because they'll just sue batches of people who are distributed all over the country or world and claim that East Texas is just as good a place as any because no forum would be more convenient.
The best fix for this is to get the law changed to eliminate software patents entirely. Maybe, just maybe, i4i will help with that, but I'm not sure. Reexamination requests are also in order. Hopefully this patent will get busted soon
Ultimately, this is just another reminder of why software patents are a bad thing.
This makes Android the most likely target among Linux-based phones and tablets for the patent owners to go after next, since they have already established (until/unless Google can get it overturned on appeal) that their patent is valid against Google. They can try to leverage off that and bring in Android as just more instances of the same overall infringement.
If I write code to target a platform whose implementation infringes a patent somewhere deep 'beneath the hood' I am not liable to pay any damages for that, I did not ship infringing code and my code is agnostic to whether the platform infringes or not.
I cannot see the need (besides FUD) for Florian to have written that. He mixes cherry picked facts and analysis with wild speculation (commonly involving Android's 'bleak future') and hopes that people won't see the difference.
Edit: As another example, see how he conveniently forgot to mention the factor of the finding coming from an East Texas court when he extrapolates from this verdict to all Android related patent suits.
import scala.collection.mutable.LinkedList
class ExpiringHashTable[K, V] {
case class Elem(key: K, var value: V, var expires: Long)
private val BUCKETS = 10
private val store = new Array[LinkedList[Elem]](BUCKETS)
for(i <- 0 until BUCKETS) store(i) = new LinkedList[Elem]
def put(key: K, value: V, expires: Long): Unit = {
val b = bucket(key)
store(b).find(_.key == key) match {
case Some(x) => {
x.value = value
x.expires = expires
}
case None => {
store(b) = new LinkedList(Elem(key, value, expires), store(b))
}
}
}
def get(key: K): Option[V] = {
val now = System.currentTimeMillis
var result: Option[V] = None
// BUG: This doesn't handle the first element in the list being expired
var prev: LinkedList[Elem] = null
var i = store(bucket(key))
while (i.next != i) {
if (i.elem.expires < now) {
prev.next = i.next
} else if (i.elem.key == key) {
result = Some(i.elem.value)
}
prev = i
i = i.next
}
result
}
private def bucket(key: K) = key.hashCode % BUCKETSYa, there's a bug. Too busy ATM to think about the clean way to fix it.
Now, let's get this patched in the kernel source.
There might be some cleverness in the specifics of integrating it into the internals of maintaining the hashtable, but I haven't read the detailed description to check. ( http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec... The idea is in three short paragraphs at "BRIEF SUMMARY OF THE INVENTION", and the problem is at "BACKGROUND OF THE INVENTION". The part I haven't read is "DETAILED DESCRIPTION OF THE INVENTION".
I wish the specific details were given of the reasons for why this parent was held valid, how exactly linux was found to infringe.
https://secure.wikimedia.org/wikipedia/en/wiki/Microsoft_wor...
Can this be appealed?
This particular suit is a tiny chink in a big dam. But, enough of these little patent trolls, as well as a few heavy hitters like Oracle, going after Google could cause them (and other Linux distributors, as well) significant pain. Fighting every patent claim is the only sensible choice. If patent trolls know Google never rolls over, and they're going to have to litigate every single time (and lose a lot of the time), they may be more hesitant to go after Google, and may instead choose more compliant targets.
If I were in Google's shoes, I'd do the same thing.
It may be that acquisition would now be a reasonable response, though the price of the company just went way up because of this win...unfortunately, now their patent troll business model has been validated.
Careful of what you read as some of this seems to have the MS tinge of Linux infringes..