The disagreement-detection lower-bound conjecture for multi-value Byzantine agreement
The disagreement-detection lower-bound conjecture for multi-value Byzantine agreement
Let nodes each be assigned an arbitrary initial value of bits. A node detects disagreement if the initial values are not all identical.
Disagreement-detection lower-bound conjecture. If the initial values are not identical, at least one node can detect this only after at least
bits have been communicated.
This auxiliary conjecture is proposed as the basis for the communication lower bound used to argue optimality of the paper's Byzantine agreement algorithm. The supplied text gives no proof or resolution of it.
Sources & referencesView supporting material
Primary source
Guanfeng Liang and Nitin Vaidya, “Complexity of Multi-Value Byzantine Agreement”, arXiv:1006.2422 (2010).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.