### Abstract

This paper proves a necessary and sufficient condition for the existence of iterative, algorithms that achieve approximate Byzantine consensus in arbitrary directed graphs, where each directed edge represents a communication channel between a pair of nodes. The class of iterative algorithms considered in this paper ensures that, after each iteration of the algorithm, the state of each fault-free node remains in the convex hull of the states of the fault-free nodes at the end of the previous iteration. The following convergence requirement is imposed: for any ε > 0, after a sufficiently large number of iterations, the states of the fault-free nodes are guaranteed to be within ε of each other. To the best of our knowledge, tight necessary and sufficient conditions for the existence of such iterative consensus algorithms in synchronous arbitrary point-to-point networks in presence of Byzantine faults, have not been developed previously. The methodology and results presented in this paper can also be extended to asynchronous systems.

Original language | English (US) |
---|---|

Title of host publication | PODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing |

Pages | 365-374 |

Number of pages | 10 |

DOIs | |

State | Published - Aug 20 2012 |

Event | 2012 ACM Symposium on Principles of Distributed Computing, PODC'12 - Madeira, Portugal Duration: Jul 16 2012 → Jul 18 2012 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing |
---|

### Other

Other | 2012 ACM Symposium on Principles of Distributed Computing, PODC'12 |
---|---|

Country | Portugal |

City | Madeira |

Period | 7/16/12 → 7/18/12 |

### Keywords

- byzantine faults
- consensus
- iterative algorithms

### ASJC Scopus subject areas

- Software
- Hardware and Architecture
- Computer Networks and Communications

## Fingerprint Dive into the research topics of 'Iterative approximate byzantine consensus in arbitrary directed graphs'. Together they form a unique fingerprint.

## Cite this

*PODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing*(pp. 365-374). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). https://doi.org/10.1145/2332432.2332505