While researching the subject matter - lock-free and wait-free data structures - I'm seeing a worrying amount of mention of patents with this area. I've hobby-researched compression algorithms years ago and by comparison the situation seems worse as hard as that is to imagine.


I have a project in progress that at this stage is personal / private but eventually is intended to be profitable targeting western markets (Europe, US, Australia etc). I understand software patents are not so much an issue in Eu, but definitely in US and by extension in Aus to a degree if not as much.

The Issue

With any computational process there are basic units that one can use. I would consider for this purpose that something like an array or list would be a fundamental unit - there are already optimal algorithms & structures researched tried and tested for longer than I've lived, but these are (as far as I know) not subject to any patents or conditional use. Perhaps not in the really extreme case like criminal offenses (in the sense that it isn't a copyright / royalty issue but actual crimes being committed but I digress).

Enter lock-free / wait-free (LFWF).

I could be wrong but it seems to me that introducing such fundamental algorithmic units to thread-safety methodology (any) would be an enhancement in the general case and probably able to be patented. However what if there is a most-simple or most-straightforward way to 'enhance' a structure for parallel processing? Would there not be such 'trivial' algorithms or structures for parallel processing?

The Question

Basically, at what point would a LFWF enhancement to something like a list or map or vector or queue etc, begin to 'stand out' enough as to be patentable or at least 'risky' to use without consulting a patent office / lawyer?

Unrelated but appreciated for consideration - would this not hamper development efforts in this area if the bar is set too low for what is a patentable enhancement to an established free-use concept via LFWF?

I understand LFWF itself is not going to be a concern because the operations themselves - the raw functions' implementations - are compiler / hardware / vendor headaches that a programmer generally would not be involved with anyway.

An Example

Most commonly I've found reference to single-linked list (SLL) structures and algorithms exhaustively patented - is this actually the situation, can I not use my own LFWF SLL ideas for fear of existing patents?

Now, considering something as simple as SLL has only so many ways it could be implemented with LFWF improvements, what sort of implementation am I limited to in order to avoid making something potentially patented already? Or is there no such limit and only specific methodologies are covered?

For analogy, one cannot patent the wheel but one could patent a new sort of wheel that has distinct features / advantages and/or disadvantages. At what point do algorithmic primitives cross the line from wheel to 'new idea' through LFWF implementations thereof?

  • 1
    One of the problems with patents is that these things get evaluated for each individual case, and usually only if a patent actually gets challenged by someone. The decisions are often surprising and hard to predict.
    – Hulk
    Jun 15, 2016 at 12:34
  • 1
    Probably better suited for patents.stackexchange.com Jun 15, 2016 at 12:35
  • @DanCornilescu yeah that may be better, but I'm not sure honestly. If it helps - I'm not interested in claiming ownership of some method, and while this is concerning patents it's more about how to approach the programming-related subject (LFWF) without worrying about patents to begin with (or If I should at all). So really I'm asking more for any experiences had with LFWF-used structures in this area... That said isn't this sort of question exactly what the Legal tag is about? Jun 15, 2016 at 12:43
  • 1
    I'm not saying it's off-topic here, only that you might get better (from the IP protection prospective) answers/comments. Jun 15, 2016 at 12:50
  • Thanks, I'll leave it here and wait a little - if nothing comes up I'll try on patents. Jun 15, 2016 at 12:54

1 Answer 1


This is a very broad topic. Unfortunately there's no general answer, due to the complex matter of patentability. And in view of the existing practice of patent trolling, there is always be some legal risk to be sued in countries in which software patents are accepted.

As a first intro, you may be interested in this WIPO article, and especially TIP3, about patentability criteria. The most significant ones in your case could be:

  • the invention must be new (e.g.not already known/published at the moment the patent is requested)
  • the invention must not be obvious to a skilled person having regard to the prior art.

While this may seems straight forward, the appreciation of what's obvious or not is in reality a russian roulette. This is certainly because programming matters are not always plainly understood by law persons (and vis-versa).

Some examples, to illustrate the complexity of that matter:

  • Someone patented the use of the XOR operation to revert the pixels corresponding to a cursor. While this trick seemed obvious to anyone knowing about boolean logic and trying to work with bitmaps, and was used by a huge number of people intuitively in their developments, someone actually thought of patenting it. And sued a couple of companies with success.
  • Another company patented the execution of an external application invoked from within a hypermedia browser (i.e. a plugin). While such things could seem obvious to skilled professionals used to windowed GUIs -- the browser case being only special situation of a more general windowed application -- the company successfully got a patent. And sued some big players. It costed a lot of years and a lot of lawyers and money to Microsoft, to finally get the patent invalidated and the claims rejected.

So two conclusions:

  • You've seen the surprising cases above. So you'll understand that for something so technical and specialized as lock free structures, it will be even more difficult to gain certainety about the case.
  • Even if you're right, you could need lots of resources to defend your right.
  • This law matter is really complex and needs highly specialized IP lawyers to remain really safe.

Additional reading (and additional examples):

Disclaimer: This is only a personal opinion drawn from my readings as IT professional. This shall in no way be considered as legal advice. For legal advice, consult a lawyer or a qualified legal expert in your juridisction

  • 2
    Thanks, this was exactly what I was after, just needed some guidance / intro into the issue... (still laughing and crying inside on that XOR patent) Jun 16, 2016 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.