We consider boundary coverage of a regular structure by a swarm of miniature robots, and compare a suite of three fully distributed coordination algorithms experimentally. All algorithms rely on boundary coverage by reactive control, whereas coordination of the robots high-level behavior is fundamentally different: random, self-organized, and deliberative with reactive elements. The self-organized coordination algorithm was designed using macroscopic probabilistic models that lead to analytical expressions for the algorithm's mean performance. We contrast this approach with a provably complete, near optimal coverage algorithm, which is due to its assumption (noise-less sensors and actuators) infeasible on a real miniature robotic platform, but is considered to yield best-possible policies for an individual robot. Experimental results with swarms of up to 30 robots show that self-organization significantly improves coverage performance with increasing swarm size. We also observe that enforcing a provably complete policy on a miniature robot with limited hardware capabilities is highly sub-optimal as there is a trade-off between coverage throughput and time spent for localization and navigation.