TY - GEN
T1 - Brief announcement
T2 - 38th ACM Symposium on Principles of Distributed Computing, PODC 2019
AU - Li, Songze
AU - Sahraei, Saeid
AU - Yu, Mingchao
AU - Avestimehr, Salman
AU - Kannan, Sreeram
AU - Viswanath, Pramod
N1 - Publisher Copyright:
© 2019 Authors.
PY - 2019/7/16
Y1 - 2019/7/16
N2 - 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.
AB - 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.
KW - Byzantine faults
KW - Computational efficiency
KW - Information theory
KW - Security
KW - State machine execution
KW - Verifiable computing
UR - http://www.scopus.com/inward/record.url?scp=85071040850&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85071040850&partnerID=8YFLogxK
U2 - 10.1145/3293611.3331573
DO - 10.1145/3293611.3331573
M3 - Conference contribution
AN - SCOPUS:85071040850
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 150
EP - 152
BT - PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 29 July 2019 through 2 August 2019
ER -