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 language | English |
---|---|
Title of host publication | 38th International Symposium on Distributed Computing, DISC 2024 |
Editors | Dan Alistarh |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
ISBN (Electronic) | 9783959773522 |
DOIs | |
Publication status | Published - 24 Oct 2024 |
Event | 38th International Symposium on Distributed Computing, DISC 2024 - Madrid, Spain Duration: 28 Oct 2024 → 1 Nov 2024 |
Publication series
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 319 |
ISSN | 1868-8969 |
Conference
Conference | 38th International Symposium on Distributed Computing, DISC 2024 |
---|---|
Country/Territory | Spain |
City | Madrid |
Period | 28/10/24 → 1/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