13 citations · 16 across the 3 of their papers we have counts for
6 papers
Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model
Andrew Lewis-Pye
We consider the message complexity of State Machine Replication protocols dealing with Byzantine failures in the partial synchrony model. A result of Dolev and Reischuk gives a qua…
A General Framework for the Security Analysis of Blockchain Protocols
Andrew Lewis-Pye, Tim Roughgarden
Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish c…
Resource Pools and the CAP Theorem
Andrew Lewis-Pye, Tim Roughgarden
Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish c…
Monotonous betting strategies in warped casinos
George Barmpalias, Nan Fang, Andrew Lewis-Pye
Suppose that the outcomes of a roulette table are not entirely random, in the sense that there exists a successful betting strategy. Is there a successful `separable' strategy, in…
The idemetric property: when most distances are (almost) the same
George Barmpalias, Neng Huang, Andrew Lewis-Pye +4
We introduce the \emph{idemetric} property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard among…
Limits of the Kucera-Gacs coding method
George Barmpalias, Andrew Lewis-Pye
Every real is computable from a Martin-Loef random real. This well known result in algorithmic randomness was proved by Kucera and Gacs. In this survey article we discuss various a…