7 Search Results for "Clementi, Andrea"


Document
Bond Percolation in Small-World Graphs with Power-Law Distribution

Authors: Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)


Abstract
Full-bond percolation with parameter p is the process in which, given a graph, for every edge independently, we keep the edge with probability p and delete it with probability 1-p. Bond percolation is studied in parallel computing and network science to understand the resilience of distributed systems to random link failure and the spread of information in networks through unreliable links. Moreover, the full-bond percolation is equivalent to the Reed-Frost process, a network version of SIR epidemic spreading. We consider one-dimensional power-law small-world graphs with parameter α obtained as the union of a cycle with additional long-range random edges: each pair of nodes {u,v} at distance L on the cycle is connected by a long-range edge {u,v}, with probability proportional to 1/L^α. Our analysis determines three phases for the percolation subgraph G_p of the small-world graph, depending on the value of α. - If α < 1, there is a p < 1 such that, with high probability, there are Ω(n) nodes that are reachable in G_p from one another in 𝒪(log n) hops; - If 1 < α < 2, there is a p < 1 such that, with high probability, there are Ω(n) nodes that are reachable in G_p from one another in log^{𝒪(1)}(n) hops; - If α > 2, for every p < 1, with high probability all connected components of G_p have size 𝒪(log n).

Cite as

Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi. Bond Percolation in Small-World Graphs with Power-Law Distribution. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.SAND.2023.3,
  author =	{Becchetti, Luca and Clementi, Andrea and Pasquale, Francesco and Trevisan, Luca and Ziccardi, Isabella},
  title =	{{Bond Percolation in Small-World Graphs with Power-Law Distribution}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.3},
  URN =		{urn:nbn:de:0030-drops-179392},
  doi =		{10.4230/LIPIcs.SAND.2023.3},
  annote =	{Keywords: Information spreading, gossiping, epidemics, fault-tolerance, network self-organization and formation, complex systems, social and transportation networks}
}
Document
Asynchronous Rumor Spreading in Dynamic Graphs

Authors: Bernard Mans and Ali Pourmiri

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)


Abstract
We study asynchronous rumor spreading algorithm in dynamic and static graphs. In the asynchronous rumor spreading, for a given underlying graph, each node is equipped with an exponential time clock of rate 1. When a node’s clock ticks, the node calls a random neighbor in order to exchange a rumor, if at least one of them knows it. Assuming a single node knows a rumor, we apply a differential equation-based technique to obtain an upper bound for the spread time of the algorithm in general dynamic graphs, which is the first time when all nodes get informed with high probability. In particular, we derive an upper bound for the spread time of the algorithm in a discrete version of a geometric mobile network, introduced by Clementi et al. [Andrea E. F. Clementi et al., 2011]. In this model, a set of n agents independently performs random walks on a √n× √n plane and every two agents are able to communicate if they are within Euclidean distance at most R, where f(n)√{log n} ⩽ R ⩽ √n and f(n) is a slowly growing function in n. Here, we show that the algorithm spreads a rumor through the network in 𝒪(log n+√n/R) time, with high probability. Although we only show an upper bound the spread time of the algorithm in a 2 dimensional space, the framework can be also applied for geometric mobile networks defined over higher dimensional space and other random dynamic evolving networks such as stationary edge-Markovian model. Besides these synchronous and discrete dynamic models, we also consider the spreading time in dynamical Erdős-Rényi graphs.

Cite as

Bernard Mans and Ali Pourmiri. Asynchronous Rumor Spreading in Dynamic Graphs. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{mans_et_al:LIPIcs.OPODIS.2021.31,
  author =	{Mans, Bernard and Pourmiri, Ali},
  title =	{{Asynchronous Rumor Spreading in Dynamic Graphs}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.31},
  URN =		{urn:nbn:de:0030-drops-158069},
  doi =		{10.4230/LIPIcs.OPODIS.2021.31},
  annote =	{Keywords: randomized rumor spreading, push/pull, asynchronous rumor spreading}
}
Document
Approximate Majority with Catalytic Inputs

Authors: Talley Amir, James Aspnes, and John Lazarsfeld

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
Population protocols [Dana Angluin et al., 2006] are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents [Bartlomiej Dudek and Adrian Kosowski, 2018; Alistarh et al., 2017; Dan Alistarh et al., 2020], we assume a population with n catalytic input agents and m worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For m = Θ(n), we show that computing the parity of the input population with high probability requires at least Ω(n²) total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics [Angluin et al., 2008; Perron et al., 2009] for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in O(n log n) total steps with high probability when the input margin is Ω(√{n log n}). We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by [Alistarh et al., 2017; Dan Alistarh et al., 2020]. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability β ≤ O(√{n log n}/n). The resilience of these dynamics to leaks exhibits similarities to previous work involving Byzantine agents, and we define and prove a notion of equivalence between the two.

Cite as

Talley Amir, James Aspnes, and John Lazarsfeld. Approximate Majority with Catalytic Inputs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.OPODIS.2020.19,
  author =	{Amir, Talley and Aspnes, James and Lazarsfeld, John},
  title =	{{Approximate Majority with Catalytic Inputs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.19},
  URN =		{urn:nbn:de:0030-drops-135040},
  doi =		{10.4230/LIPIcs.OPODIS.2020.19},
  annote =	{Keywords: population protocols, approximate majority, catalysts, leaks, lower bound}
}
Document
Extended Abstract
Consensus vs Broadcast, with and Without Noise (Extended Abstract)

Authors: Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, and Luca Trevisan

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast, and this can be rigorously established in several models. Can Consensus be easier than Broadcast? In models that allow noiseless communication, we prove a reduction of (a suitable variant of) Broadcast to binary Consensus, that preserves the communication model and all complexity parameters such as randomness, number of rounds, communication per round, etc., while there is a loss in the success probability of the protocol. Using this reduction, we get, among other applications, the first logarithmic lower bound on the number of rounds needed to achieve Consensus in the uniform GOSSIP model on the complete graph. The lower bound is tight and, in this model, Consensus and Broadcast are equivalent. We then turn to distributed models with noisy communication channels that have been studied in the context of some bio-inspired systems. In such models, only one noisy bit is exchanged when a communication channel is established between two nodes, and so one cannot easily simulate a noiseless protocol by using error-correcting codes. An Ω(ε^{-2} n) lower bound is proved by Boczkowski et al. [PLOS Comp. Bio. 2018] on the convergence time of binary Broadcast in one such model (noisy uniform PULL), where ε is a parameter that measures the amount of noise). We prove an O(ε^{-2} log n) upper bound on the convergence time of binary Consensus in such model, thus establishing an exponential complexity gap between Consensus versus Broadcast. We also prove our upper bound above is tight and this implies, for binary Consensus, a further strong complexity gap between noisy uniform PULL and noisy uniform PUSH. Finally, we show a Θ(ε^{-2} n log n) bound for Broadcast in the noisy uniform PULL.

Cite as

Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, and Luca Trevisan. Consensus vs Broadcast, with and Without Noise (Extended Abstract). In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{clementi_et_al:LIPIcs.ITCS.2020.42,
  author =	{Clementi, Andrea and Gual\`{a}, Luciano and Natale, Emanuele and Pasquale, Francesco and Scornavacca, Giacomo and Trevisan, Luca},
  title =	{{Consensus vs Broadcast, with and Without Noise}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.42},
  URN =		{urn:nbn:de:0030-drops-117277},
  doi =		{10.4230/LIPIcs.ITCS.2020.42},
  annote =	{Keywords: Distributed Computing, Consensus, Broadcast, Gossip Models, Noisy Communication Channels}
}
Document
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors

Authors: Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
The Undecided-State Dynamics is a well-known protocol for distributed consensus. We analyze it in the parallel PULL communication model on the complete graph with n nodes for the binary case (every node can either support one of two possible colors, or be in the undecided state). An interesting open question is whether this dynamics is an efficient Self-Stabilizing protocol, namely, starting from an arbitrary initial configuration, it reaches consensus quickly (i.e., within a polylogarithmic number of rounds). Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. In this paper we present an unconditional analysis of the Undecided-State Dynamics that answers to the above question in the affirmative. We prove that, starting from any initial configuration, the process reaches a monochromatic configuration within O(log n) rounds, with high probability. This bound turns out to be tight. Our analysis also shows that, if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color, with high probability.

Cite as

Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{clementi_et_al:LIPIcs.MFCS.2018.28,
  author =	{Clementi, Andrea and Ghaffari, Mohsen and Gual\`{a}, Luciano and Natale, Emanuele and Pasquale, Francesco and Scornavacca, Giacomo},
  title =	{{A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.28},
  URN =		{urn:nbn:de:0030-drops-96107},
  doi =		{10.4230/LIPIcs.MFCS.2018.28},
  annote =	{Keywords: Distributed Consensus, Self-Stabilization, PULL Model, Markov Chains}
}
Document
Average Whenever You Meet: Opportunistic Protocols for Community Detection

Authors: Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
Consider the following asynchronous, opportunistic communication model over a graph G: in each round, one edge is activated uniformly and independently at random and (only) its two endpoints can exchange messages and perform local computations. Under this model, we study the following random process: The first time a vertex is an endpoint of an active edge, it chooses a random number, say +/- 1 with probability 1/2; then, in each round, the two endpoints of the currently active edge update their values to their average. We provide a rigorous analysis of the above process showing that, if G exhibits a two-community structure (for example, two expanders connected by a sparse cut), the values held by the nodes will collectively reflect the underlying community structure over a suitable phase of the above process. Our analysis requires new concentration bounds on the product of certain random matrices that are technically challenging and possibly of independent interest. We then exploit our analysis to design the first opportunistic protocols that approximately recover community structure using only logarithmic (or polylogarithmic, depending on the sparsity of the cut) work per node.

Cite as

Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan. Average Whenever You Meet: Opportunistic Protocols for Community Detection. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.ESA.2018.7,
  author =	{Becchetti, Luca and Clementi, Andrea and Manurangsi, Pasin and Natale, Emanuele and Pasquale, Francesco and Raghavendra, Prasad and Trevisan, Luca},
  title =	{{Average Whenever You Meet: Opportunistic Protocols for Community Detection}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.7},
  URN =		{urn:nbn:de:0030-drops-94705},
  doi =		{10.4230/LIPIcs.ESA.2018.7},
  annote =	{Keywords: Community Detection, Random Processes, Spectral Analysis}
}
Document
Brief Announcement
Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors

Authors: Andrea Clementi, Luciano Gualà, Francesco Pasquale, and Giacomo Scornavacca

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
The Undecided-State Dynamics is a well-known protocol that achieves Consensus in distributed systems formed by a set of n anonymous nodes interacting via a communication network. We consider this dynamics in the parallel PULL communication model on the complete graph for the binary case, i.e., when every node can either support one of two possible colors or stay in the undecided state. Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. A interesting open question here is whether this dynamics reaches consensus quickly, i.e. within a polylogarithmic number of rounds. In this paper we present an unconditional analysis of the Undecided-State Dynamics which answers to the above question in the affirmative. Our analysis shows that, starting from any initial configuration, the Undecided-State Dynamics reaches a monochromatic configuration within O(log^2 n) rounds, with high probability (w.h.p.). Moreover, we prove that if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color within O(log n) round, w.h.p. At the heart of our approach there is a new analysis of the symmetry-breaking phase that the process must perform in order to escape from (almost-)unbiased configurations. Previous symmetry-breaking analysis of consensus dynamics essentially concern sequential communication models (such as Population Protocols) and/or symmetric updated rules (such as majority rules).

Cite as

Andrea Clementi, Luciano Gualà, Francesco Pasquale, and Giacomo Scornavacca. Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 47:1-47:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{clementi_et_al:LIPIcs.DISC.2017.47,
  author =	{Clementi, Andrea and Gual\`{a}, Luciano and Pasquale, Francesco and Scornavacca, Giacomo},
  title =	{{Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{47:1--47:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.47},
  URN =		{urn:nbn:de:0030-drops-79724},
  doi =		{10.4230/LIPIcs.DISC.2017.47},
  annote =	{Keywords: Distributed Consensus, Dynamics, Gossip model, Markov chains}
}
  • Refine by Author
  • 5 Clementi, Andrea
  • 5 Pasquale, Francesco
  • 3 Gualà, Luciano
  • 3 Natale, Emanuele
  • 3 Scornavacca, Giacomo
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Random network models
  • 1 Computing methodologies → Distributed algorithms
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Network flows
  • Show More...

  • Refine by Keyword
  • 2 Distributed Consensus
  • 1 Broadcast
  • 1 Community Detection
  • 1 Consensus
  • 1 Distributed Computing
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2018
  • 1 2017
  • 1 2020
  • 1 2021
  • 1 2022
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail