Search Results

Documents authored by Meir, Shachar

Document
DOI: 10.4230/LIPIcs.DISC.2025.9
Distributed Download from an External Data Source in Byzantine Majority Settings

Authors: John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We consider the Download problem in the Data Retrieval Model, introduced in DISC'24, where a distributed set of peers, some of which may be Byzantine, seek to learn n bits of data stored at a trustworthy external data source. Each bit of data can be learned by a peer either through a direct and costly query of the source or through other peers that have already learned it; the goal is to design a collaborative protocol that reduces the query complexity defined as the maximum number of bits queried by any honest peer. We begin with a randomized protocol for the Download problem that achieves optimal query complexity, up to a logarithmic factor. For a stronger "dynamic" adversary that can change the set of Byzantine peers from one round to the next, we achieve optimality (within log factors) for both query complexity (in expectation) and time complexity, but with larger messages. In broadcast communication, where all peers (including Byzantine peers) are required to send the same message to all peers, we achieve (up to log factors) an optimal trade-off between query complexity, time complexity, and message size with the dynamic adversary. All of our protocols can tolerate any constant fraction β < 1 of Byzantine peers.
Cite as

John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg. Distributed Download from an External Data Source in Byzantine Majority Settings. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2025.9,
  author =	{Augustine, John and Chatterjee, Soumyottam and King, Valerie and Kumar, Manish and Meir, Shachar and Peleg, David},
  title =	{{Distributed Download from an External Data Source in Byzantine Majority Settings}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.9},
  URN =		{urn:nbn:de:0030-drops-248262},
  doi =		{10.4230/LIPIcs.DISC.2025.9},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Data Retrieval Model, Distributed Download}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.48
Brief Announcement: Distributed Download from an External Data Source in Asynchronous Faulty Settings

Authors: John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as query complexity) while maximizing the resilience parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity. To the best of our knowledge, this is the first work to address the Download problem in asynchronous communication networks.
Cite as

John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg. Brief Announcement: Distributed Download from an External Data Source in Asynchronous Faulty Settings. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 48:1-48:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2025.48,
  author =	{Augustine, John and Chatterjee, Soumyottam and King, Valerie and Kumar, Manish and Meir, Shachar and Peleg, David},
  title =	{{Brief Announcement: Distributed Download from an External Data Source in Asynchronous Faulty Settings}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{48:1--48:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.48},
  URN =		{urn:nbn:de:0030-drops-248646},
  doi =		{10.4230/LIPIcs.DISC.2025.48},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Data Retrieval Model, Distributed Download}
}
Document
DOI: 10.4230/LIPIcs.DISC.2024.3
Byzantine Resilient Distributed Computing on External Data

Authors: John Augustine, Jeffin Biju, Shachar Meir, David Peleg, Srikkanth Ramachandran, and Aishwarya Thiruvengadam

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

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 𝒳 of n bits (n ≫ k), providing every peer in the congested clique read-only access to 𝒳 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 𝒳, 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 𝒳. The second problem of focus, Disjunction, requires nodes to learn if some bit in 𝒳 is set to 1.
Cite as

John Augustine, Jeffin Biju, Shachar Meir, David Peleg, Srikkanth Ramachandran, and Aishwarya Thiruvengadam. Byzantine Resilient Distributed Computing on External Data. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2024.3,
  author =	{Augustine, John and Biju, Jeffin and Meir, Shachar and Peleg, David and Ramachandran, Srikkanth and Thiruvengadam, Aishwarya},
  title =	{{Byzantine Resilient Distributed Computing on External Data}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.3},
  URN =		{urn:nbn:de:0030-drops-212304},
  doi =		{10.4230/LIPIcs.DISC.2024.3},
  annote =	{Keywords: Byzantine Fault Tolerance, Blockchain Oracle, Congested Clique, Data Retrieval Model}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact