Re: [lock-free] Re: 3-thread consensus.

I meant to write *data race* on isFree, not of *race condition*... On Sunday, 19 January 2020 15:18:08 UTC+1, Manuel Pöter wrote: > > Sorry, but what you are writing does not make *any* sense! > > It seems like you don't understand the big O notation, or how to properly > determine the complexity

Re: [lock-free] Re: 3-thread consensus.

Sorry, but what you are writing does not make *any* sense! It seems like you don't understand the big O notation, or how to properly determine the complexity of an algorithm. You can't just *pick *whatever you like to be the argument of O(). BTW: your implementation contains a race condition si

Re: [lock-free] Re: 3-thread consensus.

Hi Manuel, I really thought this list was done... But It appears you still here. Thanks for your patience. This is the first time someone call me a troll. I don't know if this is a detriment or an achievement to an introspect and somewhat arrogant nerd like me. I think I found the misunderstandi

Re: [lock-free] Re: 3-thread consensus.

Hi bittnkr, I am still not sure whether you are interested in a meaningful discussion or not (but most of your responses convey the feeling that you just want to troll around). I will make one last attempt to try to explain your misconception, but if you continue to ignore all arguments and ref

Re: [lock-free] Re: 3-thread consensus.

> So I guess your opinion is just as good? :-) No, I know my facts are better. I'm sure my solution is lock free, because it's O(1) and have no leaks. If you can't see the same, what can I do? Em sex, 17 de jan de 2020 12:58, Nitsan Wakart escreveu: > "everyone has it own ideas of what means

Re: [lock-free] Re: 3-thread consensus.

"everyone has it own ideas of what means to be lock free. " - So I guess your opinion is just as good? :-) If we are willing to redefine lock-free, we can call anything lock-free. Manuel provided you with the accepted view, you seem to think those are just opinions. If there's no agreement on what

Re: [lock-free] Re: 3-thread consensus.

Dear Nitsan, Thanks for your message. You bring me a smile this morning. I really don't think so... I'm not manipulating the words to put an alien meaning on them. But instead, I'm trying to simplify a problem, considered impossible, with a rather new, but simpler and concrete definition of a c

Re: [lock-free] Re: 3-thread consensus.

Dear Bittnkr, You are entitled to your own opinion, not your own facts. The fact is that lock-free is a concrete term that has a current meaning, one that Manuel has taken the time to collect from different authoritative sources. You seem to go for the Humpty Dumpty approach: "When I use a *word

Re: [lock-free] Re: 3-thread consensus.

Dear Manuel, When pointless people loose their arguments, they said that discussion is pointless. ;D I made the most right-to-the-point affirmation I ever made in my entire life: *The only requirement to a algorithm be lock-free is to be O(1).* To me, this affirmation is obvious and self contai

Re: [lock-free] Re: 3-thread consensus.

Progress guarantees have nothing to do with algorithmic complexity! Take Harris' lock-free linked list - the list operations are definitely not O(1), but it is still lock-free. I am not sure if you really don't understand this, or if you are deliberat

Re: [lock-free] Re: 3-thread consensus.

> Your algorithm is lockless (i.e. without lock) but not lock-free according to the definition of lock-freedom. You make me think if my cellphone is wireless or wirefree. :) Thinking carefully about, I got an axiom: An algorithm can be called lock-free if it's O(1). Condition necessary and suff

Re: [lock-free] Re: 3-thread consensus.

The definition of obstruction-free, lock-free or wait-free is not a guarantee of performance, it's a guarantee of progress, in particular when thread can dies (non-blocking algorithm ) In computer science

Re: [lock-free] Re: 3-thread consensus.

> Let me ask first: what is your definition of a lock-free algorithm? When there is no locks/waits between threads/actors. And a lock happens when some thread A cannot proceed while another thread B do not finish its job. But for practical reasons, I believe that the most important feature/chara

[lock-free] Re: 3-thread consensus.

There exists a universally accepted meaning of lock-freedom. You may find various definitions that try to describe or formalize it in different ways, but the essence is always the same. Here are a few definitions from different sources: - An algorithm is lock-free if, when the program thre

Re: [lock-free] Re: 3-thread consensus.

On Tue, Jan 14, 2020 at 4:03 PM wrote: > > Hi Manuel, > > How would a processing line be broken between the CAS and the release of the > seat? > > This will happen only if the S.O. preempt the thread on that point and never > get back. > > This is what I mean with the "my entire system is broken

[lock-free] Re: 3-thread consensus.

Thinking about my own question, I find that an abnormal termination is another possibility, yet in this case, the entire program is finished/dead/broken. Em terça-feira, 14 de janeiro de 2020 13:03:42 UTC-2, bit...@gmail.com escreveu: > > Hi Manuel, > > How would a processing line be broken be

[lock-free] Re: 3-thread consensus.

Hi Manuel, How would a processing line be broken between the CAS and the release of the seat? This will happen *only if* the S.O. preempt the thread on that point and never get back. This is what I mean with the "my entire system is broken" *Only a S.O. scheduling failure can produce that.*

Re: [lock-free] Re: 3-thread consensus.

Hi Brendon, Thanks for the observations. It that point between the CAS and the effective release of the seat, *all other threads are free to take another seat *without restriction. As well in any point of the code. There is no a single point where any thread is blocked from getting a seat.

[lock-free] Re: 3-thread consensus.

The lock-free property guarantees that at any time at least one thread is making progress in a finite number of steps. Or to put this more generally: a stalled thread must not cause all other threads to stall indefinitely. The arguments about lock-freedom (or the lack thereof) are usually based o

Re: [lock-free] Re: 3-thread consensus.

I was interested in your queue so had a look as well. Thanks for sharing it. I find it interesting looking at other implementations. I think Dmitry is correct. See the comment inline below. From my understanding the code locks the consumers waiting on a producer at the point in time where I placed

[lock-free] Re: 3-thread consensus.

> Well, if producer is preempted, consumers are blocked from progressing. Sorry, but this isn't true. The consumers are preempted only in case of a empty queue. Which isn't a lock. Meaning that there is nothing to do. If you don't have active producers, three is nothing to consume. How can you

[lock-free] Re: 3-thread consensus.

+lock-free group again, please don't drop it On Mon, Jan 13, 2020 at 8:19 AM bittnkr wrote: > > If a thread dies at that point, my entire system is broken... Which means it's not lock-free. > But It can preempts without any problem at near zero cost. Well, if producer is preempted, consumers a

[lock-free] Re: 3-thread consensus.

On Sun, Jan 12, 2020 at 7:33 PM bittnkr wrote: > > > > This blocks consumes from progressing (consuming next produced items) > and is effectively a mutex. > > Suppose the thread A got a local copy of tail in t then is preempted, > > another thread will get the same tail an get the seat normally. >

[lock-free] Re: 3-thread consensus.

On Sat, Jan 11, 2020 at 9:26 AM bittnkr wrote: > > Good observations. Thank you. > > If the thread preempts on those points, the seat position will be held on > local variables h and t. This blocks consumes from progressing (consuming next produced items) and is effectively a mutex. This makes a

[lock-free] Re: 3-thread consensus.

On Sat, Jan 11, 2020 at 4:09 AM bittnkr wrote: > > Hello Dmitry and fellows from the group. > > If you look carefully, you will see that there is no blocking, just simple > CAS, even the buffer is a common buffer. But consider you look inside of a spin lock, or you take a spin-lock-based algorit

Re: [lock-free] Re: 3-thread consensus.

Hi bittnkr Beyond Relacy, if you are looking to publish a paper, you might want to specify/run your algorithm in a formal language like Spin or TLA+ . They can't verify correct use of C++11 but you can assert

[lock-free] Re: 3-thread consensus.

On Wed, Jan 8, 2020 at 9:29 PM bittnkr wrote: > > Dear Dmitry, > > I found a nice solution for the problem called 3 thread consensus, considered > impossible on the book The art of the multiprocessor programming. I think > that is a breakthrough. > > Debating on S.O. with someone about if the so