Why SMR/ROP/VZOOM is not the special case of RCU?
Dmitriy Vyukov
mutual-exclusion and maintaining coherency in a multiprocessor system
utilizing execution history and thread monitoring":
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=5727209.PN.&OS=PN/5727209&RS=PN/5727209
Claim 1:
"1. A method of using an updater thread to update an original element
of a shared data structure in a computer system while maintaining
access to the data structure for reader threads, the method comprising
the following steps:
[1.1] with an updater thread, updating the original element by
creating a new element;
[1.2] with the updater thread, modifying links used by reader threads
for referencing the original element to now reference the new element;
and
[1.1] using a summary of thread activity to determine when the
original element may be erased."
Consider SMR:
Point [1.1] is true for SMR, point [1.2] is true for SMR, point [1.3]
is true for SMR. "a summary of thread activity" for SMR is a set of
hazard pointers.
Consider ROP:
The same as for SMR.
Consider RCU+SMR:
The same as for SMR.
Consider vZOOM PDR:
Point [1.1] is true for vZOOM, point [1.2] is true for vZOOM, point
[1.3] is true for vZOOM. "a summary of thread activity" for vZOOM is
means for "determining if there are any persistent references to the
data object by application threads in the plurality of application
threads" (particularly "a set of per thread array of counters")
So it seems for me that this patent covers all PDR schemes out there.
Term "a summary of thread activity" is very broad, so it can be
applied to anything.
Can anyone comment this and, I hope, disprove my statement.
Dmitriy V'jukov
Chris Thomasson
news:1181313129.8...@o11g2000prd.googlegroups.com...
> Patent 5,727,209 "Apparatus and method for achieving reduced overhead
> mutual-exclusion and maintaining coherency in a multiprocessor system
> utilizing execution history and thread monitoring":
> http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=5727209.PN.&OS=PN/5727209&RS=PN/5727209
>
> Can anyone comment this and, I hope, disprove my statement.
The fundamental difference between vZOOM and RCU is that references in RCU
simply cannot span multiple quiescent states. This limitation does not exist
for vZOOM:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/1216861ac568b2be
Chris Thomasson
news:1181313129.8...@o11g2000prd.googlegroups.com...
> mutual-exclusion and maintaining coherency in a multiprocessor system
> utilizing execution history and thread monitoring":
> http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=5727209.PN.&OS=PN/5727209&RS=PN/5727209
>
> Claim 1:
I think one could claim different methods for detecting quiescent states. I
made sure to point my lawyer to the exact same patent you reference back
when I was doing the patent feasibility study.
The fact that a reference can overlap multiple quiescent points is a major
fundamental difference between vzoom and rcu.
Dmitriy Vyukov
> The fact that a reference can overlap multiple quiescent points is a major
> fundamental difference between vzoom and rcu.
But there are said only "using a summary of thread activity to
determine when the
original element may be erased"! There is nothing about quiescent
points and object lifetime!
> The fundamental difference between vZOOM and RCU is that references in RCU
> simply cannot span multiple quiescent states
This is just well known thing about RCU. But the patent claims is the
only "official" thing afaik. So they patent exactly next: "using a
summary of thread activity to determine when the
original element may be erased" and nothing more. Yes there are some
other words in "Abstract" part of patent - something about "quiescent
states" and "object generations". But there is nothing about it in
"Claims".
Dmitriy V'jukov
Chris Thomasson
when your reading patents IMHO.
The fact that RCU requires the references to be confined and executed before
a quiescent state is key aspect of RCU algorithm as a whole.
If you try to use persistent vZOOM reader-pattern algorithm with RCU you
will crash. There different.
The SMR patent will be approved along side the RCU patent. SMR uses
per-thread data. Sure, thats public domain. The idea of per-thread data
being polled is nothing new. Is the quiescent state tracking and the rules
for the reader references which state that they must be confined.
Confined in the sense that a reference in RCU:
my_func() {
rcu_read_lock();
foo_t* const _this = rcu_dereference(&shared_data);
rcu_read_unlock();
[my_func processing]
if (_this) {
rcu_read_lock();
_this->do_something_illeagle_with_rcu(); // boom!
rcu_read_unlock();
}
}
Its key aspect of their proofs.
Chris Thomasson
news:ppidnVsYJs2KB_Tb...@comcast.com...
> The broad claims get narrowed down. You focus on the narrow claims first
> when your reading patents IMHO.
>
Please note that the teachings must match and support the claims. So the
patent teachings are important.
Joe Seigh
If it really was that broad, the claim would be invalidated
since there's prior art in that area. That's the RCU patent
and it's understood to refer to tracking of "quiescent states".
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Dmitriy Vyukov
> Please note that the teachings must match and support the claims. So the
> patent teachings are important.
Do you mean part "DESCRIPTION OF EMBODIMENTS" of the patent?
Dmitriy V'jukov
Dmitriy Vyukov
> The broad claims get narrowed down. You focus on the narrow claims first
> when your reading patents IMHO.
There are narrow claims:
"
14. The method of claim 13 in which the execution history data are
further stored in a generation counter.
15. The method of claim 13 in which the execution history data are
further stored in a thread counter.
"
So can I patent RCU with another method of storing/tracking of
execution history and use such RCU w/o permission from IBM?
Dmitriy V'jukov
Dmitriy Vyukov
> If it really was that broad, the claim would be invalidated
> since there's prior art in that area. That's the RCU patent
> and it's understood to refer to tracking of "quiescent states".
And how do you think, what from the following are fundamental points
of RCU? By fundamental points I mean following. If my invention don't
have at least one of them, I can patent the invention as unrelated to
RCU. You can mark only "yes" (fundamental point) or "no" (not
fundamental point)
1. References cannot survive through quiescent state
2. We can "delete" some more objects only if *all* threads pass
through quiescent state
3. We have some "generations" of references. For example, "current"
and "new"
4. We detect only whether thread pass through quiescent state or not.
I.e. we don't collect any other information
Dmitriy V'jukov
Chris Thomasson
This is the fundamental key aspect of RCU.
> 2. We can "delete" some more objects only if *all* threads pass
> through quiescent state
> 3. We have some "generations" of references. For example, "current"
> and "new"
> 4. We detect only whether thread pass through quiescent state or not.
> I.e. we don't collect any other information
2-4 are methods of claim 1.
Chris Thomasson
Yes. Everything but the claims.
Chris Thomasson
It must be a novel method and you should talk to Paul about it.
David Schwartz
Dmitriy Vyukov wrote:
> So it seems for me that this patent covers all PDR schemes out there.
> Term "a summary of thread activity" is very broad, so it can be
> applied to anything.
You would have to carefully read the entire specification to see what
the term "a summary of thread activity" really means. It could mean
that every thread on the system passes a particular quiescent point,
but it could also mean something else.
Sadly, to be sure what the term means in the patent, you would also
need to see the patent's prosecution history. If the patent examiner
complained that the term might include some previously known or
patented ideas, they might have disclaimed the broadest possible
reading of that term. Such a disclaimer would be binding on them when
it comes to enforcing the patent.
DS
Chris Thomasson
news:1182022382....@d30g2000prg.googlegroups.com...
>
> Dmitriy Vyukov wrote:
>
>> So it seems for me that this patent covers all PDR schemes out there.
>> Term "a summary of thread activity" is very broad, so it can be
>> applied to anything.
>
> You would have to carefully read the entire specification to see what
> the term "a summary of thread activity" really means. It could mean
> that every thread on the system passes a particular quiescent point,
> but it could also mean something else.
Yup.
> Sadly, to be sure what the term means in the patent, you would also
> need to see the patent's prosecution history.
Yeah... Didn't somebody already get sued over this particular algorithm?
;^)
Chris Thomasson
There is a "clause" in all patents that says something like:
"Of course those skilled in the art will be able to think of other ways to
implement the claims."
You should feel completely comfortable explaining the fundamental
differences between your algorithm and RCU to a Jury...
Chris Thomasson
>> Sadly, to be sure what the term means in the patent, you would also
>> need to see the patent's prosecution history.
>
> Yeah... Didn't somebody already get sued over this particular algorithm?
http://news.com.com/2100-1016_3-1017965.html
:^0
Dmitriy Vyukov
> Sadly, to be sure what the term means in the patent, you would also
> need to see the patent's prosecution history. If the patent examiner
> complained that the term might include some previously known or
> patented ideas, they might have disclaimed the broadest possible
> reading of that term. Such a disclaimer would be binding on them when
> it comes to enforcing the patent.
Sh#t. Sorry.
I always think that this is very formal field. And I just can read
those formal claims. And then formally identify whether those claims
cover my invention or not.
So it seems that this it is impossible for single human to cope with
all this... sh#t.
And as I understand even if I publish my ideas in some journals, and
then make some software based on the ideas, after few years they can
came to me and say "we want $3 billion from you for using our
intellectual property". Sh#t.
So it seems for me that the only solution for single human is to came
to IBM/SUM/Microsoft and say "Hey, I can sell to you some cool stuff,
and you can patent it, I just want $X for it" :)
Dmitriy V'jukov
Chris Thomasson
> So it seems for me that the only solution for single human is to came
> to IBM/SUM/Microsoft and say "Hey, I can sell to you some cool stuff,
> and you can patent it, I just want $X for it" :)
They can always choose to recreate your idea with some minor changes, and
say something like "our lawyers are bigger than yours, Ha!"...
Of course that would be the worst case scenario!
;^0
Dmitriy Vyukov
> They can always choose to recreate your idea with some minor changes, and
> say something like "our lawyers are bigger than yours, Ha!"...
Yes, yes. I think that they even can recreate my idea without changes
at all and say "@#$% off!" :)
Thus the situation is bad for every little person...
Dmitriy V'jukov
Dmitriy Vyukov
> Yes, yes. I think that they even can recreate my idea without changes
> at all and say "@#$% off!" :)
> Thus the situation is bad for every little person...
So the only choice is to make contract with the devil and work for
them :)
Dmitriy V'jukov