  Implementations of SGD on distributed systems create new vulnerabilities,
which can be identified and misused by one or more adversarial agents.
Recently, it has been shown that well-known Byzantine-resilient gradient
aggregation schemes are indeed vulnerable to informed attackers that can tailor
the attacks (Fang et al., 2020; Xie et al., 2020b). We introduce MixTailor, a
scheme based on randomization of the aggregation strategies that makes it
impossible for the attacker to be fully informed. Deterministic schemes can be
integrated into MixTailor on the fly without introducing any additional
hyperparameters. Randomization decreases the capability of a powerful adversary
to tailor its attacks, while the resulting randomized aggregation scheme is
still competitive in terms of performance. For both iid and non-iid settings,
we establish almost sure convergence guarantees that are both stronger and more
general than those available in the literature. Our empirical studies across
various datasets, attacks, and settings, validate our hypothesis and show that
MixTailor successfully defends when well-known Byzantine-tolerant schemes fail.
