Multi-Krum

Multi-Krum is an extension of Krum that selects the top-$m$ most central client updates and averages them — instead of using only a single client's update (high variance), Multi-Krum selects multiple trustworthy updates and averages for lower variance while maintaining Byzantine robustness.

How Multi-Krum Works

• Score: Compute Krum scores for all clients (sum of distances to nearest neighbors).
• Select Top-$m$: Pick the $m$ clients with the lowest Krum scores.
• Average: Compute the average of the $m$ selected updates.
• $m$ Choice: $m = 1$ is standard Krum. $m = n - f$ uses all honest clients. Typical $m in [f+1, n-f]$.

Why It Matters

• Lower Variance: Averaging multiple selected updates reduces variance compared to single-client Krum.
• Tunable: $m$ controls the trade-off between robustness (lower $m$) and efficiency (higher $m$).
• Practical: Multi-Krum is more practical than Krum for real deployments where variance matters.

Multi-Krum is selecting the most trustworthy committee — choosing the top-$m$ most reliable updates and averaging them for stable, robust aggregation.