caa a22 4500 445355131 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00446-011-0131-y doi (NATIONALLICENCE)springer-10.1007/s00446-011-0131-y How much memory is needed for leader election [Elektronische Daten] [Emanuele Fusco, Andrzej Pelc] We study the minimum memory size with which nodes of a network have to be equipped, in order to solve deterministically the leader election problem. Nodes are unlabeled, but ports at each node have arbitrary fixed labelings which, together with the topology of the network, can create asymmetries to be exploited in leader election. We consider two versions of the leader election problem: strong LE in which exactly one leader has to be elected, if this is possible, while all nodes must terminate in a state "infeasible” when the election of a unique leader fails, and weak LE, which differs from strong LE in that no requirement on the behavior of nodes is imposed, if leader election is impossible. Nodes are modeled as identical automata and we ask what is the minimum amount of memory of such an automaton to enable leader election. We show that logarithmic memory is optimal for both strong and weak leader election in the class of arbitrary connected graphs. By contrast we show that strong LE can be accomplished in the class of trees of maximum degree Δ using only O(log log Δ) bits of memory, thus proving an exponential gap in memory requirements for leader election between the class of trees and the class of arbitrary graphs. Springer-Verlag, 2011 Leader election nationallicence Anonymous graphs nationallicence Memory nationallicence Fusco Emanuele Computer Science Department, Sapienza, University of Rome, 00198, Rome, Italy aut Pelc Andrzej Département d'informatique, Université du Québec en Outaouais, J8X 3X7, Gatineau, QC, Canada aut Distributed Computing Springer-Verlag 24/2(2011-10-01), 65-78 0178-2770 24:2<65 2011 24 446 https://doi.org/10.1007/s00446-011-0131-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0131-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fusco Emanuele Computer Science Department, Sapienza, University of Rome, 00198, Rome, Italy aut NATIONALLICENCE 700 1- Pelc Andrzej Département d'informatique, Université du Québec en Outaouais, J8X 3X7, Gatineau, QC, Canada aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/2(2011-10-01), 65-78 0178-2770 24:2<65 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer