Over the past years, various low-power wireless protocols based on synchronous
transmissions (ST) have been developed to meet the high dependability requirements of
emerging cyber-physical applications. For example, Wireless Paxos provides consensus,
a key mechanism for building fault-tolerant systems through replication. However,
Wireless Paxos and other ST-based protocols are themselves not fault-tolerant: They
suffer from a single point of failure that fundamentally impairs the availability of the
communication service in the presence of node crashes and network partitions.
We present Butler, a mechanism that allows removing the single point of failure in
many ST-based protocols. Butler synchronizes all nodes in the network so that the
communication process can be jointly started by multiple randomly chosen nodes rather
than a single dedicated node. We analyze and formally prove the correctness of Butler
and implement it on the state-of-the-art nRF52840 platform. Experiments on the
FlockLab testbed demonstrate that Butler reliably synchronizes the network to within
±3 µs despite large initial offsets, unpredictable node failures, and network partitions.
Butler’s temporal overhead ranges well below 1 %. Because of this efficiency and
effectiveness, our results further indicate that Butler can dramatically improve the
availability of an existing ST-based protocol without any noticeable impact on the
overall communication reliability and efficiency.