Potential legal issues with lock-free / wait-free structures / algorithms

softwareengineering.stackexchange https://softwareengineering.stackexchange.com/questions/322298

Question

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.

Background

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?

Was it helpful?

Solution

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

Licensed under: CC-BY-SA with attribution
scroll top