# What is total order and how can generate and maintain total order among the proposer proposals in paxos?

1) What is total order? Does total order mean the consecutive numbers must be strictly less than "<" or it can less than or equal to "<="?

2) how can generate and maintain total order among the proposers in paxos? Can each proposer generate a pair independently from disjoint sets as (seq_number, ip_address) ? and if we can how can we maintain total order in this case? Also can we not maintain a total order by simply generating a (seq_number) instead of (seq_number, ip_address) by multiple proposers?

• Your question #1 is off-topic here, since it is a maths question. But it's really simple: a total order means that all items can be compared. I.e. there are no items where a is neither equal to nor less than nor greater than b. So, it is an order that is total (i.e. defined on its entire domain). – Jörg W Mittag Nov 10 '16 at 8:25
• Pretty much Every Algorithm question is indeed an applied math question. And if I post this math.stackexchange (people there ask me what context are you talking about? and if tell them paxos they say that is CS Algorithm.) Anyways I meant specifically total order w.r.t to paxos algorithm. Also I am having a hard time following what you said. can you give me an example on what total order means for Integers per say? How can you compare without comparison operators? – user1870400 Nov 10 '16 at 9:03
• But "total order" is not a Paxos concept. It is a maths concept. I don't understand what you mean by "compare without comparison operators". An order is a binary relation that satisfies certain laws. A total order is an order that satisfies the additional law that all items can be pairwise ordered. E.g. the ≤ relation on the integers is a total order, because it satisfies all the laws of being an order, and it is total, i.e. for any two integers, it is true that either a ≤ b or b ≤ a. The "is-a-descendent-of" relation on humans is a partial order; it satisfies all the laws of being an order, … – Jörg W Mittag Nov 10 '16 at 9:23
• … but it is not total. There are pairs of humans (for example you and me, probably), where neither you are a descendant of me, nor am I a descendant of you. – Jörg W Mittag Nov 10 '16 at 9:24
• Your question #2 is definitely an algorithms question, which is definitely on-topic on Computer Science, and probably also on-topic here. Your question #1 is definitely a maths question and is off-topic here. And the fact that you co-mingled it with a second question makes it hard to treat your question fairly: half of it is on-topic, half isn't, and the fact that there's multiple questions makes it both unclear and too broad. – Jörg W Mittag Nov 10 '16 at 9:28

1. What is total order?

A total order is just an ordering (`<=`) which can compare every pair of elements, as Jörg W Mittag said in comments, and as you could easily have discovered by simply searching for the term.

Each proposal is uniquely numbered for a given Proposer

So, numbers are comparable, and we automatically have a total ordering on the proposals from a given Proposer.

Can each proposer generate a pair independently from disjoint sets as (seq_number, ip_address) ?

Yes, obviously, you described how to do that in the question. If each proposer has a unique IP address, each Proposer can generate an independent set of such pairs.

However, we don't automatically have any way to order proposals from different Proposers. They're just not related, and I have no idea which precedes the other: this is identical to Jörg's example of the descendant-of relationship in humans. Currently, this is a partial ordering, because we can only order those parts (of the set of all proposals) which came from the same Proposer.

and if we can how can we maintain total order in this case?

By using the IP address in your comparison. You know it's an integer, right? You can just use the normal tuple ordering.

That is, if you want your ordering to be total, you need some way of deciding whether proposal #37 from Proposer A came before or after proposal #42 from Proposer B.

Also can we not maintain a total order by simply generating a (seq_number) instead of (seq_number, ip_address) by multiple proposers?

Only if you don't care which Proposer an element comes from. Your title asks about maintaining a total order among Proposers, and the body of your question is about maintaining a total order among their proposals. You definitely can't order Proposers by just sequence number, because it's only a property of their proposals.

Note however the linked Wikipedia page (again), suggests you're asking the wrong question: it describes proposals being ordered only by sequence number for most parts of the algorithm.

• wikipedia is probably assuming paxos contains one proposer or it might be illustrating using one proposer. I am more interested in multiple proposers which are proposing different proposal number, values and maintaining a total order between them. Anyways, you response clarifies most of the question. – user1870400 Nov 10 '16 at 10:32
• No, it says things like, "If the proposal's number N is higher than any previous proposal number received from any Proposer by the Acceptor," meaning it's only using the number to decide. (Obviously it still needs to track which Proposer to reply to). – Useless Nov 10 '16 at 10:36

Yes, you can always combine totally ordered things together and have a total order on the combination, by treating them as ordered N tuples (pairs, triples etc).

E.g.

``````class SomeData {
int Age;
int HouseNumber;
}

bool SomeTotalOrder(SomeData lhs, SomeData rhs){
if (lhs.Age > rhs.Age) { return true; }
else if (!(rhs.Age > lhs.Age)) { return lhs.HouseNumber < rhs.HouseNumber; }
return false;
}
``````
• Hi, I just edited my question a little bit because I feel like I couldn't get my message across. I am mainly looking for why we cannot maintain a total order among multiple proposers merely by generating a sequence_number by each individual proposer instead of (seq_number, ip_address) ? – user1870400 Nov 10 '16 at 9:55
• I don't know about paxos, but I imagine that different ip_addresses can have equal sequence_numbers, which is why you need the pair to have a unique value – Caleth Nov 10 '16 at 10:08
• yeah thats what I thought to but I think an understand of paxos is necessary here so my question will be more clear. – user1870400 Nov 10 '16 at 10:09