Self-stabilizing Population Protocols
summary
Shows a way to count anonymous agents with only one bit each by giving a single initialized base station three counters (n0 n1 n) and flipping encountered bits; the naive base‑station scheme stabilizes in exponential expected parallel time, and a refined two‑state protocol matches a proved lower bound and is time‑optimal. Presents a self‑stabilizing leader election and ranking that runs in O(log n) parallel time by giving agents names from [1..n^3], merging rosters via epidemic propagation, detecting ghost names and homonyms with historical sync trees of depth O(log n), and using resets to reassign unique names; per‑agent space is polylogarithmic.
AI-written summary · about
chapters (9)
- 0:00Self-stabilizing population protocols
- 1:50Distributed algorithms overview
- 6:53Formal model and fairness
- 16:49Self-stabilization in systems
- 19:13Counting agents with memory
- 33:34Leader election in protocols
- 42:34Self-stabilizing leader election
- 53:43Efficient name collision detection
- 1:05:02Challenges in self-stabilizing protocols
related talks
52mGame-Theoretically Secure Protocols Inspired by Blockchains
29mBuilding Probabilistic BFT Protocols Through Subsampled Voting
46mTiming Matters: Online Dynamics in Broadcast Games
42mStochastic reasoning in decentralised systems
34mTribes is Hard in the Message Passing Model
49mAn Algorithmic Theory of Brain Networks
31mCompositional Verification of Stigmergic Collective Systems
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)