Brief announcement: Coded state machine - Scaling state machine execution under byzantine faults

Songze Li, Saeid Sahraei, Mingchao Yu, Salman Avestimehr, Sreeram Kannan, Pramod Viswanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationPODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages150-152
Number of pages3
ISBN (Electronic)9781450362177
DOIs
StatePublished - Jul 16 2019
Event38th ACM Symposium on Principles of Distributed Computing, PODC 2019 - Toronto, Canada
Duration: Jul 29 2019Aug 2 2019

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference38th ACM Symposium on Principles of Distributed Computing, PODC 2019
CountryCanada
CityToronto
Period7/29/198/2/19

Fingerprint

Computational efficiency
Throughput

Keywords

  • Byzantine faults
  • Computational efficiency
  • Information theory
  • Security
  • State machine execution
  • Verifiable computing

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Li, S., Sahraei, S., Yu, M., Avestimehr, S., Kannan, S., & Viswanath, P. (2019). Brief announcement: Coded state machine - Scaling state machine execution under byzantine faults. In PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (pp. 150-152). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Association for Computing Machinery. https://doi.org/10.1145/3293611.3331573

Brief announcement : Coded state machine - Scaling state machine execution under byzantine faults. / Li, Songze; Sahraei, Saeid; Yu, Mingchao; Avestimehr, Salman; Kannan, Sreeram; Viswanath, Pramod.

PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2019. p. 150-152 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Li, S, Sahraei, S, Yu, M, Avestimehr, S, Kannan, S & Viswanath, P 2019, Brief announcement: Coded state machine - Scaling state machine execution under byzantine faults. in PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 150-152, 38th ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, Canada, 7/29/19. https://doi.org/10.1145/3293611.3331573
Li S, Sahraei S, Yu M, Avestimehr S, Kannan S, Viswanath P. Brief announcement: Coded state machine - Scaling state machine execution under byzantine faults. In PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery. 2019. p. 150-152. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). https://doi.org/10.1145/3293611.3331573
Li, Songze ; Sahraei, Saeid ; Yu, Mingchao ; Avestimehr, Salman ; Kannan, Sreeram ; Viswanath, Pramod. / Brief announcement : Coded state machine - Scaling state machine execution under byzantine faults. PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2019. pp. 150-152 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).
@inproceedings{bad4d5739ffa462b9de57f3b63505829,
title = "Brief announcement: Coded state machine - Scaling state machine execution under byzantine faults",
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.",
keywords = "Byzantine faults, Computational efficiency, Information theory, Security, State machine execution, Verifiable computing",
author = "Songze Li and Saeid Sahraei and Mingchao Yu and Salman Avestimehr and Sreeram Kannan and Pramod Viswanath",
year = "2019",
month = "7",
day = "16",
doi = "10.1145/3293611.3331573",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
publisher = "Association for Computing Machinery",
pages = "150--152",
booktitle = "PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing",

}

TY - GEN

T1 - Brief announcement

T2 - Coded state machine - Scaling state machine execution under byzantine faults

AU - Li, Songze

AU - Sahraei, Saeid

AU - Yu, Mingchao

AU - Avestimehr, Salman

AU - Kannan, Sreeram

AU - Viswanath, Pramod

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

ER -