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.

Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we consider a given physical network and the measured communication demands between the nodes. Our goal is to augment the given physical network with a matching, so that the shortest path lengths in the augmented network, weighted with the demands, are minimal. We prove that this problem is NP-hard, even if the physical network is a cycle. We then use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching in case that only a few nodes in the network cause almost all the communication. For general real-world communication patterns, we design and evaluate a series of heuristics that can deal with arbitrary graphs as the underlying network structure. Our algorithms are validated experimentally using real-world traces (from e.g., Facebook) of data centers.

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.

Small-world networks are attractive for the efficient routing they provide, requiring only a low link density. They have hence also been considered for the design of distributed systems, such as peer-to-peer networks. However, existing small-world network designs are oblivious to the actual traffic they serve. In this paper, we initiate the study of demand-aware small-world networks. In particular, we extend the Kleinberg graph model, by allowing the nodes to choose the distribution of long-range links according to the traffic demand. We present a formal analysis of the weighted route lengths for the important case of clustered demands. We show both in theory and in simulations, using real-world traffic workloads, that demand-aware small-world graphs can significantly outperform their demand-oblivious counterparts.

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.

In this paper, we present distributed fault-tolerant algorithms that approximate the centroid (i.e., the average) of a set of n data points in $$\mathbb {R}^d$$ . Our work falls into the broader area of multidimensional Byzantine approximate agreement. We show that state-of-the-art algorithms, such as agreeing inside the convex hull of all non-faulty vectors, or minimum-diameter averaging (MDA), in the worst case either prevent us from agreeing on a vector close to the centroid (in terms of approximation quality), or allow Byzantine parties to influence the output considerably (in terms of validity). To design better approximation algorithms, we propose a novel concept of defining an approximation ratio of the centroid by including the vectors of the Byzantine adversaries in the definition. We analyze synchronous algorithms in the public channel communication model. We show that the standard agreement algorithms based on agreeing inside the convex hull of all non-faulty vectors do not allow us to compute a better approximation than 2d of the centroid. On the other hand, MDA can be used to achieve constant approximation at the cost of only satisfying strong validity. As a trade-off, we develop an approach that reaches a $$2\sqrt{d}$$ -approximation of the centroid, while satisfying box validity. Our approach provides optimal resilience, allowing up to $$t

We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: 1. All LCL problems solvable with locality $O(\log^\star n)$ in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality $O(1)$. This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. 2. In rooted trees, if we can solve an LCL problem with locality $o(\log \log \log n)$ in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality $O(\log^\star n)$ in the classical deterministic LOCAL model. One of many implications is that in rooted trees, $O(\log^\star n)$ locality in quantum-LOCAL is not stronger than $O(\log^\star n)$ locality in classical LOCAL.

Peer review, as a widely used practice to ensure the quality and integrity of publications, lacks a well-defined and common mechanism to self-incentivize virtuous behavior across all the conferences and journals. This is because information about reviewer efforts and author feedback typically remains local to a single venue, while the same group of authors and reviewers participate in the publication process across many venues. Previous attempts to incentivize the reviewing process assume that the quality of reviews and papers authored correlate for the same person, or they assume that the reviewers can receive physical rewards for their work. In this paper, we aim to keep track of reviewing and authoring efforts by users (who review and author) across different venues while ensuring self-incentivization. We show that our system, DecentPeeR, incentivizes reviewers to behave according to the rules, i.e., it has a unique Nash equilibrium in which virtuous behavior is rewarded.

In the well-known Minimum Linear Arrangement problem (MinLA), the goal is to arrange the nodes of an undirected graph into a permutation so that the total stretch of the edges is minimized. This paper studies an online variant of MinLA where the graph is not given at the beginning, but rather revealed piece-by-piece. The algorithm starts in a fixed initial permutation, and after a piece of the graph is revealed, the algorithm must update its current permutation to be a MinLA of the subgraph revealed so far. The objective is to minimize the total number of swaps of adjacent nodes as the algorithm updates the permutation. The main result of this paper is an online randomized algorithm that solves the online MinLA problem for the restricted cases where the graph is either a collection of cliques or a collection of lines. We show that the algorithm is$8\ ln n$- competitive, where$n$is the number of nodes of the graph. We complement this result by constructing a lower bound of$\Omega(\ln (n)$for competitiveness of any online algorithm, concluding that our randomized algorithm is asymptotically optimal.

Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we differentiate between a given physical network and the measured communication demands between the nodes. Our goal is to minimize the weighted average shortest path length via matching augmentation, where the weights correspond to the communication frequency of any pair of nodes. We use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching on a ring in case only a few nodes in the network cause almost all the communication. Since the problem is NP-hard, we design and evaluate a series of heuristics that can deal with arbitrary graphs as underlying network structures. We evaluate our heuristics on general real-world communication patterns and show that already with simple and efficient heuristics we are able to reach near-optimal quality.

In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a new model of computing, called the online-LOCAL model: the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node we get to see its radius-T neighborhood before choosing the output. We compare the online-LOCAL model with three other models: the LOCAL model of distributed computing, where each node produces its output based on its radius-T neighborhood, its sequential counterpart SLOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-T neighborhood of the point of change. The SLOCAL and dynamic-LOCAL models are sandwiched between the LOCAL and online-LOCAL models, with LOCAL being the weakest and online-LOCAL the strongest model. In general, all models are distinct, but we study in particular locally checkable labeling problems (LCLs), which is a family of graph problems studied in the context of distributed graph algorithms. We prove that for LCL problems in paths, cycles, and rooted trees, all models are roughly equivalent: the locality of any LCL problem falls in the same broad class - $O(\log^* n)$, $Θ(\log n)$, or $n^{Θ(1)}$ - in all four models. In particular, this result enables one to generalize prior lower-bound results from the LOCAL model to all four models, and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in the LOCAL model. We also show that this equivalence does not hold in general bipartite graphs. We provide an online-LOCAL algorithm with locality $O(\log n)$ for the $3$-coloring problem in bipartite graphs - this is a problem with locality $Ω(n^{1/2})$ in the LOCAL model and $Ω(n^{1/10})$ in the SLOCAL model.

In this paper, we study the notion of mending: given a partial solution to a graph problem, how much effort is needed to take one step towards a proper solution? For example, if we have a partial coloring of a graph, how hard is it to properly color one more node? In prior work (SIROCCO 2022), this question was formalized and studied from the perspective of mending radius: if there is a hole that we need to patch, how far do we need to modify the solution? In this work, we investigate a complementary notion of mending volume: how many nodes need to be modified to patch a hole? We focus on the case of locally checkable labeling problems (LCLs) in trees, and show that already in this setting there are two infinite hierarchies of problems: for infinitely many values 0 < α ≤ 1, there is an LCL problem with mending volume Θ(n^α), and for infinitely many values k ≥ 1, there is an LCL problem with mending volume Θ(log^k n). Hence the mendability of LCL problems on trees is a much more fine-grained question than what one would expect based on the mending radius alone.

In this paper, we present tight bounds for the k-server problem with delays in the uniform metric space. The problem is defined on n+k nodes in the uniform metric space which can issue requests over time. These requests can be served directly or with some delay using k servers, by moving a server to the corresponding node with an open request. The task is to find an online algorithm that can serve the requests while minimizing the total moving and delay costs. We first provide a lower bound by showing that the competitive ratio of any deterministic online algorithm cannot be better than (2k+1) in the clairvoyant setting. We will then show that conservative algorithms (without delay) can be equipped with an accumulative delay function such that all such algorithms become (2k+1)-competitive in the non-clairvoyant setting. Together, the two bounds establish a tight result for both, the clairvoyant and the non-clairvoyant settings.

This paper presents a novel shared memory model that simplifies the analysis of consensus on a Chain and a DAG. In this new model, referred to as the append memory model, nodes are allowed to write new values to the unordered memory, but not to overwrite already existing values. We show that although this model differs from the standard shared memory model with n shared read-write registers, many known results from the shared memory model still hold in the append memory model: It is, for example, impossible to establish consensus on n nodes with one crash failure if the nodes in the system are asynchronous. We also consider the append memory model in a synchronous setting with Byzantine failures. For this case, we show that Byzantine agreement cannot be solved in less than t+1 rounds, where t is the number of Byzantine nodes in the system. Assuming a probabilistic access restriction to the append memory, we compare the Byzantine agreement protocols on the Chain and the DAG. We show that the DAG structure achieves an almost optimal resilience (close to t<n/2) in contrast to the Chain structure that can tolerate less than t

Human activity recognition from raw sensor data has enabled modern wearable devices to track and analyze everyday activities. However, when used in real world conditions, the performance of off-the-shelf devices is often insufficient. This paper tackles the problem of swimming style recognition and lap counting using sensor data from a single smartwatch. In total 17 hours of this data was collected from 40 swimmers of diverse backgrounds. The data was then used to train a convolutional neural network to recognize the four main swimming styles, transition periods and lap turns. Our method achieves an F1 score of 97.4% for style recognition and 99.2% for counting laps. To the best of our knowledge, these results are the first to enable accurate automatic swimming recognition in a realistic and completely uncontrolled environment.

To solve Byzantine agreement, n nodes with real input values, among which t <; n/3 are Byzantine, have to agree on a common consensus value. Previous research has mainly focused on determining a consensus value equal to an input value of some arbitrary node. In this work we instead assume that the values of the nodes are ordered and introduce a novel validity condition which accepts consensus values that are close to the k-th smallest value of the correct nodes. We propose a deterministic algorithm that approximates the k-th smallest value and show that this approximation is the best possible for the synchronous message passing model. Our approach is furthermore extended to multiple dimensions, where the order is not well-defined, and we show that our algorithm can be applied to determine a value that lies within a box around all correct input vectors.