More Like this

1. Distributed Data Persistency

   https://doi.org/10.1145/3466752.3480060  

   Kokolis, Apostolos ; Psistakis, Antonis ; Reidys, Benjamin ; Huang, Jian ; Torrellas, Josep ( October 2021 , MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture)

   null (Ed.)
2. Distributed Partial Clustering

   https://doi.org/10.1145/3322808  

   Guha, Sudipto ; Li, Yi ; Zhang, Qin ( December 2019 , ACM Transactions on Parallel Computing)
3. Distributed Partial Clustering

   https://doi.org/10.1145/3087556.3087568  

   Guha, Sudipto ; Li, Yi ; Zhang, Qin ( July 2017 , The 29th ACM Symposium on Parallelism in Algorithms and Architectures)

   Recent years have witnessed an increasing popularity of algorithm design for distributed data, largely due to the fact that massive datasets are often collected and stored in different locations. In the distributed setting communication typically dominates the query processing time. Thus it becomes crucial to design communication efficient algorithms for queries on distributed data. Simultaneously, it has been widely recognized that partial optimizations, where we are allowed to disregard a small part of the data, provide us significantly better solutions. The motivation for disregarded points often arise from noise and other phenomena that are pervasive in large data scenarios. In this paper we focus on partial clustering problems, k-center, k-median and k-means, in the distributed model, and provide algorithms with communication sublinear of the input size. As a consequence we develop the first algorithms for the partial k-median and means objectives that run in subquadratic running time. We also initiate the study of distributed algorithms for clustering uncertain data, where each data point can possibly fall into multiple locations under certain probability distribution. 

   more » « less
4. Distributed Multiarmed Bandits

   https://doi.org/10.1109/TAC.2023.3247982  

   Zhu, Jingxuan ; Liu, Ji ( May 2023 , IEEE Transactions on Automatic Control)
5. Interactive Distributed Proofs

   Kol, Gillat ; Oshman, Rotem ; Saxena, Raghuvansh. ( January 2018 , ACM Symposium on Principles of Distributed Computing)

   Interactive proof systems allow a resource-bounded verifier to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee that the prover can only convince the verifier of true statements. In the context of centralized computation, a celebrated result shows that interactive proofs are extremely powerful, allowing polynomial-time verifiers to decide any language in PSPACE. In this work we initiate the study of interactive distributed proofs: a network of nodes interacts with a single untrusted prover, who sees the entire network graph, to decide whether the graph satisfies some property. We focus on the communication cost of the protocol — the number of bits the nodes must exchange with the prover and each other. Our model can also be viewed as a generalization of the various models of “distributed NP” (proof labeling schemes, etc.) which received significant attention recently: while these models only allow the prover to present each network node with a string of advice, our model allows for back-and-forth interaction. We prove both upper and lower bounds for the new model. We show that for some problems, interaction can exponentially decrease the communication cost compared to a non-interactive prover, but on the other hand, some problems retain non-trivial cost even with interaction. 

   more » « less