title: Simple Algorithms for Distributed Leader Election in Anonymous Synchronous Rings and Complete Networks Inspired by Neural Development in Fruit Flies.
abstract: Leader election in anonymous rings and complete networks is a very practical problem in distributed computing. Previous algorithms for this problem are generally designed for a classical message passing model where complex messages are exchanged. However, the need to send and receive complex messages makes such algorithms less practical for some real applications. We present some simple synchronous algorithms for distributed leader election in anonymous rings and complete networks that are inspired by the development of the neural system of the fruit fly. Our leader election algorithms all assume that only one-bit messages are broadcast by nodes in the network and processors are only able to distinguish between silence and the arrival of one or more messages. These restrictions allow implementations to use a simpler message-passing architecture. Even with these harsh restrictions our algorithms are shown to achieve good time and message complexity both analytically and experimentally.
authors.affiliation: Audaque Data Technology Ltd., Software Building, 9 Gaoxin Middle First Road, Nanshan District, Shenzhen 518000, China.|Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK.
authors.forename: Lei
authors.initials: L
authors.lastname: Xu
authors.affiliation: Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK.
authors.forename: Peter
authors.initials: P
authors.lastname: Jeavons
mesh_terms: D000465:Algorithms; D000818:Animals; D002450:Cell Communication / Q000502:physiology; D004330:Drosophila / Q000254:growth & development / Q000502:physiology; D008959:Models, Neurological; D016571:Neural Networks, Computer; D013997:Time Factors
keywords: Leader election; anonymous networks; bio-inspired algorithms; cell signalling; distributed computing