Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence. / Wolthusen, Stephen D.

Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection. Springer-Verlag, 2014. p. 263.

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

Published

Standard

Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence. / Wolthusen, Stephen D.

Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection. Springer-Verlag, 2014. p. 263.

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

Harvard

Wolthusen, SD 2014, Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence. in Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection. Springer-Verlag, pp. 263. https://doi.org/???10.1007/978-3-662-45355-1_17

APA

Wolthusen, S. D. (2014). Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence. In Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection (pp. 263). Springer-Verlag. https://doi.org/???10.1007/978-3-662-45355-1_17

Vancouver

Wolthusen SD. Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence. In Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection. Springer-Verlag. 2014. p. 263 https://doi.org/???10.1007/978-3-662-45355-1_17

Author

Wolthusen, Stephen D. / Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence. Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection. Springer-Verlag, 2014. pp. 263

BibTeX

@inproceedings{1d10444ee07b4f089dcea690e58a7bb0,
title = "Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence",
abstract = "Consensus problems are of great interest in distributed systems research, especially in the presence of Byzantine faults. While asynchronous message passing is an interesting network model, Fischer, et al. have shown that deterministic algorithms do not exist even for single faults, requiring the use of randomization as proposed by Ben-Or.While most approaches implicitly assume full connectivity, the case of non-complete graphs is particularly interesting when studying the feasibility and efficiency of consensus problems. This topic has received limited scrutiny despite the fact that non-complete graph structures are ubiquitous in many networks that require low overall latency and reliable signaling (e.g., electrical power networks). One of the core benefits of such an approach is the ability to rely on redundant sensors in large networks for detecting faults and adversarial actions without impacting real-time behavior. It is, therefore, critical to minimize the message complexity in consensus algorithms.This paper studies the existence and efficiency of randomized asynchronous binary Byzantine consensus for graphs in the G(n,d⃗ ) configuration model with a power-law degree sequence. The main contribution is an algorithm that explicitly utilizes the network structure to gain efficiency over a simple randomized algorithm while allowing the identification of possible additional edges in the graph to satisfy redundancy requirements.",
author = "Wolthusen, {Stephen D.}",
year = "2014",
doi = "???10.1007/978-3-662-45355-1_17",
language = "English",
pages = "263",
booktitle = "Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection",
publisher = "Springer-Verlag",

}

RIS

TY - GEN

T1 - Asynchronous Binary Byzantine Consensus over Graphs with Power Law Degree Sequence

AU - Wolthusen, Stephen D.

PY - 2014

Y1 - 2014

N2 - Consensus problems are of great interest in distributed systems research, especially in the presence of Byzantine faults. While asynchronous message passing is an interesting network model, Fischer, et al. have shown that deterministic algorithms do not exist even for single faults, requiring the use of randomization as proposed by Ben-Or.While most approaches implicitly assume full connectivity, the case of non-complete graphs is particularly interesting when studying the feasibility and efficiency of consensus problems. This topic has received limited scrutiny despite the fact that non-complete graph structures are ubiquitous in many networks that require low overall latency and reliable signaling (e.g., electrical power networks). One of the core benefits of such an approach is the ability to rely on redundant sensors in large networks for detecting faults and adversarial actions without impacting real-time behavior. It is, therefore, critical to minimize the message complexity in consensus algorithms.This paper studies the existence and efficiency of randomized asynchronous binary Byzantine consensus for graphs in the G(n,d⃗ ) configuration model with a power-law degree sequence. The main contribution is an algorithm that explicitly utilizes the network structure to gain efficiency over a simple randomized algorithm while allowing the identification of possible additional edges in the graph to satisfy redundancy requirements.

AB - Consensus problems are of great interest in distributed systems research, especially in the presence of Byzantine faults. While asynchronous message passing is an interesting network model, Fischer, et al. have shown that deterministic algorithms do not exist even for single faults, requiring the use of randomization as proposed by Ben-Or.While most approaches implicitly assume full connectivity, the case of non-complete graphs is particularly interesting when studying the feasibility and efficiency of consensus problems. This topic has received limited scrutiny despite the fact that non-complete graph structures are ubiquitous in many networks that require low overall latency and reliable signaling (e.g., electrical power networks). One of the core benefits of such an approach is the ability to rely on redundant sensors in large networks for detecting faults and adversarial actions without impacting real-time behavior. It is, therefore, critical to minimize the message complexity in consensus algorithms.This paper studies the existence and efficiency of randomized asynchronous binary Byzantine consensus for graphs in the G(n,d⃗ ) configuration model with a power-law degree sequence. The main contribution is an algorithm that explicitly utilizes the network structure to gain efficiency over a simple randomized algorithm while allowing the identification of possible additional edges in the graph to satisfy redundancy requirements.

U2 - ???10.1007/978-3-662-45355-1_17

DO - ???10.1007/978-3-662-45355-1_17

M3 - Conference contribution

SP - 263

BT - Proceedings of the 8th Annual IFIP WG 11.10 International Conference on Critical Infrastructure Protection

PB - Springer-Verlag

ER -