How to Elect a Leader Faster Than a Tournament (2014)

by jbapple • 11 years ago

24 4 11 years ago

titanomachy2• 11 years ago

How can an algorithm which sends O(n^2) messages between n nodes have O(log-star(n)) time complexity? I'm reading the paper now to try and understand, but it doesn't seem possible to me. Doesn't O(n^2) messages mean each node send on average O(n) messages? Perhaps some subtlety of asymptotic notation escapes me here.

For those (like me) who didn't know, log-star is the iterated log function and grows very slowly: IteratedLog[2^65536] == 5.

titanomachy2• 11 years ago

The answer, of course, is in the paper: "time complexity" here doesn't have its usual meaning, but is defined as "the number of times a processor relies on the adversary to schedule a computation step or to deliver messages". The paper implies that this is the usual definition used in distributed systems analysis.

z3t4• 11 years ago

Why do scientific "papers" insist of using PDF when HTML would be a much better choice as it supports linking to references, dynamic media (better graphs), meta keywords and search indexing!?

jamessb• 11 years ago

Why do scientific "papers" insist of using PDF when HTML would be a much better choice

Almost all journals do offer both HTML and PDF versions of their articles. The main advantage of PDF is that it appears exactly the same as the printed article in a journal, and is easy to print.

A PDF also combines the whole article into a single file that can be easily imported into reference management software.

as it supports linking to references

So does PDF (easily generated in LaTeX using the hyperref package), though a given PDF file may or may not actually include links. For example, the ACS journals offer a 'PDF' and 'PDF w/ Links' download for every article.

dynamic media (better graphs)

This is a fair point, but enhanced/interactive figures could be on a separate figures-only web page.

meta keywords

PDF does support metadata, including Author, Title and Keywords. In LaTeX this can set using pdfinfo: http://www.howtotex.com/tips-tricks/adding-pdf-metadata-in-l...

search indexing

I'm not sure what you mean. The PDF of any paper will contain serchable text (except for old papers produced by scanning archived copies).

How to Elect a Leader Faster Than a Tournament (2014)

Related Stories