2021 · 13 citations · 14 references
ComputingComputer ScienceComputer SystemsDistributed SystemsFault-tolerant ComputingFault-tolerant SystemsFault-tolerant CommunicationNetwork ProtocolsReliable Distributed SystemsReliable System DesignByzantine FaultsCompressionFault-tolerant Distributed AlgorithmsFault-tolerant Distributed SystemsFault-tolerant NetworksLiveness PropertiesLiveness VerificationMessage Compression
This work formalizes the structure and protocols underlying recent distributed systems leveraging block DAGs, which are essentially encoding Lamport's happened-before relations between blocks, as their core network primitives. We then present an embedding of any deterministic Byzantine fault tolerant protocol ℘ to employ a block DAG for interpreting interactions between servers. Our main theorem proves that this embedding maintains all safety and liveness properties of ℘. Technically, our theorem is based on the insight that a block DAG merely acts as an efficient reliable point-to-point channel between instances of ℘ while also using ℘ for efficient message compression.
14
Handbook of applied cryptography
Choice Reviews Online · 1997 · 10.5K citations · Full text
Consensus in the presence of partial synchrony
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer · Journal of the ACM · 1988 · 1.9K citations · Full text