Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917659057061888 |
|---|---|
| author | Bandarupalli, Akhil Bhat, Adithya Bagchi, Saurabh Kate, Aniket Liu-Zhang, Chen-Da Reiter, Michael K. |
| author_facet | Bandarupalli, Akhil Bhat, Adithya Bagchi, Saurabh Kate, Aniket Liu-Zhang, Chen-Da Reiter, Michael K. |
| contents | Agreement protocols are crucial in various emerging applications, spanning from distributed (blockchains) oracles to fault-tolerant cyber-physical systems. In scenarios where sensor/oracle nodes measure a common source, maintaining output within the convex range of correct inputs, known as convex validity, is imperative. Present asynchronous convex agreement protocols employ either randomization, incurring substantial computation overhead, or approximate agreement techniques, leading to high $\mathcal{\tilde{O}}(n^3)$ communication for an $n$-node system.
This paper introduces Delphi, a deterministic protocol with $\mathcal{\tilde{O}}(n^2)$ communication and minimal computation overhead. Delphi assumes that honest inputs are bounded, except with negligible probability, and integrates agreement primitives from literature with a novel weighted averaging technique. Experimental results highlight Delphi's superior performance, showcasing a significantly lower latency compared to state-of-the-art protocols. Specifically, for an $n=160$-node system, Delphi achieves an 8x and 3x improvement in latency within CPS and AWS environments, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_02431 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles Bandarupalli, Akhil Bhat, Adithya Bagchi, Saurabh Kate, Aniket Liu-Zhang, Chen-Da Reiter, Michael K. Distributed, Parallel, and Cluster Computing Cryptography and Security Agreement protocols are crucial in various emerging applications, spanning from distributed (blockchains) oracles to fault-tolerant cyber-physical systems. In scenarios where sensor/oracle nodes measure a common source, maintaining output within the convex range of correct inputs, known as convex validity, is imperative. Present asynchronous convex agreement protocols employ either randomization, incurring substantial computation overhead, or approximate agreement techniques, leading to high $\mathcal{\tilde{O}}(n^3)$ communication for an $n$-node system. This paper introduces Delphi, a deterministic protocol with $\mathcal{\tilde{O}}(n^2)$ communication and minimal computation overhead. Delphi assumes that honest inputs are bounded, except with negligible probability, and integrates agreement primitives from literature with a novel weighted averaging technique. Experimental results highlight Delphi's superior performance, showcasing a significantly lower latency compared to state-of-the-art protocols. Specifically, for an $n=160$-node system, Delphi achieves an 8x and 3x improvement in latency within CPS and AWS environments, respectively. |
| title | Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles |
| topic | Distributed, Parallel, and Cluster Computing Cryptography and Security |
| url | https://arxiv.org/abs/2405.02431 |