20 citations · 56 across the 31 of their papers we have counts for
20 papers · 1 filter
Multimmit: Extending Blocks for Faster Finality
Andrew Lewis-Pye, Patrick O'Grady
To meet the throughput demands of modern blockchain systems, protocols for State Machine Replication (SMR) increasingly have many processors disseminate blocks of transactions in p…
Volition-Guarded Multiagent Atomic Transactions: Describing People and their Machines
Andy Lewis-Pye, Ehud Shapiro
Formal models for concurrent and distributed systems describe machines; the people who operate them are either ignored or treated as external environment. Yet, key distributed syst…
The Carnot Bound: Limits and Possibilities for Bandwidth-Efficient Consensus
Andrew Lewis-Pye, Patrick O'Grady
In leader-based State Machine Replication (SMR), the leader's outgoing bandwidth is a natural throughput bottleneck. Erasure coding can alleviate this by letting the leader send ea…
Reaching Univalency with Subquadratic Communication
Andrew Lewis-Pye
The Dolev-Reischuk lower bound establishes that any deterministic Byzantine Agreement (BA) protocol for processors tolerating faults requires messages. But what…
Minimmit: Fast Finality with Even Faster Blocks
Brendan Kobayashi Chou, Andrew Lewis-Pye, Patrick O'Grady
Achieving low-latency consensus in geographically distributed systems remains a key challenge for blockchain and distributed database applications. To this end, there has been sign…
Frosty for partial synchrony
Stephen Buttolph, Andrew Lewis-Pye, Kevin Sekniqi
Snowman is the consensus protocol used by blockchains on Avalanche. Recent work has shown both how to augment Snowman with a `liveness' module called `Frosty' that protects against…
Constitutional Consensus for Democratic Governance
Idit Keidar, Andrew Lewis-Pye, Ehud Shapiro +1
Permissionless-consensus-based Decentralised Autonomous Organisations (DAOs) are the prevailing paradigm for participant-governed digital organisations. As participants have verifi…
Morpheus Consensus: Excelling on trails and autobahns
Andrew Lewis-Pye, Ehud Shapiro
Recent research in consensus has often focussed on protocols for State-Machine-Replication (SMR) that can handle high throughputs. Such state-of-the-art protocols (generally DAG-ba…
Snowman for partial synchrony
Aaron Buchwald, Stephen Buttolph, Andrew Lewis-Pye +1
Snowman is the consensus protocol run by blockchains on Avalanche. Recent work established a rigorous proof of probabilistic consistency for Snowman in the \emph{synchronous} setti…
Beyond Optimal Fault Tolerance
Andrew Lewis-Pye, Tim Roughgarden
The optimal fault-tolerance achievable by any protocol has been characterized in a wide range of settings. For example, for state machine replication (SMR) protocols operating in t…
The Economic Limits of Permissionless Consensus
Eric Budish, Andrew Lewis-Pye, Tim Roughgarden
The purpose of a consensus protocol is to keep a distributed network of nodes "in sync," even in the presence of an unpredictable communication network and adversarial behavior by…
Frosty: Bringing strong liveness guarantees to the Snow family of consensus protocols
Aaron Buchwald, Stephen Buttolph, Andrew Lewis-Pye +2
Snowman is the consensus protocol implemented by the Avalanche blockchain and is part of the Snow family of protocols, first introduced through the original Avalanche leaderless co…
Lumiere: Making Optimal BFT for Partial Synchrony Practical
Andrew Lewis-Pye, Dahlia Malkhi, Oded Naor +1
The view synchronization problem lies at the heart of many Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) protocols in the partial synchrony model, since these prot…
Flash: An Asynchronous Payment System with Good-Case Linear Communication Complexity
Andrew Lewis-Pye, Oded Naor, Ehud Shapiro
While the original purpose of blockchains was to realize a payment system, it has been shown that, in fact, such systems do not require consensus and can be implemented determinist…
Permissionless Consensus
Andrew Lewis-Pye, Tim Roughgarden
Blockchain protocols typically aspire to run in the permissionless setting, in which nodes are owned and operated by a large number of diverse and unknown entities, with each node…
Fever: Optimal Responsive View Synchronisation
Andrew Lewis-Pye, Ittai Abraham
View synchronisation is an important component of many modern Byzantine Fault Tolerant State Machine Replication (SMR) systems in the partial synchrony model. Roughly, the efficien…
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…
Byzantine Generals in the Permissionless Setting
Andrew Lewis-Pye, Tim Roughgarden
Consensus protocols have traditionally been studied in a setting where all participants are known to each other from the start of the protocol execution. In the parlance of the 'bl…
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…