Byzantine Resilient Distributed Computing on External Data

John Augustine*, Jeffin Biju*, Shachar Meir*, David Peleg*, Srikkanth Ramachandran*, Aishwarya Thiruvengadam*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We study a class of problems we call retrieval problems in which a distributed network has read-only access to a trusted external data source through queries, and each peer is required to output some computable function of the data. To formalize this, we propose the Data Retrieval Model comprising two parts: (1) a congested clique network with k peers, up to βk of which can be Byzantine in every execution (for suitable values of β ∈ [0, 1)); (2) a trusted source of data with no computational abilities, called the External Data Source (or just source for short). This source stores an array X of n bits (n ≫ k), providing every peer in the congested clique read-only access to X through queries. It is assumed that a query to the source is significantly more expensive than a message between two peers in the network. Hence, we prioritize minimizing the number of queries a peer performs over the number of messages it sends. Retrieval problems are easily solved by having each peer query all of X, so we focus on designing non-trivial query-efficient protocols for retrieval problems in the DR network that achieve low query performance per peer. Specifically, to initiate this study, we present deterministic and randomized upper and lower bounds for two fundamental problems. The first is the Download problem that requires every peer to output an array of n bits identical to X. The second problem of focus, Disjunction, requires nodes to learn if some bit in X is set to 1.

Original languageEnglish
Title of host publication38th International Symposium on Distributed Computing, DISC 2024
EditorsDan Alistarh
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773522
DOIs
Publication statusPublished - 24 Oct 2024
Event38th International Symposium on Distributed Computing, DISC 2024 - Madrid, Spain
Duration: 28 Oct 20241 Nov 2024

Publication series

SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume319
ISSN1868-8969

Conference

Conference38th International Symposium on Distributed Computing, DISC 2024
Country/TerritorySpain
CityMadrid
Period28/10/241/11/24

Funding

John Augustine: Supported by the Cybersecurity Centre, IIT Madras. We would like to thank Atharva Chougule for useful ideas.

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Byzantine Resilient Distributed Computing on External Data'. Together they form a unique fingerprint.

Cite this