Distributed Download from an External Data Source in Asynchronous Faulty Settings

The Data Retrieval Model (DR) was first introduced in [3] to abstract the fundamental process of a group learning from a reliable external data source, where the data source is too large or it is too expensive to be learned individually (i.e., requires members of the group to collaborate), and some members of the group might crash during execution or act in other ways to deliberately sabotage the learning process. One key example of systems where this process takes place is blockchain oracles [12, 16]. We address this Oracle data delivery process in detail later and present a method for improving its performance using the DR model and the protocols designed in this work.

The DR model contains two entities: (i) a peer-to-peer network and (ii) an external data source in the form of an $n$ bit array X. There are $k$ peers, up to $\beta$ fraction of which may be faulty (and at least $\gamma =1-\beta$ fraction of which are nonfaulty). Each peer has access to the content of the array through queries. The general class of retrieval problems consists of problems $\text{Retrieve}(f)$ requiring every peer to output $f(\text{X})$ for some computable function $f$ of the input array X. In this work, we focus on the most fundamental retrieval problem, $\text{Retrieve}(f_{id})$ where $f_{id}(\text{X})=\text{X}$, referred to hereafter as the Download problem¹¹1It is fundamental since every retrieval problem $\text{Retrieve}(f)$ can be solved by first performing download and then locally computing $f(\text{X})$., where every peer needs to learn the entire input X.

In the absence of failures, the problem can be easily solved in a query-balanced manner. Even with failures, the problem can be trivially solved at the cost of a large number of queries, as the non-faulty peers can directly query all the bits. This solution is prohibitively expensive; thus, we focus on minimizing the number of queries made by each non-faulty peer. For synchronous systems with Byzantine faults, a lower bound of $\mathrm{\Omega }(\beta n)$ on query complexity for deterministic Download is shown in [3] for every , followed by a matching upper bound when . This implies that in the presence of Byzantine faults, one cannot attain the ideal query complexity of $\frac{n}{\gamma k}$ without using randomization.

In this work, we consider Download protocols in the asynchronous setting for both the crash and Byzantine fault models. In the asynchronous Byzantine fault setting, we prove that, unlike the synchronous setting, where randomization can overcome the deterministic lower bound, $\mathrm{\Omega }(n)$ queries per peer are required when $\beta \ge 1/2$, even for randomized protocols. We complement this lower bound with a protocol for the regime that achieves a query complexity of $\tilde{O}\left(\frac{n}{(\gamma -\beta )k}\right)$, which, for a constant $\gamma -\beta$ , is within log factors of the generic lower bound of $\mathrm{\Omega }(n/\gamma k)$.

Turning to the more benign setting of crash faults (i.e., where all peers are honest but some $\beta$ fraction may stop functioning), the picture is brighter. For this model, it turns out that even in the asynchronous setting, one can get efficient deterministic Download protocols that achieve the optimal query complexity of $O\left(\frac{n}{\gamma k}\right)$, for any fraction of crashes.

In the Data Retrieval (DR) model, the system consists of two components. The first is a collection of $k$ peers, each equipped with a unique ID from the range $[1,k]$, connected by a complete communication network (or clique). The network provides peer-to-peer message passing, namely, every peer can send at time $t$ a (possibly different) message of size at most $\varphi$ bits to each other peer.

The second component of the DR model is an external data source. The source stores an $n$-bit input array $\text{X}=\{b_1,\mathrm{\dots },b_n\}$. It provides the peers with read-only access, allowing each peer to retrieve the data through queries of the form $\text{Query}(i)$, for $1\le i\le n$. The answer returned by the source would then be $b_i$, the $i^{th}$ element in the array. This type of communication is referred to as source-to-peer communication.

We consider asynchronous communication, where any communication (both among peer-to-peer and source-to-peer) can be delayed by any finite amount of time. For randomized protocols, we use the following notion of cycles.

The vast literature on fault-tolerant distributed computing includes extensive work on both crash faults and Byzantine faults. A foundational result by Fischer, Lynch, and Paterson (FLP)[20] demonstrated that in asynchronous networks, even a single crash fault renders many fundamental problems – such as consensus and reliable broadcast – impossible to solve deterministically. Specifically, they showed that the adversary can indefinitely delay progress, violating the termination property. To circumvent this impossibility, many subsequent works in asynchronous settings have adopted randomized techniques[7, 22] or relaxed the termination requirement [9].

Given the practical relevance of the asynchronous model, it has been widely adopted for studying fault-tolerant protocols under crash faults [19, 24, 17, 6] and Byzantine faults [1, 8, 10, 13, 14, 15, 18, 21, 23, 28]. Fundamental problems such as agreement and reliable broadcast have often served as building blocks in distributed protocol design, typically assuming that all input data is already locally available to the peers.

In contrast, our work addresses the Data Retrieval (DR) model, where each peer must actively fetch data from a trusted external source and disseminate it to the rest of the peers while minimizing the cost associated with querying the source. We focus on the Download problem, which requires every nonfaulty peer to correctly learn the entire data. Unlike classical problems, we show that Download – despite requiring termination – can be solved deterministically in asynchronous networks. This highlights that employing reliable broadcast or agreement as foundational components is not necessary to solve the Download problem. Moreover, this can be done with optimal query complexity for any fraction of crash-faults. In the more adversarial Byzantine setting, we also design randomized protocols that solve the problem even when a majority of the peers are Byzantine.

To the best of our knowledge, this work is the first to study retrieval problems in the Data Retrieval (DR) model under asynchronous communication. The DR model has previously been explored in synchronous networks, most notably in [3, 5]. In particular,[3] introduced the Download problem, motivated by practical applications such as Distributed Oracle Networks (DONs), which form a crucial component of blockchain systems and employ protocols like OCR and DORA[12, 16].

The primary focus of [3] was on minimizing query complexity in the presence of Byzantine faults in synchronous settings. They proved that any deterministic protocol must incur a query complexity of at least $𝒬=\mathrm{\Omega }(\beta n)$ and matched this with an upper bound when . On the randomized front, they proposed two protocols. The first tolerates any constant fraction of Byzantine faults but has suboptimal query complexity, achieving $𝒬=O\left(\frac{n}{\gamma k}+\sqrt{n}\right)$ with high probability. The second protocol improves upon this by achieving near-optimal query complexity $\tilde{O}\left(\frac{n}{\gamma k}\right)$³³3We use the $\tilde{O}(\cdot )$ notation to hide $\beta$ factors and polylogarithmic terms in $n$ and $k$. with high probability, but it can only tolerate up to a fraction of Byzantine faults.

The paper [5] builds upon the foundational work in [3] by closing several gaps in the randomized setting. It presents a randomized Download protocol with query complexity $𝒬=O\left(\frac{n}{\gamma k}\right)$, time complexity $𝒯=O(n\log k)$, and message complexity $ℳ=O(n{k}^2)$ for any Byzantine-fault fraction $\beta \in [0,1)$. Additionally, it establishes a lower bound showing that in any single-round randomized protocol, each peer must essentially query the entire input, indicating the inherent limitations of extremely fast protocols.

Moving to two-round protocols, [5] proposes a randomized solution that achieves query complexity $𝒬=O\left(\frac{n}{\gamma k}+\sqrt{n}\right)$ with high probability, improving upon the time complexity of [3] under the same fault threshold . Notably, this protocol operates under a stronger adversarial model – referred to as Dynamic Byzantine – in which the set of Byzantine peers may change from one round to another. Under this dynamic fault model, the authors further develop a protocol that achieves expected query complexity $\tilde{O}\left(\frac{n}{\gamma k}\right)$ (within logarithmic factors), at the expense of a higher time complexity of $O(\log k)$.

In contrast to prior work, this paper explores the Download problem in asynchronous networks, under both crash and Byzantine faults. Our results are summarized in the next section; a concise comparison to prior synchronous protocols is provided in Table 1.

We present the Download problem in asynchronous communication networks, under both crash and Byzantine failures settings. In the crash-fault setting, our deterministic results are optimal w.r.t. to the resilience (for any ) and query complexity. Notice that this optimality also holds for randomized algorithms. In the Byzantine failure setting, we provide deterministic and randomized lower bounds as well as upper bounds. The main results are:

1. (1)

   Deterministic Download in Crash-Fault: We present a deterministic protocol for solving Download problem in the asynchronous setting with at most crash faults ($\gamma =1-f/k$) with $𝒬=\mathrm{\Theta }(\frac{n}{\gamma k})$, $𝒯=O\left(\frac{n}{\varphi }+{\log }_{k/f}(\varphi )\right)$ and $ℳ=O(n{k}^2)$ where $\varphi$ is the message size. Our result achieves the optimal query complexity for any fraction of crash fault, .

2. (2)

   Deterministic Lower Bound in Byzantine Fault: We show that for $\beta \ge 1/2$, every deterministic asynchronous Download protocol that is resilient to Byzantine faults requires $𝒬=n$.

3. (3)

   Deterministic Download in Byzantine Fault: We show that for , there exists a deterministic asynchronous protocol that solves Download with $Q=O(\beta n)$, $𝒯=O\left(\frac{\beta n}{\varphi }\right)$ and $ℳ=O(f\cdot n)$.

4. (4)

   Randomized Lower Bound in Byzantine Fault: We show that for any randomized asynchronous Download protocol where $\beta \ge 1/2$, there does not exist any execution in which every peer queries less than or equal $n/2$ bits.

5. (5)

   2-cycle Randomized Download in Byzantine Fault: We present a 2-cycle asynchronous randomized protocol for Download with $𝒬=O\left(\sqrt{\frac{n}{\gamma -\beta }}+\frac{n\log n}{(\gamma -\beta )k}\right)$ and $ℳ=O(k^2)$ where $\beta \le 1/2$, and the message size is $\varphi =O(\frac{n}{\gamma k})$.

6. (6)

   Randomized Download in Byzantine Fault: We present a $O\left(\log \left(\frac{\gamma k}{\ln n}\right)\right)$-cycle protocol that computes Download whp in the point-to-point model having expected query complexity $𝒬=O\left(\frac{n\log n}{(\gamma -\beta )k}\right)$ and $ℳ=O\left(\log \left(\frac{\gamma k}{\ln n}\right)k^2\right)$ where $\beta \le 1/2$, and the message size is $\varphi =O(n)$.

In this subsection, we present a protocol that can tolerate up to $f$ crashes for any (for a more basic algorithm for the case of $f=1$ see [4]). The main difficulty in achieving tolerance with up to $f$ crashes is that in the presence of asynchrony, one cannot distinguish between a slow peer and a crashed peer, making it difficult to coordinate.

Algorithm 1 executes in phases, each consisting of three stages. Each peer $\mu$ stores the following local variables. (We omit the superscript $\mu$ when it is clear from the context.)

• $\mathrm{■}$

  $phase(\mu )$: $\mu$’s current phase.

• $\mathrm{■}$

  $stage(\mu )$: $\mu$’s current stage within the phase.

• $\mathrm{■}$

  $H_p^{\mu }$: the correct set of $\mu$ for phase $p$, i.e., the set of peers $\mu$ heard from during phase $p$.

• $\mathrm{■}$

  ${\sigma }_p^{\mu }$: the assignment function of $\mu$ for phase $p$, which assigns the responsibility for querying each bit $i$ to some peer ${\mu }^{\prime }$.

• $\mathrm{■}$

  $re{s}^{\mu }$: the output array.

In the first stage of phase $p$, each peer $\mu$ queries bits according to its local assignment ${\sigma }_p$ and sends a $\mathrm{𝚙𝚑𝚊𝚜𝚎}p\mathrm{𝚜𝚝𝚊𝚐𝚎}1$ request (asking for bit values according to ${\sigma }_p$, namely $\{i\mid {\sigma }_p(i)={\mu }^{\prime }\}$) to every other peer ${\mu }^{\prime }$ and then continues to stage 2. Upon receiving a $\mathrm{𝚙𝚑𝚊𝚜𝚎}p\mathrm{𝚜𝚝𝚊𝚐𝚎}1$ request, $\mu$ waits until it is at least in stage 2 of phase $p$ and returns the requested bit values that it knows.

In stage 2 of phase $p$, $\mu$ waits until it hears from at least $|H_p^{\mu }|\ge k-f$ peers (again, waiting for the remaining $f$ peers risks deadlock). Then, it sends a $\mathrm{𝚙𝚑𝚊𝚜𝚎}p\mathrm{𝚜𝚝𝚊𝚐𝚎}2$ request containing the set of peers’ IDs $F_p^{\mu }=\{1,\mathrm{\dots },k\}\setminus H_p^{\mu }$ (namely, all the peers it didn’t hear from during phase $p$) and continues to stage 3. Upon receiving a $\mathrm{𝚙𝚑𝚊𝚜𝚎}p\mathrm{𝚜𝚝𝚊𝚐𝚎}2$ request, $\mu$ waits until it is at least in stage 3 of phase $p$, and replies to every peer ${\mu }^{\prime }$ as follows. For every $j\in F_p^{{\mu }^{\prime }}$, it sends ${\mu }_j$’s bits if $j\in H_p^{{\mu }^{\prime }}$ and “me neither” otherwise.

In stage 3 of phase $p$, $\mu$ waits for $k-f$ $\mathrm{𝚙𝚑𝚊𝚜𝚎}p\mathrm{𝚜𝚝𝚊𝚐𝚎}2$ responses. Then, for every $j\in F_p^{\mu }$, if it received only “me neither” messages, it reassigns ${\mu }_j$’s bits evenly between peers $1,\mathrm{\dots },k$. Otherwise, it updates $res$ in the appropriate indices. Finally, it continues to stage 1 of phase $p+1$. Upon receiving a $\mathrm{𝚙𝚑𝚊𝚜𝚎}p\mathrm{𝚜𝚝𝚊𝚐𝚎}i$ response, $\mu$ updates $res$ in the appropriate index and updates $H_p$ for every bit value in the message. The pseudocode is provided in Algorithm 1.

Before diving into the analysis, we overview the following intuitive flow of the protocol’s execution. At the beginning of phase 1, the assignment function ${\sigma }_1$ is the same for every peer. Every peer is assigned $n/k$ bits, which it queries and sends to every other peer. Every peer $\mu$ hears from at least $k-f$ peers, meaning that it has at most $f\cdot n/k$ unknown bits after phase 1. In the following phases, every peer $\mu$ reassigns its unknown bits uniformly among all the peers, such that the bits assigned to every peer ${\mu }^{\prime }$ are either known to it from a previous phase or ${\mu }^{\prime }$ is about to query them in the current phase (i.e., ${\mu }^{\prime }$ assigned itself the same bits). Hence, after every phase, the number of unknown bits diminishes by a factor of $f/k$. After sufficiently many phases, the number of unknown bits will be small enough to be directly queried by every peer.

We start the analysis by showing some properties of the relations between local variables.

When $\beta \ge 1/2$, any asynchronous Download protocol that is resilient to Byzantine faults requires $𝒬=\mathrm{\Omega }(n)$. Moreover, any deterministic asynchronous Download protocol resilient to Byzantine faults requires $𝒬=n$, namely, the only such protocol is the naive one.

We defer the proof to [4] since we next establish a similar result for randomized protocols (with a slightly weaker bound of $n/2$ instead of $n$).

One subtle point that makes the randomized lower bound more complicated has to do with the limitations imposed on the adversary due to the fact that honest peers are aware of the minimal number of honest peers in every execution, and are therefore entitled to wait for these many messages. This point deserves further scrutiny. In the asynchronous model, each peer operates in an event-driven mode. This means that its typical cycle consists of (a) performing some local computation, (b) sending some messages, and then (c) entering a waiting period, until “something happens.” Typically, this “something” is the arrival of a new message. However, the algorithm may instruct the peer $\mu$ to continue waiting until it receives new messages from $k-f-1$ distinct peers. Since it is guaranteed that at least this many honest peers exist in the execution, this instruction is legitimate (in the sense that it cannot cause the peer to deadlock). Moreover, in case $\mu$ has already identified and “blacklisted” a set $F^{\prime }$ of peers as failed peers, it is entitled to wait until it receives new messages from $k-f-1$ distinct peers in $V\setminus F^{\prime }$. This observation restricts the ability of the adversary to delay messages sent by honest peers indefinitely. In particular, at some point during the execution, it may happen that all honest peers are waiting for new messages from other honest peers and will not take any additional actions until they do. In such a situation, sometimes referred to in the literature as reaching quiescence, the adversary may not continue delaying messages indefinitely and is compelled to “release” some of the delayed messages and let them reach their destination. Throughout, we assume that the adversary abides by this restriction.

For , we consider an input vector X that is divided into $𝒦=\lceil n/\phi \rceil$ contiguous segments, each of length approximately $\phi$. The $\mathrm{\ell }$th segment is denoted by $\text{X}[\mathrm{\ell },\phi ]$. Peers issue queries for specific segments and obtain the corresponding bit strings as responses. These responses are then broadcast to all other peers in the form of messages $⟨\mathrm{\ell },s⟩$, where $\mathrm{\ell }$ denotes the segment index and $s$ the returned bit string. Two messages are said to be overlapping if they refer to the same segment and consistent if, in addition, they carry identical bit strings. A set of consistent responses from at least $t$ peers is referred to as a $t$-frequent string, denoted by the function $\text{FS}(MS,t)$ applied to a multiset $MS$ of overlapping responses.

To handle inconsistencies caused by Byzantine peers, we employ a decision-tree construction for each set $S$ of overlapping responses corresponding to a particular segment. If $S$ contains only one candidate, the tree consists of a single leaf labeled by that bit string. Otherwise, two non-consistent bit strings $s,s^{\prime }\in S$ are chosen, and the first index at which they differ is identified as a separating index. An internal node is created at this index, and the set $S$ is split into two subsets according to the value of the separating bit. The process is applied recursively until the leaves correspond to distinct candidate bit strings. By querying X at the separating indices, inconsistencies can be resolved, and the correct bit string is determined as long as it appears among the leaves of the decision tree.

Next, the input is first partitioned into $𝒦$ segments, and each peer $\mu$ independently selects one segment uniformly at random, queries it, and broadcasts the result to all other peers. Subsequently, each peer constructs decision trees for every segment using the overlapping responses it received. A segment $\mathrm{\ell }$ is determined by forming a decision tree from the responses that appeared at least $t=\frac{(\gamma -\beta )k}{2𝒦}$ times, ensuring that the correct bit string for each segment is eventually recovered. From the above discussion, we have the following results (due to space constraints, details are deferred to [4].

To extend the above protocol ($2$-cycle) into a multi-cycle protocol that improves the expected query complexity. The first cycle matches the first cycle of the $2$-cycle protocol, but in each later cycle $i>1$, the input is divided into ${𝒦}_i=\frac{n}{2^i\phi }$ segments of size ${\phi }_i=2^i\cdot \phi$. Each $i$-segment consists of two $(i-1)$-segments. Every peer $\mu$ selects an $i$-segment uniformly at random, reconstructs its value from decision trees built in the previous cycle, and then broadcasts the result. Since segment size doubles each cycle, after $O(\log 𝒦)$ cycles, each peer has the entire input and outputs correctly, therefore, leading to the following results (details are deferred to [4].

We now present a deterministic asynchronous Download protocol for Byzantine faults where . Consider the deterministic synchronous protocol presented in [3], where a committee $C_i$ of size $2f+1$ is formed for every $i\in [1,n]$, and every peer $\mu \in C_i$ queries the bit $\text{X}[i]$ and broadcasts the message $(\mu ,\text{X}[i]=b_i)$ to all other peers. In order to adapt that protocol to the asynchronous model, we modify the final part of the protocol, requiring each non-committee peer $\mu \notin C_i$ to wait until it gets messages $({\mu }^{\prime },\text{X}[i]=b)$ with identical value $b$ from at least $f+1$ peers ${\mu }^{\prime }$, and then decide $re{s}^{\mu }[i]\leftarrow b$. We get the following result (see [4]).