Abstract | ||
---|---|---|
We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.
|
Year | DOI | Venue |
---|---|---|
2019 | 10.1145/3293611.3331573 | Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing |
Keywords | DocType | Volume |
byzantine faults, computational efficiency, information theory, security, state machine execution, verifiable computing | Conference | abs/1906.10817 |
ISBN | Citations | PageRank |
978-1-4503-6217-7 | 0 | 0.34 |
References | Authors | |
0 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Songze Li | 1 | 134 | 16.22 |
Saeid Sahraei | 2 | 15 | 4.28 |
Mingchao Yu | 3 | 15 | 2.70 |
Amir Salman Avestimehr | 4 | 1880 | 157.39 |
Sreeram Kannan | 5 | 120 | 21.76 |
Viswanath, P. | 6 | 1330 | 179.87 |