Topology recognition and leader election are fundamental tasks in distributed computing in networks. The first of them requires each node to find a labeled isomorphic copy of the network, while the result of the second one consists in a single node adopting the label 1 (leader), with all other nodes adopting the label 0 and learning a path to the leader. We consider both these problems in networks whose nodes are equipped with...

We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph...

We resolve a conjecture proposed by D.E. Knuth concerning a recurrence arising in the satisfiability problem. Knuth's recurrence resembles recurrences arising in the analysis of tries, in particular PATRICIA tries, and asymmetric leader election. We solve Knuth's recurrence exactly and asymptotically, using analytic techniques such as the Mellin transform and analytic depoissonization.

Tries are among the most versatile and widely used data structures on words. They are pertinent to the (internal) structure of (stored) words and several splitting procedures used in diverse contexts ranging from document taxonomy to IP addresses lookup, from data compression (i.e., Lempel- Ziv'77 scheme) to dynamic hashing, from partial-match queries to speech recognition, from leader election algorithms to distributed hashing...