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). | ||