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.
Filed Under: linux, patents
Companies: bedrock computer technologies, google
Comments on “Google Loses Patent Case Filed By Patent Attorney Who Was Helping Fight Patent Excesses”
What are the chances that that is the entire point? I suspect that this is an underhanded way of making sure Linux server users pay money, then people can genuinely say that it’s not free and harms innovation.
Re: Re:
I seriously doubt it’s a malicious or anti-competitive attack on Linux. Much more likely to be a greedy grab for a fruit that someone decided was hanging low enough to be worth reaching for.
Re: Re: Re:
And there’s a difference…how, precisely?
Re: Re: Re: Re:
A directed attack on linux would probably be multi-vectored. Someone going for money won’t be trying to completely take down linux as a force in the market, even if they could have that effect. Intent does matter.
Re: Re: Re:2 Re:
So what if GNU/Linux is attacked. There is the BSDs one can always choose and run the stuff that makes a “server” valuable to end users.
Re: Re: Re:3 Re:
I like to think that the various free BSDs and Linux offer each other healthy competition, I’d prefer to see them both around in the future. An attack on Linux hurts the whole open source software community, not just the distribution in question.
Re: Re: Re:
At some point real soon we as a people will have to stand up against this kind of behavior.
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.
Re: Re:
Or it’s a way to help IP maximists point to any superiority IP based operating systems may have (ie: Windows) and claim, “See, IP helps the produce better operating systems”.
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.
Re: Re: Re:
But if IP helps produce better operating systems and they point to their alleged IP in Linux, wouldn’t they then claim by extension that Linux is a better operating system?
Re: Re: Re: Re:
No.
Re: Re: Re: Re:
(that would make sense, and IP maximists hardly ever make any sense).
Re: Re: Re: Re:
Linux is a far better operating system than anything microsoft have ever produced and that is what they are afraid of.
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.
Re: Re: Re:
Or it’s a way to help IP maximists point to any superiority IP based operating systems may have (ie: Windows) and claim, “See, IP helps the produce better operating systems”.
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…
Re: Re: Re: Re:
That’s another thing. Patents allegedly promote inventive transparency, Microsoft has all these patents, yet their operating system is still closed source. Where is this inventive transparency they speak of?
Patents
It’s all about money. Google is trying to make money and so is the patent troll or computer company. The whole system is geared to making money. What makes Linux users exempt from the game?
Re: Patents
What makes Linux users exempt? As one of those Linux users, I’d have to say nothing does, nor do I think that’s really the point. In fact I get far more done with Linux than I ever could with Windows in the same time, or even at all for some things; In other words, at twice the cost per seat of Windows, it would still be a bargain.
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.
Re: Re: Patents
and why should those people who are worthy of evaluating patents be wasting time evaluating patents? They should be spending that time innovating instead. That’s one reason I say we abolish patents. It’s a waste of time and resources, time and resources that can better be spent innovating.
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.
Re: Re: Re: Patents
(Sorry Nom du Clavier, meant that to be a response to
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.
Re: Re: Re:2 Patents
Indeed, even if patents were a good idea and intended to protect the little guy from the big guy, the way they’re used today is pretty much the opposite of that original intention.
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.
Re: Re: Re: Patents
Too true, I agree wholeheartedly.
How can end users infringe
I do not understand this situation. How can an end user of a product infringe on a patent? How can they be expected to be aware of possible patent infringement? I understand that Google did roll their own version of Linux, but I would hazard that they did not create the functionality that “infringes” on the use of this horridly obvious patent.
Re: How can end users infringe
patent owners have the exclusive right to “use” the claimed invention. So if you’re “using” it (e.g., performing the claimed method), you’re infringing.
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.
Obviousness
This patent is obviously obvious. I think the method used to get a patent for this obvious storage and retrieval technique is probably patentable.
Re: Obviousness
I think the point is that this patent is obvious to anyone with any reasonable understanding of computer operations and programming. However, most patent examiners are probably not software engineers. And most jury members probably wont be either.
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.
Re: Re: Obviousness
I don’t think I’ve ever read a more succint summary of the patent situation that at the same time hits the nail on the head. Kudos.
Hey, this patent may be obvious, but it does promote the progress (of lawsuits).
Worth mentioning...
It is worth mentioning that this is a jury trial.
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.
Obviousness
A few have already commented on the obviousness of the patent, but didn’t support that with details.
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.
Re: Obviousness
“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””
Of course this never occurred to anyone prior to the awe inspiring brain storm described within this patent.
/s
Re: Obviousness
You mentioned “includes code!” so I checked out the patent claim.
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.
Re: Obviousness
“It seems trivial to work around the patent by simply using other hash table structures that don’t include linked-lists.”
Seeking patents to work around isn’t the intended purpose of the patent system. Promoting the progress is.
Re: Re: Obviousness
The fact that we should have to work around such a dumb patent, and all the other dumb patents out there, itself is unacceptable. The patent system becomes a minefield, you have to keep working around each mine in hopes that your work around doesn’t step on another mine. Have you ever played the game twister. That’ what this is. This is not what the patent system should be about.
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.
Re: Re: Re: Obviousness
“I must repeat the process again for the next line of code.”
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.
Re: Re: Re:2 Obviousness
and so forth for each successive line *
Re: Re: Re: Obviousness
and this patent is on a general idea, not a specific implementation. It thought patents aren’t supposed to be on ideas, but specific implementations? The patent doesn’t cover any specific set of source code in any specific language, it covers this broad idea.
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.
Re: Re: Re:2 Obviousness
I thought *
Prior Art Located-- In an Obvious Place to Look
Slashdot has already located the prior art, in Knuth, dating back to 1973.
http://linux.slashdot.org/story/11/04/21/2140249/Google-Loses-Bedrock-Suit-All-Linux-May-Infringe
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.
Re: Prior Art Located-- In an Obvious Place to Look
The patent office should start crowdsourcing before approving any patent.
Re: Re: Prior Art Located-- In an Obvious Place to Look
http://www.peertopatent.org/
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.shtml
http://www.techdirt.com/articles/20090709/1907055504.shtml?threaded=true
http://www.techdirt.com/articles/20080916/0249512282.shtml
Re: Prior Art Located-- In an Obvious Place to Look
The reference in slashdot does not discuss what is unique in this patent. The unique part is deleting expired entries in the linked list pointed to by an entry in a hash table. I looked through my copy of the 2nd edition of Knuth’s, The Art of Computer Programming. On page 533-34 Volume 3, he discusses deletions from a hash table. He notes the difficulty of doing so except in the case of a hash table using external chaining.
“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.
Re: Re: Prior Art Located-- In an Obvious Place to Look
This [using external chaining to make deletes easy] is exactly what the patent covers. It’s an exercise in a college textbook!
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.
Re: Re: Re: Prior Art Located-- In an Obvious Place to Look
No part of this patent is novel in itself. I was pointing out that there is certainly prior art to deleting entries in external chains belonging to hash table entries. Your point is well taken, but opportunistic removal of linked list entries as opposed to a dedicated garbage collection process or thread is not novel either. Embedded systems often had proprietary kernels that were single tasking at least until the early ’90s when it became easier to get a license for a pre-packaged OS like PSOS. Any data structure that required garbage collection had to have this done in an opportunistic way during normal access. The only thing that may, perhaps, be novel is combining all three aspects:
-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.
Re: Re: Prior Art Located-- In an Obvious Place to Look
It’s an exercise in a college textbook!
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.
Clearly, software should not be patentable.
?...many Linux users all around the world...?
But patents are not valid ?all around the world?.
OK, how do you NOT infringe this patent?
Suppose you want to make something that retrieves a lot of data that tends to age and expire, like a podcatcher or a usenet news server, or a file backup system… how can you possibly avoid infringing 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.
It must be lawsuits like this one that convinced Google to try to buy up all of Nortel’s patents, for “defensive purposes.” Since Intellectual Ventures started suing, I now completely disbelieve the claims of any business entity that it is buying up patents for “defensive purposes only.” However, even when it does inevitably start suing, Google will likely be able to evade the “patent troll” label (and thus take advantage of judicial preference for “practicing” entities over NPEs/PAEs), since it also engages in R&D. Clever.
Anyone remember Pick???
The Pick System / Microdata Reality System and too many flavors to name which goes back to early to mid 70’s used hashing with chaining filesystem / database and such techinques as described by patent…
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…
re: [aldestrawk] The jury determined that the patent was valid.
On what basis did the jury determine 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…
Only you can’t tax Linux this way… due to the GPL, in the FSF’s position it’s implicit in the license that you can’t distribute unless you can pass on all the same terms you have. They count patents as part of that (it’s not in the GPL as written but they feel that it’s implied by it’s terms, GPL3 makes this explicit, but Linux is not under GPL3).
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)
patent rights
Hi, if it were your patent, you might feel different. When you find a wallet on the street the law hold that possession is only 9 tenths of the law; that means that if any one can prove a better claim of ownership, that person is rightful owner. And that is where the one percent comes from ; like it or not. Look up pat 5893120 and you will find the owner of the wallet that Google rifled through. 007 wingman