Skip to Main content Skip to Navigation
Conference papers

On Greedy Trie Execution

Abstract : In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping fair coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen. We give an answer to the question stated in the Prodinger's paper – what happens if not a 0-party is recursively looking for a leader but always a party with a smaller cardinality. We show the lower bound on the number of rounds of the greedy algorithm (for fair coin).
Keywords : Trie leader election
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01197231
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, September 11, 2015 - 12:54:51 PM
Last modification on : Tuesday, March 7, 2017 - 3:18:43 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:33:58 AM

File

dmAQ0129.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01197231, version 1

Collections

Citation

Zbigniew Gołębiewski, Filip Zagórski. On Greedy Trie Execution. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.377-380. ⟨hal-01197231⟩

Share

Metrics

Record views

203

Files downloads

642