  To improve the overall efficiency and reliability of Byzantine protocols in
large sparse networks, we propose a new system assumption for developing
multi-scale fault-tolerant systems, with which several kinds of multi-scale
Byzantine protocols are developed in large sparse networks with high system
assumption coverage. By extending the traditional Byzantine adversary to the
multi-scale adversaries, it is shown that efficient deterministic Byzantine
broadcast and Byzantine agreement can be built in logarithmic-degree networks.
Meanwhile, it is shown that the multi-scale adversary can make a finer
trade-off between the system assumption coverage and the overall efficiency of
the Byzantine protocols, especially when a small portion of the low-layer
small-scale protocols are allowed to fail arbitrarily. With this, efficient
Byzantine protocols can be built in large sparse networks with high system
reliability.
