[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [tlaplus] Several detailed questions about Paxos algorithm



Hi,

The TCP/IP protocol handles message duplication (and also message ordering!) by introducing "sequence numbers". The sequence number is incremented each time a new message is sent by the sender.

TCP/IP is a communication protocol. It provides several useful features (such as avoiding message duplication) for two interacting systems.

When we implement our system based on a communication protocol such as TCP/IP, we are able to forget about the underlying difficulties that the communication protocol has promised to handle. Therefore, we would be living at a certain abstraction level that is made available by the underlying layers!

Message duplication in Paxos algorithm is a case when a single message is delivered to its destination multiple times. Please note that the messages (including the duplicate ones) may be delivered out of order, at any time.

The Paxos algorithm manages to operate in such an unreliable network, and it does so without using an underlying network communication protocol.

By the way, the Paxos algorithm is an extremely general and flexible algorithm. If you are sure that your TCP/IP implementation (for example, provided by an operating system) can definitely handle all message duplicates, then you can try to modify or perhaps simplify the Paxos algorithm assuming that message duplicates are impossible.

I Hope this is helpful.

Regards,
AmirHossein



On Fri, May 31, 2019 at 2:23 PM remuscl <remus.clearwater@xxxxxxxxx> wrote:
I'm sorry if here is not the right place for such question, but I didn't manage to find an online Paxos leaner group.

----

https://en.wikipedia.org/wiki/Paxos_(computer_science)#Network

Q1:

Does it really necessary for Paxos algorithm to handle message duplication when we already have TCP (to avoid such duplication)? If all the RPC (prepare and accept) in a Paxos group is implemented with TCP then such "message duplication" assumption could be removed from Paxos network assumption. Is it correct?

Q2:

To be clear, the meaning of "message duplication" in the Paxos network assumption I understand is like below:

  When proposer1 send one Prepare(e0) request to acceptor1 then acceptor1 may receive two Prepare(e0) requests because the msg duplication problem and the response from acceptor1 to proposer1 could be 4 or even more.

  Proposer1->P(e0)->                                                     Acceptor1

  Proposer1                                         ->P(e0)->P(e0)->Acceptor1

  Proposer1                                    <-Reply1<-Reply0<-Acceptor1

  Proposer1<-Reply1<-Reply0<-Reply1<-Reply0<-        Acceptor1

----

Is my understanding of "msg duplication" in Paxos network assumption is correct?

Thank very much for your patience and help.

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@xxxxxxxxxxxxxxxx.
To post to this group, send email to tlaplus@xxxxxxxxxxxxxxxx.
Visit this group at https://groups.google.com/group/tlaplus.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/f20b80d0-241f-4d49-8bc4-2b5ee53abb86%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@xxxxxxxxxxxxxxxx.
To post to this group, send email to tlaplus@xxxxxxxxxxxxxxxx.
Visit this group at https://groups.google.com/group/tlaplus.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/CAKxfy0saC-%3DsaOOh9Juz68YiN6gJ1v2D-yqE5qbF-Xj%2BpDGKmw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.