Multidimensional Approximate Agreement (D-AA) considers a setting with n parties with inputs in ℝD. Out of the n parties, up to t may be byzantine (malicious). The goal is for the honest parties to obtain ϵ-close outputs that lie in the convex hull of the honest inputs.

Demand-aware reconfigurable datacenter networks adapt toward the traffic they serve by providing topological shortcuts between frequently communicating racks. However, only little is known about computing optimized demand-aware networks quickly and in a distributed manner. In this paper, we investigate fast distributed algorithms to compute demand-aware networks for hybrid datacenters, where a fixed capacitated network can be enhanced with a bounded-degree demand-aware network, i.e., with a set of matchings created by optical circuit switches. We make two main contributions. Firstly, we present a distributed algorithm, called the Coordinator algorithm for computing demand-aware networks on all underlying topologies. The algorithm is analyzed in the widely deployed Clos topology and in the Congested Clique model, where it is optimal in terms of quality and nearly optimal in distributed runtime. Secondly, we focus on improving the round complexity at the cost of the quality of the resulting topology. We show that for tree demands, an adaptation of a distributed matching algorithm by Wattenhofer and Wattenhofer (DISC 2004) achieves a$1 / 6$-approximation. Based on this approach, we introduce the Propose and REJECT algorithm for general demands, which we evaluate on real-world Facebook datacenter and HPC traces. Our results show that the Propose and REJECT algorithm, even with limited knowledge of the demand matrix, performs nearly optimally on real traffic demands and covers over 80 % of the demand. This is achieved with significantly fewer communication rounds than the optimal solution computed by the Coordinator algorithm.

In Byzantine collaborative learning, n clients in a peer-to-peer network collectively learn a model without sharing their data by exchanging and aggregating stochastic gradient estimates. Byzantine clients can prevent others from collecting identical sets of gradient estimates. The aggregation step thus needs to be combined with an efficient (approximate) agreement subroutine to ensure convergence of the training process. In this work, we study the geometric median aggregation rule for Byzantine collaborative learning. We show that known approaches do not provide theoretical guarantees on convergence or gradient quality in the agreement subroutine. To satisfy these theoretical guarantees, we present a hyperbox algorithm for geometric median aggregation. We practically evaluate our algorithm in both centralized and decentralized settings under Byzantine attacks on non-i.i.d. data. We show that our geometric median-based approaches can tolerate sign-flip attacks better than known mean-based approaches from the literature.