  It was suggested that a programmable matter system (composed of multiple
computationally weak mobile particles) should remain connected at all times
since otherwise, reconnection is difficult and may be impossible. At the same
time, it was not clear that allowing the system to disconnect carried a
significant advantage in terms of time complexity. We demonstrate for a
fundamental task, that of leader election, an algorithm where the system
disconnects and then reconnects automatically in a non-trivial way (particles
can move far away from their former neighbors and later reconnect to others).
Moreover, the runtime of the temporarily disconnecting deterministic leader
election algorithm is linear in the diameter. Hence, the disconnecting --
reconnecting algorithm is as fast as previous randomized algorithms. When
comparing to previous deterministic algorithms, we note that some of the
previous work assumed weaker schedulers. Still, the runtime of all the previous
deterministic algorithms that did not assume special shapes of the particle
system (shapes with no holes) was at least quadratic in $n$, where $n$ is the
number of particles in the system. (Moreover, the new algorithm is even faster
in some parameters than the deterministic algorithms that did assume special
initial shapes.)
  Since leader election is an important module in algorithms for various other
tasks, the presented algorithm can be useful for speeding up other algorithms
under the assumption of a strong scheduler. This leaves open the question: "can
a deterministic algorithm be as fast as the randomized ones also under weaker
schedulers?"
