On the Smallest Grain of Salt to Get a Unique Identity

We study the fundamental enumeration problem in asynchronous message-passing networks. Anonymous processes have to eventually decide on pairwise distinct identifiers, despite all starting in the same initial state. It is known since Angluin’s seminal result [2] that some grain of salt is required for distributed algorithms to solve the problem, e.g., the system needs to have a non-symmetrical topology or unbiased independent random bits.