Fast Quantum Byzantine Agreement: Difference between revisions

Jump to navigation Jump to search
Line 49: Line 49:


==Properties==
==Properties==
The protocol-
The protocol
* solves the problem in <math>O(1)</math> expected number of rounds, in particular independent of <math>n</math> and <math>t</math>, whereas classically a lower bound of <math>\Omega(\sqrt{n / \log(n)})</math> is known [[Quantum Byzantine Agreement#References|(3), (6)]];
* solves the problem in <math>O(1)</math> expected number of rounds, in particular independent of <math>n</math> and <math>t</math>, whereas classically a lower bound of <math>\Omega\left(\sqrt{n / \log(n)}\right)</math> is known [[Quantum Byzantine Agreement#References|(3), (6)]];
* tolerates <math>t \leq n/3</math> (synchronous) or <math>t \leq n/4</math> (asynchronous) Byzantine failures;
* tolerates <math>t \leq n/3</math> (synchronous) or <math>t \leq n/4</math> (asynchronous) Byzantine failures;
* reaches ''agreement'' (each player outputs the same bit) under the ''validity'' condition (the agreement value was proposed by at least one player) and is guaranteed to ''terminate eventually'' (infinite executions occur almost never - i.e. have probability measure zero).
* reaches ''agreement'' (each player outputs the same bit) under the ''validity'' condition (the agreement value was proposed by at least one player) and is guaranteed to ''terminate eventually'' (infinite executions occur almost never - i.e. have probability measure zero).
Write
262

edits

Navigation menu