On the Distributed Complexity of Large-Scale Graph Computations

Autor: Peter Robinson, Michele Scquizzato, Gopal Pandurangan

Publikováno v: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
SPAA
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures-SPAA 18
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures -SPAA '18

Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly per

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f533d2d59f62ff5c3bf728f1e9b4871
https://doi.org/10.1145/3460900

A $${o}\mathopen {}\left( n\right) \mathclose {}$$-Competitive Deterministic Algorithm for Online Matching on a Line

Autor: Michele Scquizzato, Michael Nugent, Kirk Pruhs, Neal Barcelo, Antonios Antoniadis

Publikováno v: Algorithmica. 81:2917-2933

Online matching on a line involves matching an online stream of requests to a given set of servers, all in the real line, with the objective of minimizing the sum of the distances between matched server-request pairs. The best previously known upper

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::f54baaeda3caa556c793bcdc7ca25065
https://doi.org/10.1007/s00453-019-00565-w

Matching on the line admits no $o(\sqrt{\log n})$-competitive algorithm

Autor: Enoch Peserico, Michele Scquizzato

We present a simple proof that no randomized online matching algorithm for the line can be \((\sqrt {\log _2(n\!+\!1)}/15) \) -competitive against an oblivious adversary for any \(n=2^i\!-\!1: i\in \mathbb {N} \) . This is the first super-constant lo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e70c11b36695332b98bb5218cccf2177
http://arxiv.org/abs/2012.15593

Equivalence classes and conditional hardness in massively parallel computations

Autor: Danupon Nanongkai, Michele Scquizzato

Publikováno v: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Nanongkai, D & Scquizzato, M 2022, ' Equivalence classes and conditional hardness in massively parallel computations ', Distributed Computing, vol. 35, no. 2, pp. 165-183 . https://doi.org/10.1007/s00446-021-00418-2

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical gr

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::08a63be832588d7f7685e3301d5872c3
http://hdl.handle.net/11577/3335098

A time- and message-optimal distributed algorithm for minimum spanning trees

Autor: Michele Scquizzato, Peter Robinson, Gopal Pandurangan

Publikováno v: STOC

This article presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Õ( D + √ n ) t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1c3bcfaa0f0fa28f3d3c4e69a991f256
http://hdl.handle.net/11577/3298666