Parsec/ABA: How do you map ORDERING to binary agreement instances (or other nonbinary value)?

1

Hi all @pierrechevalier83 @anon86652309 @mav @dirvine ,

This problem is slightly external to the Parsec algorithm as such so I’ll make a separate thread of it:

I have a question in Parsec’s problem domain for you: So ABA and therefore Parsec, solves the binary agreement (/consensus) problem, right.

In order to ask non-binary questions, such as “which do you want of apple, pear or orange”, you need to have an algorithm that maps it to binary values.

Here I could see two options:

One option is, run one binary agreement for each option. So one YES/NO vote for apple, one YES/NO vote for pear and one YES/NO vote for orange. This would mean THREE binary agreement instances for the consensus.

Another option would be, map each option to a binary value - in this case apple is 01b, pear is 10b and orange is 11b. This would mean TWO binary agreement instances for the consensus.

From a security perspective I guess these two approaches are equivalent, as byzantine nodes not can disturb the binary agreement in either case. Maybe some kind of cosmetic reason would make either preferable over the other??

Which approach would you prefer, or would you look into doing this some totally other way?

Thanks!!
Guy

2

Actually I must kind of supplement my own question, immediately:

So normally actually what you use the binary agreement for, is the ORDERING question.

So then the question becomes, how do you translate the ORDERING problem, into a set of binary agreement instances.

How does Parsec do this, how do you do this?

Paper references would be much appreciated! Like @pierrechevalier83 you mention that there are other papers that provide necessary background to ABA - which are they, which are the must reads?

Thanks!

3

The way I would resolve the problem you give us to divide in it into two sequential binary decisions, for example:

  1. Apple v Pear/Orange?
    If choice was Apple, that’s it, otherwise:
  2. Pear v Orange?
2 Likes