Signal, if you can’t (for the damage)
summary
Claim: arbitrary noiseless protocols are simulatable by pure signaling when every link’s content is destroyed, provided the network is 2-edge connected; impossible if the graph has a bridge. Construction: deterministic pulse protocols build a Robbins cycle via content‑oblivious DFS/ear decomposition and run token/data + ack/end signaling; leader election on rings is done by ID‑pulse counts. Limitations: needs a root (or ring leader preprocessing), no clean termination in unoriented rings, preprocessing ~n^8 and ~n^3 pulses per simulated bit, leader cost ~n·maxID.
AI-written summary · about
chapters (10)
- 0:00Content-oblivious computation intro
- 2:46Message corruption breaks models
- 5:56Bridges block async computation
- 10:37Simulate on 2-edge networks
- 13:09Signaling with pulses
- 18:45Extending to general 2-edge graphs
- 22:52Robbins cycles without content
- 28:00Leader election in oblivious rings
- 35:47Unoriented networks and termination
- 40:22Summary: pulse-based computation
related talks
39mBroadcasting on Directed Acyclic Graphs
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
57mCoding for Interactive Communication
56mConsensus Through Herding
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
16mCyclic Message Histories for Automated Safety Verification of Distributed Algorithms
34mConsensus with Adaptive Adversaries in the Synchronous and Partially Synchronous Models...
58mThe Communication Complexity Landscape of Information-theoretic MPC