FURI | Spring 2024

Canonicalizing Amoebot Leader Election Algorithms

Leader election is a fundamental problem in distributing computing theory, in which systems must determine a unique leader processor. An area where leader election plays an important role is programmable matter — substances that can change their properties based on inputs. The model being looked at, the Amoebot model, has many leader election algorithms proposed, but since the model was not standardized until 2022, the assumptions of different algorithms can be inconsistent. This project intends to standardize the assumptions of leader election algorithms, ensure the validity of their proofs under standard assumptions, and make clear comparisons between the algorithms.