Texas jury finds Google infringes a patent: $5,000,000 damage award | Hacker News Reader

Texas jury finds Google infringes a patent: $5,000,000 damage award

fosspatents.blogspot.com

A patent for searching a linked list? This is disgusting.

As a middle finger, here's me infringing on it.

  typedef struct node {
    struct node *next;
    void *data;
  } node_t;
  
  void *find(node_t *head, void *what, int (*cmp)(void *, void *)) {
    while(*head != NULL && cmp(head->data, what) != 0) {
      head = head->next;
    }
    return head;
  }

Of course, there is an age old infringer on this patent:

  (define (find ll what)
          (if (or (null? ll) (eq? (car ll) what))
                  ll
                  (find (cdr ll) what)))

You didn't read the patent, did you?

I did, the only part my code sample doesn't involve is expiring the oldest record, which is:

  void expire(node_t **head) {
    node_t *next = (*head)->next;
    free(*head);
    *head = next;
  }

In terms of using a linked list as an LRU cache, this is done in the Java SDK by LinkedHashMap:

http://download.oracle.com/javase/6/docs/api/java/util/Linke...

http://grepcode.com/file/repository.grepcode.com/java/root/j...

Except that the patent doesn't do any "expiring of the oldest record" and it's not LRU.

The patent includes expiring the records in the linked list, and removing (some) expired records when doing the search:

  #define EXPIRE_LOOKUPS 500

  typedef struct node {
    struct node *next;
    void *data;
    int age;
  } node_t;

  void *find(node_t *head, void *what, int (*cmp)(void *, void *)) {
    while(*head != NULL && cmp(head->data, what) != 0) {
      if (head->next == NULL)
          return NULL;
      if (head->next->age > EXPIRE_LOOKUPS)
          head->next = head->next->next;
      ++head->age;
      head = head->next;
    }
    return head;
  }

(I didn't see the patent specify an actual expiry mechanism in any specific detail, so here's a useless, but patent-infringing one.)

In the case where you expire the last entry of the linked list you will SEGFAULT. A test for head being NULL at the end of the loop would take care of that, but I'd put it in the condition of the while loop since it is probably free on a modern processor given the memory access pattern and it makes something sane happen when a client calls find(NULL,...).

I also don't think the last element ages, but since aging is unrelated to reality that is ok. On second thought, it protects you from the SEGFAULT because the last element can never expire. Very cunning of you.

I'm not seeing the segfault, but it does leak memory like a sieve with no filter.

Good point re: age. ++head->age should be the first operation of the while loop.

Just in case someone is scratching their head over this...

Let's come into the while loop body with data like this where H is the head pointer, C and E are elements of the list...

  H -> C            /* head points to current node */
  C->next -> E      /* expired node is next*/
  E->next -> NULL   /* expired node is last */
  
  if ( head->next == NULL)...        /* no, head points to C, C->next is E */
  if ( head->next->age > EXP...)     /* yes, head->next is E and is expired */
      head->next = head->next->next  /* C->next is now NULL (E->next) */
  head = head->next;                 /* head is now NULL */
  /* back to the top of the loop */
  while( *head != NULL...            /* BANG! a NULL value just got dereferenced */

On the other hand, I can see it makes interviewing a lot more difficult: "I would answer your question, but it would infringe on a patent".

You mean, garbage collection?

s/*head != NULL/head != NULL/ (d'oh)

The title here on Hacker News has been mangled to be incomprehensible or just wrong. This is not a "Linux patent", it is a software patent which is potentially infringed by the Linux kernel.

Note it's the same person here and there.

unfortunately, it's not "potentially" it's "it does", the courts ruled in favor of it being an infringement.

This is one of the disadvantages of open-source software: the patent trolls can easily find places that are violating their bullshit patents. I'm sure Microsoft and Apple also use linked lists, but they're not being sued, because it's harder to prove.

I'm not seeing which part of the Linux kernel is afflicted, but this exhibit from an Amazon case at least suggests that it is for the route cache.

http://docs.justia.com/cases/federal/district-courts/texas/t...

If so, it should be easy to excise from future kernels with minimal performance impact. (I was suspecting filesystem entry caches, but that doesn't show up when I google.)

In a perfect world the patent would not have been issued since it is obvious to anyone skilled in the art that considers when to purge expired entries from a hash table with linked list overflow, especially in a world where systems are constrained by memory access times more than computation. But we are not legislated by that world.

I hate reading patents because I always feel like they try to make it look as complicated as possible. In particular, I always find the inclusion of the computer architecture somewhat useless. Do we really care that there might be 25 software applications running on your computer? Is there any reason other than overcomplication (and thus making the patent appear more novel) to include this stuff?

Because of this, I just want to make sure I understand the patent properly:

From what I can tell, its a patent on a hash table that resolves collisions using chaining, implemented using linked lists. On top of this, each entry has an expiration time and it can remove them as it does lookups for entries.

In particular, I always find the inclusion of the computer architecture somewhat useless. Do we really care that there might be 25 software applications running on your computer?

I think the reason for this is that it moves the patent from an idea/algorithm to one that runs on a physically manifested device.

In the USA, software patentability has always been dubious. But you can patent a complete physical setup that also runs software.

So software patents are usually written as if one had invented some special-purpose device, that just happens to consist of hardware that looks remarkably like a standard PC, running software.

I did a quick read of the patent, 5,893,120 filed in 1997. It seems likely to me to be invalid over the prior art.

The jury dismissed Google's invalidity defense. This is a case where re-examination might be better. A lot of juries simply may not feel comfortable overturning the PTO, even with a lower standard of proof.

The award is peanuts for Google. But establishes a scary precedent. Basically everyone had get ready to give this company effectively a license fee for past shipments of Linux-based products.

What is the problem with that east Texas district?

Nothing. There's a common myth on the internet that it massively favors patent plaintiffs, but in reality it isn't even in the top five.

There are two reasons so many patent suits are filed there.

1. It has judges that have experience with patent suits and like handling them. Whether you are plaintiff or defendant, you want this.

2. There isn't much federal crime there. Criminal cases always take precedent over civil cases on the court calendar. In some districts, especially those where the stupid "war on drugs" is highly active, it can take a long long time to get any court time for civil cases.

Basically a pissed off judge - http://www.technologyreview.com/communications/16280/page1/

It's a rocket docket. So cases move through very quickly. And many of the rulings have been very patent-friendly. There aren't very many judges in that district, either, as I recall.

Now, you will find stats saying that patent holders don't win disproportionately often there. What those leave out is how many EDT cases settle beforehand. Basically, only the strongest cases even go to trial there and they still lose about half the time.

I can't remember if there's a rule requiring local counsel or not, but I know that several firms have set up shop in or near Marshall, Texas.

What a perfectly ridiculous patent.

I find it hard to believe that in the time between the story appearing and your comment you had time to read and understand the patent.

Admittedly, I only read up to the end of the claims section here:

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec...

If you read those and skim to see passages like these:

"The problem, then, is to provide the speed of access of hashing techniques for large, heavily used information storage systems having expiring data and, at the same time, prevent the performance degradation resulting from the accumulation of many expired records. Although a hashing technique for dealing with expiring data is known and disclosed in U.S. Pat. No. 5,121,495, issued Jun. 9, 1992, that technique is confined to linear probing and is entirely inapplicable to external chaining. The procedure shown there traverses, in reverse order, a consecutive sequence of records residing in the hash table array, continually relocating unexpired records to fill gaps left by the removal of expired ones.

Unlike arrays, linked lists leave no gaps when items from it are removed, and furthermore it is not possible to efficiently traverse a singly linked list in reverse order. There are significant advantages to external chaining over linear probing that sometimes make it the method of choice, as discussed in considerable detail in the aforementioned texts, and so hashing techniques for dealing with expiring data that do not use external chaining prove wholly inadequate for certain applications. For example, if the data records are large, considerable memory can be saved using external chaining instead of linear probing. Accordingly, there is a need to develop hashing techniques for external chaining with expiring data. The methods of the above-mentioned patent are limited to arrays and cannot be used with linked lists due to the significant difference in the organization of the computer's memory."

The triviality of the patent should be fairly evident (but if I've jumped to a bad conclusion, I'm happy to be corrected). Fair point though!

It's pretty easy to assert that all software patents are "ridiculous". Math is generally held to be unpatentable after all.

Software is not math. If you think otherwise, please state OpenOffice in the form of a theorem and proof. :-)

Seriously, though, software patents do not involve patenting math. They involve patenting at most the use of math in specific circumstances. By the same token, you can't patent physics or chemistry, but you can patent the application of physics (mechanical and electrical devices) and the application of chemistry (drugs).

http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

It's pretty trivial to show that software is in fact math. Not "approximative with math", like a mechanical device with the laws of physics perhaps, but actually math^.

If you want to express OpenOffice.org terms more easily recognizable to the layman as "math", simply translate the program from whatever it may be written in to lisp, at which point a conversion to lambda calculus is quite clear.

(^ Unless perhaps you also have a definition of "math" that precludes something like the Pythagorean Theorem as well, which is absurd.)

EDIT: Addendum: even if you for some reason don't agree with this, it remains a fact that someone that does hold software patents to be invalid for this reason can easily and reasonably criticize a software patent without first reading it.

Would you say I'm doing math when I write down my recipe chocolate chip cookies? I'd say I'm just describing steps to be executed in order to accomplish a particular real world task. Software is the same--it is steps to execute on a machine to accomplish a task.

Software can be described in ways that sometimes make it amenable to mathematical analysis, but that doesn't make it math.

The Pythagorean Theorem is math--and you can't patent it. However, if you designed, say, a new way to truss bridges, and a key aspect of that was that certain things were of lengths that formed right triangles via the Pythagorean Theorem, it would not be patenting math if a patent were issued on your truss system.

As per the Church Turing Thesis, computation that you do with step by step instructions and computation that you preform with lambda calculus are equivalent.

That you think Pythagorean Theorem is math, but "software" somehow isn't, seems to indicate to me that you are restricting your definition of math to something like arithmetic and symbolic manipulation. That, or similar definitions, is all fine and dandy, but the field of math is not actually limited to such opinions. Regardless of opinion, you can show with math that software is math.

It's just using a different notation than small subset of math they teach you in primary school.

EDIT: If you're still not convinced, check out what Knuth has to say about the issue. I suspect he is a far more rigorous mathematician than either of us will ever be, and his writing is certainly better than my own: http://eupat.ffii.org/gasnu/knuth/swpatknuth.en.pdf

You can go further. Show them the Curry-Howard correspondence:

http://www.haskell.org/haskellwiki/Curry-Howard-Lambek_corre...

"Interestingly, the isomorphism maps programs (functions in Haskell) to (constructive) proofs in logic (and vice versa)."

So not only is software equivalent to math, there are people out there actually writing the software program equivalent to ZFC (one of the most commonly used sets of axioms in mathematics):

http://us.metamath.org/index.html

If that program is math, then all software is math. If that program is not math, please tell me what is.

From what I've seen, lawyers love to draw lines in the air, creating distinctions between things that are, in fact, formally equivalent. I have no doubt that they can, in fact, write some distinction that satisfies them legally, but in doing so, they will be creating a legal fiction wholly alien to mathematicians.

I believe it was Knuth who pointed out that there's no difference between numbers and other kinds of precise information.

The distinction is between the thing and the use of the thing. For instance, you can't get a patent on wood. You can get a patent on using wood to make some particular thing if the use of the wood there is novel, useful, and non-obvious.

Same with software and math. Software patents do not cover the mathematical aspects of software--they cover the use of the mathematics in a novel, useful, non-obvious way (at least when the patent office does its job during examination...).

The logical conclusion of what you're saying is that while you cannot patent the Pythagorean Theorem, you could patent using the Pythagorean Theorem to solve triangles, perhaps in the context of architecture.

That is of course, patently absurd.

"Software patents do not cover the mathematical aspects of software"

As Knuth explicitly notes in the materials I've already linked, trying to separate the math from the rest of software is a fundamentally flawed endeavor.

Software "processes" merely turn one number into another algorithmically. What part of that isn't math?

Is it because the computer usually tells you that the very large numbers in question are pictures, documents, web pages, or whatever else? As far as the computer is concerned, it's a very long number and it's no different from all the other numbers stored on your computer.

But a drug is a specific mixing of certain compounds and chemicals. It's very definite in how it's made.

Patenting a searchable linked list with expiring timestamped nodes is just throwing together a few algorithms in computer science and saying it's new an innovative. There's thousands of way to implement that.

Actually, if it's a software patent, there's a really good chance that it is ridiculous on the face of it.

I don't think you deserve to be downvoted because I made a whitenoise comment. I should have pasted the explanation I made in my defensive response in the first place or not bothered at all. My bad.

I find it hard to believe that a jury, selected at random, would have the necessary background to understand the patent. US patent law is notoriously subtle and complicated.

It's a software patent, so there's no need to read it in order to reach the grandparent's conclusion.

I think that Microsoft Corp. v. i4i Limited Partnership, which was argued before the Supreme Court on April 18, may change how this plays out in the end.

"Since 1983, the courts have followed a clear, firm rule: In order to overcome the statutory presumption that a patent is valid, a litigant must provide clear and convincing evidence that a patent is invalid. That's a high hurdle to overcome. ... Many observers expect the Supreme Court will reject the current bright-line rule and, at least under some circumstances, make it easier for parties to attack the validity of patents." - http://www.abajournal.com/magazine/article/court_may_make_it...

Previously on HN: http://news.ycombinator.com/item?id=2453895 and http://news.ycombinator.com/item?id=2464698

Here is a link to the full text of the patent in question: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec...

Some people have trouble viewing images at the PTO site. Here's a copy as a PDF: http://www.scribd.com/doc/53561493/Pat-5893120

This was generated by the excellent site pat2pdf.org, which I highly recommend for those who want convenient copies of patents.

So here we go again. Last time there was a highly voted fosspatents article here it was completely bogus. And everyone chimed in about how this guy had ulterior motives:

http://news.ycombinator.com/item?id=2355056

Misleading title, dubious blog. This is an anti-Google/Android blogger with likely ties to Google competitors.

http://lwn.net/Articles/434587/

http://news.ycombinator.com/item?id=2428188

I don't see what the author has to do with it. It links to the relevant patents & court files so you can read them yourself.

They just won a judgment against Google for using Linux. Granted, it was in East Texas, but that's where all the trolls file. This is exactly why software patents should not be allowed. I hope the patent gets invalidated soon.

are we actually sure of what is being reported??... he has miss-reported before

About some files in the JDK copied [1] from Sun/Oracle. I think that was, to put it in Wikipedia terms "original research" and that's always risky. Florian was right about the files but his conclusions about the gravity of those findings were wrong as they were not shipped in the end-product.

[1] http://fosspatents.blogspot.com/2011/01/new-evidence-support...

This is ridiculous. The author has a long and excellent record fighting against software patents. On a couple of occasions his analysis may have been an error, but I don't think he's ever mis-reported anything. You comment is just FUD.

There's a good chance that he's a paid anti-Google shill: http://lwn.net/Articles/434587/. Note that in this case he immediately jumps from the verdict to "Android is doomed", when the case had nothing to do with Android specifically except that it uses Linux, as do millions of other products.

How does that prove he's an anti-Google "shill", exactly?

I disagree. I'm also looking for a better source. Florian Mueller has a very bad reputation and was the guy behind "Boycott Novell".

Roy Schestowitz is the guy behind "Boycott Novell". The only connection Florian Mueller has to Boycott Novell is that Boycott Novell calls him "Microsoft Florian" and constantly accuses him of working for Microsoft.

Ah, you're right. Thank you for the correction, I had conflated the two, probably because I hear them both maligned often, or maybe I read another incorrect statement some time ago.

Nevertheless, Florian Mueller is still a controversial figure and has incorrectly reported in the past (see here: http://www.theinquirer.net/inquirer/news/1939165/mueller-for... ). Something like groklaw would be better, but the story isn't showing up there at the moment.

The thing with Florian is that he's never always on one side of the story. Unlike Groklaw, where they openly admit to being in pain if they have to side with MS on a case.

Actually, it's pretty trivial to figure out what side of something Florian is going to be on: just reverse whatever opinion Groklaw happens to voice.

Seriously, check out that guys HN account and look at his comments on any article having anything to do with Groklaw. Totally unhealthy obsession.

So you're saying that he supports i4i in this patent case against MS? I find that hard to believe, since MS is trying to weaken SW patents, which is something he has been trying to do for a while.

I don't think its as simple as you think.

Exception that proves the rule I'd say.

What I have suspected ever since he not so deftly started dodging questions concerning his employment on LWN is that there is a rather specific reason he supports MS over i4i, and it has little to do with software patents.

But in general, without resorting to getting to conspiracy theory-ish stuff, I'd say that 99.9% of the time I'd say his motivation is almost entirely the Groklaw community collectively laughing at him and not paying him the respect he thinks he deserves. His ego was bruised and he doesn't know how to respond as an adult.

That's a rather one-sided view. You are ignoring the fact that Groklaw takes a lot of shots at him. He's critical of rabidly pro-software patent company IBM, and Groklaw doesn't seem to like people who criticize IBM.

> The author has a long and excellent record fighting against software patents.

Based on what? All we have is your (and his) assertion. I had trouble finding any history at all of this guy with "25 years software industry experience". And every single one of his blog posts portrays FOSS software as an unreliable IP minefield. Even if that's not the specific legal issue at hand.

In my opinion this looks like he is paid to smear FOSS.

http://en.wikipedia.org/wiki/Florian_Mueller

According to Wikipedia:

"In 2004, Müller received the support of corporate sponsors 1&1, Red Hat and MySQL for launching NoSoftwarePatents.com, which opposed the European Commission's proposed directive on the patentability of computer-implemented inventions.[8] Following several years of intensive lobbying by many parties, this proposed directive was rejected by the European Parliament on July 6, 2005, with 648 out of 680 votes cast.[9][10]

For his political activities, Müller received several awards in 2005. A leading publication for intellectual property lawyers, "Managing Intellectual Property", counted Müller - such as the Chinese vice premier Wu Yi - among the "top 50 most influential people in intellectual property"[11][12] (renominated in 2006[13]). IT-focused website Silicon.com listed him among the Silicon Agenda Setters.[14] A jury of EU-focused weekly newspaper "European Voice" elected Müller as one of the "EV50 Europeans of the Year 2005", and handed him the "EU Campaigner of the Year 2005" award.[15] Jointly with the FFII, Müller received the "CNET Networks UK Technology Award" in the "Outstanding Contribution to Software Development" category.[16]"

Another example of this: http://www.groklaw.net/article.php?story=20110420141724403

Reply on news.ycombinator.com