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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.3007⟩. ⟨hal-01197231⟩

Share

Metrics

Record views

54

Files downloads

414