Keynote: Resilient Distributed Computing on External Data
摘要
Distributed computing via message passing [6] has blossomed over the years, thanks in large part to the anchoring provided by the LOCAL model, the CONGEST model, and other related models like the congested clique, and the massively parallel computation model. Alongside, we have also seen the development of fault tolerant and Byzantine resilient models of computing [5]. In all of these models, the data is assumed to be within the network with each node holding a portion of the data. Consequently, the study of fault tolerance is somewhat stifled [4] because the data contained within the faulty nodes are lost at best (under crash failures) or maliciously misrepresented at worst (under Byzantine failures). We explore several real-world contexts where the data is, in fact, external to the network and accessible to all nodes through queries and API calls – often at a cost that must be optimized. Inspired by these contexts, we will present a recent Byzantine resilient distributed computing model on external data [1]. We will then focus on the download problem that requires all good nodes in the network to optimally learn all the external data (represented as an array of n bits that can be individually queried) through careful collaboration despite \(\beta \) fraction (out of the k nodes) being Byzantine. The download problem is fundamental because all other conceivable problems can be solved locally after the download. It is easy to see that n/k is a lower bound for the average number of queries per node even when the fraction of Byzantine nodes \(\beta \) is 0. Somewhat surprisingly, we will see that the download problem can be solved in the synchronous setting with at most a \(\text {polylog}(n)\) factor overhead for any fixed \(\beta < 1\) [2, 3]. We will end with some discussion on what might be interesting directions that can be explored further.