Brief Announcement: Distributed Download from an External Data Source in Byzantine Majority Settings

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 (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 maximum number of bits queried by any one peer ("query complexity"). We achieve optimal query complexity in a synchronous fully connected network with resilience to any constant fraction β < 1 of Byzantine peers, under varying assumptions regarding time and message size.