Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleOctober 2022
Deterministic Leader Election in Anonymous Radio Networks
ACM Transactions on Algorithms (TALG), Volume 18, Issue 3Article No.: 25, Pages 1–33https://doi.org/10.1145/3527171Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader, and for all other nodes to become non-leaders. We consider leader election in anonymous radio ...
- research-articleOctober 2021
Smaller Cuts, Higher Lower Bounds
ACM Transactions on Algorithms (TALG), Volume 17, Issue 4Article No.: 30, Pages 1–40https://doi.org/10.1145/3469834This article proves strong lower bounds for distributed computing in the congest model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts.
The contribution of bit-gadgets is twofold. First, developing careful sparse ...
- research-articleMarch 2017
Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
ACM Transactions on Algorithms (TALG), Volume 13, Issue 3Article No.: 31, Pages 1–41https://doi.org/10.1145/3039870Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that ...