Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Time and Communication Complexity of Leader Election in Anonymous
  Networks   We study the problem of randomized Leader Election in synchronous distributed
networks with indistinguishable nodes. We consider algorithms that work on
networks of arbitrary topology in two settings, depending on whether the size
of the network, i.e., the number of nodes, is known or not. In the former
setting, we present a new Leader Election protocol that improves over previous
work by lowering message complexity and making it close to a lower bound by a
factor of $\tilde{O}(\sqrt{t_{mix}\sqrt{\Phi}})$, where $\Phi$ is the
conductance and $t_{mix}$ is the mixing time of the network graph. We then show
that lacking the network size no Leader Election algorithm can guarantee that
the election is final with constant probability, even with unbounded
communication. Hence, we further classify the problem as Irrevocable Leader
Election (the classic one, requiring knowledge of n - as is our first protocol)
or Revocable Leader Election, and present a new polynomial time and message
complexity Revocable Leader Election algorithm in the setting without knowledge
of network size. We analyze time and message complexity of our protocols in the
Congest model of communication.

20
The categories of this paper are: acc-phys
21
The categories of this paper are: adap-org
28
The categories of this paper are: alg-geom
14
The categories of this paper are: math-ph
11
The categories of this paper are: hep-lat
32
The categories of this paper are: atom-ph
26
The categories of this paper are: bayes-an
34
The categories of this paper are: chem-ph
37
The categories of this paper are: supr-con
5
The categories of this paper are: gr-qc
22
The categories of this paper are: chao-dyn
0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex
19
The categories of this paper are: eess
17
The categories of this paper are: q-fin
27
The categories of this paper are: comp-gas