Vi studerar den minsta minnesstorlek med vilken noder av ett nätverk måste utrustas, för att deterministiskt lösa problemet ledare val. Noder är omärkta, men hamnar vid varje nod har godtyckliga fasta märkningar som tillsammans med nätverkets topologi kan skapa asymmetrier som ska utnyttjas i ledarval. Vi anser att två versioner av ledare val problem: stark LE där exakt en ledare måste väljas, om detta är möjligt, medan alla noder måste avsluta i en stat "ogenomförbar" när valet av en unik ledare misslyckas, och svag LE, som skiljer sig från stark LE i att inga krav på beteendet av noder införs, om ledare val är omöjligt. Noder är modellerade som identiska automata och vi frågar vad är den minsta mängden minne av en sådan automaton för att möjliggöra ledarval. Vi visar att logaritmiskt minne är optimalt för både starka och svaga ledare val i klassen av godtyckliga anslutna grafer. Däremot visar vi att stark LE kan uppnås i klassen av träd av Computer Science Department, Sapienza, University of Rome, 00198 Rom, Italien e-post: fusco@di.uniroma1.it A. Pelc Département d'informatique, Université du Québec en Outaouais, Gatineau, QC J8X 3X7, Kanada e-post: pelc@uqo.ca maximal grad med endast O (logglogglogg ) bitar av minne, vilket visar en exponentiell lucka i minne krav för ledare val mellan klassen av träd och klassen av godtyckliga grafer.
Minne som behövdes för ledarval i omärkta nätverk studerades i REF.
How much memory is needed for leader election
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}