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

> 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).

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.