TY - GEN
T1 - Brief Announcement
T2 - 41st ACM Symposium on Principles of Distributed Computing, PODC 2022
AU - Alhaddad, Nicolas
AU - Das, Sourav
AU - Duan, Sisi
AU - Ren, Ling
AU - Varia, Mayank
AU - Xiang, Zhuolun
AU - Zhang, Haibin
N1 - Publisher Copyright:
© 2022 Owner/Author.
PY - 2022/7/20
Y1 - 2022/7/20
N2 - We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is O(|M| + κ n^2), and the retrieval cost per client is O(|M| + κ n). Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of O(|M|+κ n) in comparison to O(|M|+κ n łog n) of prior best. Moreover, each node in our AVID protocol incurs a storage cost of O(|M|/n + κ) bits, in comparison to O(|M|/n + κ łog n) bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs - only a factor of O(κ) gap from the lower bounds.
AB - We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is O(|M| + κ n^2), and the retrieval cost per client is O(|M| + κ n). Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of O(|M|+κ n) in comparison to O(|M|+κ n łog n) of prior best. Moreover, each node in our AVID protocol incurs a storage cost of O(|M|/n + κ) bits, in comparison to O(|M|/n + κ łog n) bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs - only a factor of O(κ) gap from the lower bounds.
KW - asynchronous networks
KW - asynchronous verifiable information dispersal
KW - communication complexity
KW - lower bounds
UR - http://www.scopus.com/inward/record.url?scp=85135302521&partnerID=8YFLogxK
U2 - 10.1145/3519270.3538476
DO - 10.1145/3519270.3538476
M3 - Conference contribution
AN - SCOPUS:85135302521
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 418
EP - 420
BT - PODC 2022 - Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 25 July 2022 through 29 July 2022
ER -