Mediated population protocols are an extension of popula-tion protocols in which communication links, as well as agents, have internal states. We study the leader election problem and some applica-tions in constant-state mediated population protocols. Depending on the power of the adversarial scheduler, our algorithms are either stabilizing or allow the agents to explicitly reach a terminal state. We show how to elect a unique leader if the graph of the possible interactions between agents is complete (as in the traditional popula-tion protocol model) or a tree. Moreover, we prove that a leader can be elected in a complete bipartite graph if and only if the two sides have coprime size. We then describe how to take advantage of the presence of a leader to solve the tasks of token circulation and construction of a shortest-path spanning tree of the network. Finally, we prove that with a leader we can transform any stabilizing protocol into a terminating one that solves the same task.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-55911-7_13
Series Lecture Notes in Computer Science
Citation
Das, S. (Shantanu), Di Luna, G.A. (Giuseppe Antonio), Flocchini, P. (Paola), Santoro, N, & Viglietta, G. (Giovanni). (2017). Mediated population protocols: Leader election and applications. In Lecture Notes in Computer Science. doi:10.1007/978-3-319-55911-7_13