Grocery on Distributed Algorithms

B1: Paradigms for Randomized Algorithms

Reminder: This post contains 471 words · 2 min read · by Xianbin

When designing randomized algorithms, there are many ways. The following paradigms in [1] are useful.

  1. Fooling an adversary
  2. Random Sampling
  3. Abundance of witness
  4. Fingerprinting and hashing
  5. Random re-ordering
  6. Load Balancing
  7. Rapidly mixing Markov chains
  8. Isolation and symmetry breaking
  9. Probabilistic methods and existence proofs.

Paradigms 2, 6, 7, 9 can be seen a lot in papers. In this blog, I will cover all the above methods by examples.

Reference

[1]. Motwani, Rajeev, and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.