Stochastic coalescence in logarithmic time

DOI10.1214/11-AAP832zbMath1270.60110arXiv1101.3110OpenAlexW2762105436MaRDI QIDQ1948695

Eyal Lubetzky, Po-Shen Loh

Publication date: 24 April 2013

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1101.3110

zbMATH Keywords

processstochastic coalescencerandomized distributed algorithms

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic fringe distributions for general families of random trees
• Birth control for giants
• The coalescent
• On tail probabilities for martingales
• The expected linearity of a simple equivalence algorithm
• Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists
• On the distribution for the duration of a randomized leader election algorithm
• Perfect information leader election in \(\log^*n+O(1)\) rounds
• Fast perfect-information leader-election protocols with linear immunity
• Simple and efficient leader election in the full information model
• Probabilistic Analysis of Disjoint Set Union Algorithms
• Probability Models for DNA Sequence Evolution
• Percolation
• Probability
• Graph colouring and the probabilistic method

This page was built for publication: Stochastic coalescence in logarithmic time