Google Loses Patent Case Filed By Patent Attorney Who Was Helping Fight Patent Excesses
from the making-a-point? dept
A bunch of folks have been passing on variations of the story that Google has lost the patent infringement lawsuit filed against it by Bedrock Computer Technologies, concerning patent 5,893,120. The jury has ordered Google to pay $5 million for that infringement. $5 million is pocket change to Google, but hopefully it'll continue to fight. There are some interesting points concerning this case. We had mentioned it in the past, mainly to note the "oddity" of Bedrock suing two tiny Texas companies (one of which was apparently defunct) along with Google, MySpace, Paypal, Yahoo, Amazon, Match.com and AOL. We assumed that this was a really sleazy trick to keep the case in East Texas, which is the favorite spot for patent trolls to file lawsuits. There's also the fact that the owner of Bedrock is David Garrod, a patent lawyer who has also worked with PubPat, the group that seeks to stop some of the more extreme abuses of patent law.Of course, that's all sideshow information. The real fear here is that Bedrock might now be in a position to claim that many Linux users all around the world (especially on the server side) are infringing on the same patent, which might create some pretty serious headaches. Considering how many businesses use Linux servers, this seems like a patent that can be used extensively against all sorts of companies, whose work has absolutely nothing to do with this patent. It could create a new tax for any business using Linux.
Thank you for reading this Techdirt post. With so many things competing for everyone’s attention these days, we really appreciate you giving us your time. We work hard every day to put quality content out there for our community.
Techdirt is one of the few remaining truly independent media outlets. We do not have a giant corporation behind us, and we rely heavily on our community to support us, in an age when advertisers are increasingly uninterested in sponsoring small, independent sites — especially a site like ours that is unwilling to pull punches in its reporting and analysis.
While other websites have resorted to paywalls, registration requirements, and increasingly annoying/intrusive advertising, we have always kept Techdirt open and available to anyone. But in order to continue doing so, we need your support. We offer a variety of ways for our readers to support us, from direct donations to special subscriptions and cool merchandise — and every little bit helps. Thank you.
–The Techdirt Team
Filed Under: linux, patents
Companies: bedrock computer technologies, google
Reader Comments
Subscribe: RSS
View by: Time | Thread
[ link to this | view in thread ]
Re:
[ link to this | view in thread ]
Patents
[ link to this | view in thread ]
Re: Re:
[ link to this | view in thread ]
How can end users infringe
[ link to this | view in thread ]
Obviousness
[ link to this | view in thread ]
[ link to this | view in thread ]
Re: Obviousness
And therein lies the biggest flaw with the patent system. How can the same patent examiner determine obviousness for patents relating to nuclear physics, airplane wing design, drug formulation, acrylic paint formulas, and any other of innumerable possible topics? Only by hiring the most brilliant minds in history could the USPTO have the required expertise to do its job. The problem is that most of these brilliant minds are out actually *inventing* things and wouldnt be content sitting around reviewing other people's inventions. Without a distributed peer review system, it is inherently self-defeating.
[ link to this | view in thread ]
Worth mentioning...
One would hope on appeal the patent will get thrown out, since it describes intelligent, but not innovative, usage of common software techniques.
To put it another way, this is an obvious implementation of standard programming techniques(Hash tables, lists, removal from tables, pointers, etc...). Most OO languages have these components out of the box, even older versions.
[ link to this | view in thread ]
Obviousness
Reading the claims and the detailed description (includes code!), the supposed novelty here is to lazily remove "expired" entries from the linked-lists of hash table while performing other operations, such as searching or deleting, and apparently to determine the "threshold" for expiration "dynamically". I didn't try to figure out what was meant by that.
It seems trivial to work around the patent by simply using other hash table structures that don't include linked-lists.
[ link to this | view in thread ]
Prior Art Located-- In an Obvious Place to Look
http://linux.slashdot.org/story/11/04/21/2140249/Google-Loses-Bedrock-Suit-All-Linux-May-In fringe
http://linux.slashdot.org/comments.pl?sid=2095044&cid=35902328
The "inventor" seems to be ex-Bellcore.
http://pipl.com/directory/name/Nemes/Richard
It is quite possible that if he were put on the witness stand, he would have to admit to having owned a set of Knuth at the relevant dates. It's one of those standard reference works which students are expected to buy.
[ link to this | view in thread ]
Re: Obviousness
Of course this never occurred to anyone prior to the awe inspiring brain storm described within this patent.
/s
[ link to this | view in thread ]
Re:
But it's only because IP makes it difficult for people to create free operating systems with certain qualities without infringing on someones IP, not because IP helps the innovative process.
[ link to this | view in thread ]
Re: Re:
The all branches of government are against the people.
We will be needing to make these kinds of suits unthinkable to bring. The courts do nothing. Without 500 million lawsuits there would be less of a need for Judges.
The politicians do nothing. They are paid to keep this going.
No president will take this on.
It must in the end be the people. On their own. That must deal with this.
It is sad because on their own means it will have to be done outside the law.
Not that I personally advocate violent behavior but I can see the day coming when a company like bedrock has its corporate headquarters destroyed by a flash mob.
Where a lawyer starting up a patent trolling company ends up dead.
People are going to get fed up.
Innocent people will get caught in the middle.
It is not a good thing. I do though see it coming.
[ link to this | view in thread ]
Re: Prior Art Located-- In an Obvious Place to Look
[ link to this | view in thread ]
Re: Re:
[ link to this | view in thread ]
Re: Re: Re:
[ link to this | view in thread ]
Re: Re: Re:
[ link to this | view in thread ]
Re: Re: Obviousness
[ link to this | view in thread ]
Re: Patents
It's how you go about making that money. The whole patent system is a net drain on the entire economy, not just the part in which Linux operates. Non-Practicing Entities (aka patent trolls) bring nothing to the table whatsoever, yet they expect payment. That's hardly just a Linux problem, it hurts everyone.
[ link to this | view in thread ]
Re: How can end users infringe
You're right, of course, that there is no good way for the average end user of an operating system to know what patents they may or may not be infringing.
[ link to this | view in thread ]
Re: Re: Prior Art Located-- In an Obvious Place to Look
http://priorartdatabase.com/
Now we just need the USPTO to review these databases.
Anyways, a discussion of peer to patent can be found below
http://www.techdirt.com/articles/20101012/01364511378/peer-to-patent-about-to-come-back.sht ml
http://www.techdirt.com/articles/20090709/1907055504.shtml?threaded=true
http://www.techd irt.com/articles/20080916/0249512282.shtml
[ link to this | view in thread ]
Re: Re:
This claim holds up until this guy decides to sue Microsoft and gets access to their OS source code during discovery...and finds that Bill Gates and company also uses this.
At which point, your statement can be revised slightly:
But it's only because IP makes it difficult for people to create free^H^H^H^H operating systems with certain qualities without infringing on someones IP...
[ link to this | view in thread ]
Re: Re: Re:
[ link to this | view in thread ]
[ link to this | view in thread ]
Re: Re: Patents
Plus, the entire market has far more resources and incentive to innovate than a single monopolist who can use patents to prevent the rest of the market from innovating.
[ link to this | view in thread ]
Re: Re: Re: Patents
Dave (profile), Apr 22nd, 2011 @ 7:41am
)
But in response to your post
The U.S. grants patents for the same reason that it grants practically all the other monopolies that it grants. To scam the public and exploit the poor. Just like with every other monopoly, I say we abolish patents.
[ link to this | view in thread ]
Re: Re: Re: Patents
[ link to this | view in thread ]
Re: Obviousness
The claim actually does cite Knuth's "The Art of Computer Programming" and Robert L Kruse's "Data Structures and Program Design.
I actually have the first edition of Kruse's book -- not the cited second edition. This book does talk about a hash table using "chaining", which most people would call a linked list. It even has Pascal code examples.
I'll agree that this patent claim has something different. Most hash table with linked lists will implement a retrieve function to do a search for an item and nothing else.
This patent claim puts in a way of somehow marking each item as "expired". Every time you do something with the hash table (insert, retrieve or delete), if it sees any "expired" items, it will immediately remove them. See the comments labled "HEART OF THE TECHNIQUE" and "ON-THE-FLY REMOVAL OF EXPIRED RECORD!".
I'd imagine some other process will mark these items as expired. Personally I'd provide in another (interface) function for the client/application program that would do this.
I will say that this patent covers a variation of hash table that uses linked lists.
So someone uses a normal, textbook hash table with linked lists should be safe. What is not clear is whether Linux uses this hash table variant covered by the patent claim or uses the regular textbook version.
If anyone is really is using this patented hash table variant, they'll have to eliminate the "expired" feature
from their hash tables.
Another possibility is that Linux really does follow the textbook in its hash table implementation, but this particular court couldn't tell the difference between these two versions.
[ link to this | view in thread ]
Re: Re: Re: Re: Patents
Software and pharma patents stand out in that they're even more onerous, because sometimes there's only 'one right way' and the patent can't be worked around... worse, anyone solving the same problem will come to pretty much the same solution.
I welcome people making money off of Linux, just not by leveraging patents. I oppose leveraging patents against Microsoft or Apple just as much, and it's not as if I have a lot of love for those two companies in particular. Patents - in the current incarnation at least, but maybe even by definition - hold back innovation.
[ link to this | view in thread ]
Re: Re: Re:
[ link to this | view in thread ]
Re: Obviousness
Seeking patents to work around isn't the intended purpose of the patent system. Promoting the progress is.
[ link to this | view in thread ]
Re: Re: Obviousness
How many dumb patents do we need to work around. For each line of code that I write, must I search through every patent out there to make sure that it doesn't infringe on someone else's patent. and then when I come up with a work around, I must do another search to make sure that this new work around doesn't infringe. When I finally get a line of code that infringes on no ones patents, I must repeat the process again for the next line of code. I will never get my program written at this rate.
[ link to this | view in thread ]
Re: Re: Re: Obviousness
On top of that, I must then make sure that the combination of the two lines doesn't infringe either, and so for each successive line.
[ link to this | view in thread ]
Re: Re: Re: Re: Obviousness
[ link to this | view in thread ]
Re: Re: Re: Obviousness
and, do you honestly think that Google et al even saw this patent and used it as a basis for building their operating system? Do you honestly think that Google benefited one iota from the patent or the patent holder? I highly doubt it. This is one of those things that will exist just fine without patents. Patents aren't needed for this sort of idea to be thought of, it will be thought of when the need for the idea arises. In other words, this patent did nothing to promote the progress and is only hindering progress which defies the intent of the patent system. This patent should be invalidated and should have never been granted in the first place. Inconveniencing everyone else with the need to work around (or pay royalties for) a ridiculous patent just for the benefit of one person is not acceptable.
[ link to this | view in thread ]
Re: Re: Re: Re: Obviousness
[ link to this | view in thread ]
Re: “...many Linux users all around the world...”
[ link to this | view in thread ]
Re: Prior Art Located-- In an Obvious Place to Look
"Of course when chaining is used with separate lists for each possible hash value, deletion causes no problems since it is simply a deletion from a linked linear list."
Exercise 23 in that chapter is to design an algorithm to do just that. The answers to the exercises references a deletion scheme for coalesced chaining which is a more complicated twist on simple chaining [J.S. Vitter, Algorithms 3 (1982) 261-275]
This is exactly what the patent covers. It's an exercise in a college textbook! The very first thing that comes to mind is to do deletions while doing a search as a separate garbage collection process or thread within the kernel seems a bit cumbersome.
Knuth's 2nd Edition was published in 1998, one year after this patent was submitted. Odds are he wrote this before 1997. The real kicker though is the more complicated scheme for coalesced chaining was published 15 years prior to the patent submission.
The other unique portion is dynamically determining the max number of entries to be removed during any search. If the chains are short, which is generally true for a hash table, then this shouldn't even be something to consider. For long chains, yes, but this improvement is so painfully obvious.
This is the first patent I have fully read. I wrote a scheduler for a kernel in 1991 (A scheduler was just the application mentioned in the patent). I did, on the fly deletion of expired entries in a linked list, but the sum total of entries was not big enough to require hashing. If it had been, I would have added that in without a second thought and without any consideration of patenting the idea. I am so disgusted that this was accepted as a patent I am now speechless.
[ link to this | view in thread ]
Re: Re: Prior Art Located-- In an Obvious Place to Look
Not really. People have been using linked lists for hash chains, or collisions (entries that hash to the same value) since time immemorial. It's a well known way to implement hash tables.
What's "novel" (hardly) here as far as I can tell is the idea of removing "expired" entries while traversing the linked list for other operations. I'm sure it must have been done before this wizard came up with the idea, and it's an obvious (in the patent sense) optimization to reduce contention for list updates, as is shown by the fact that others have independently invented it.
[ link to this | view in thread ]
Re: Re: Re: Re:
[ link to this | view in thread ]
Re: Re: Re: Re: Re:
[ link to this | view in thread ]
OK, how do you NOT infringe this patent?
You have to use hash tables - they are the fastest and most developed data structures, and used everywhere. You have to check the expiration and delete old message. And when you have a big database, it become obvious that you should expire as you seek for the data.
What's most awful about the patent is that the patent refers to some prior art - another patent - that was better than this patent. So it wasn't even an improvement.
[ link to this | view in thread ]
Re: Re: Re: Prior Art Located-- In an Obvious Place to Look
-hash table with simple chaining
-deleting expired entries within the chains.
-do the deletes during another operation (search or add).
This combination is obvious to anyone familiar with these separate parts. Even if there is no other prior art for this combination, Richard Nemes, the inventor has a prior patent which covers precisely this combination. Patent #5121495 with a filing date of Oct. 31, 1989. The only real difference with the later patent #5893120 is the addition of a dynamically determined maximum number of entries to delete at any one time. Nemes sold his #5893120 patent to Bedrock on March 26, 2009. It is not indicated in the court documents if he sold his earlier patent. I suspect not. This may not really matter for this trial which was filed on June 16, 2009, however, his earlier patent expired on Oct 31, 2009. Infringement on the 120 patent should only be possible if the code includes the max limit for deletes. I don't think that part is particularly useful as hash tables should be designed to keep the collision chains short.
For anyone interested, it looks like the code involved deals with route caching. In particular, the rt_genid() function within route.c is referenced in the court documents. I haven't looked at the code yet. From the court documents, it looks like the "infringing" code was added to resolve a DDOS security vulnerability dealing with timely removal of route cache entries. This means the code would only be used by servers that were interested in suppressing a DDOS attack.
The trial is continuing for the other parties besides Google. I suspect it will finish in the next few days as the Linux kernel infringement has already been covered. I think Yahoo is next. What I would like to see discussed (Mike?) is:
-Was patent #5121495 discussed for this trial?
-In patent law does anything beside the filing date or issue date determine the term linit of the patent? Nemes published, in a Bell memorandum, a patent proposal on Sept. 9, 1987. Does this factor into the term?
-Does the 120 patent renew everything? Is 120 considered completely different or can the doctrine of equivalence be applied to 495 to cover most of what's in 120?
-There are two claims involved in the suit. Claim 1 seems to me to be covered by patent 495. Claim 2 is dependent upon claim 1 and is the dynamic max covered in 120. IF 495 had expired, then it seems there could be no infringement.
-The jury determined that the patent was valid. Can an appeal overturn that? Can Google, Red Hat, et. al. get the patent invalidated some other way?
-My feeling is that even if Bedrock wins across the board, there will be no further impact as patent 495 has now expired. I am wondering what a lawyer, in particular, Google and Redhat's lawyers think of that.
[ link to this | view in thread ]
Re: Re: Prior Art Located-- In an Obvious Place to Look
I was about to say the same thing. I'm probably going to be doing exactly the same thing next year, when I take a class in data structures.
That this is patentable at all is ridiculous.
[ link to this | view in thread ]
[ link to this | view in thread ]
Anyone remember Pick???
Maybe Pick should sue Bedrock Computer Technologies, LLC for infringement of it's intellectual property.
Company is bogus / shell established lawyer just to bring suit.
Another disgusting example of our broken systems...
[ link to this | view in thread ]
re: [aldestrawk] The jury determined that the patent was valid.
see my "Anyone remember Pick???"
i read the patent 2-3 times in disbelief. Even his earlier patent should never have been awarded since Pick going back decades earlier has implemented it in their system...
The problems appears to be the people examining the patents don't have a clue, the juries and courts don't have a clue...
Back then company's like Pick did not patent their intellectual property because they did not want it to become public they kept it secret.
Sadly it's now become a game to patent old ideas / implementations that have not been previously patent for whatever reason then sue and settle...
This country's institutions have become such a scam...
[ link to this | view in thread ]
I'd link to the position but I don't remember where I saw it.
Basically it means that anyone who wants to distribute Linux would need to get a patent license that covers everyone they give it to and anyone further down the chain, in other words it would effectively cover every Linux user and distributor there is. If they can't get that they can't distribute. (Or so says the FSF, for GPL3 this is definitely the case since they made it that way on purpose)
I'm curious has Bedrock ever used Linux, if so have they ever done something that could count as distributing it? If so they may have given everyone the right to use Linux.
(Note this implicit patent thing would only cover stuff that could be a derivative work of the software in question so they could still troll proprietary companies)
[ link to this | view in thread ]
Re: Re: Re:
I have been using Linux for 6 months and i would never go back to microsoft products now.
People are like sheep, they just follow what they see in front of them and do not see where the grass is greener.
Why use something that comes from a person that stole from his friends, how can you trust a person like that.
I rest my case.
[ link to this | view in thread ]
patent rights
[ link to this | view in thread ]