This paper presents gossip algorithms for aggregation tasks that demonstrate both robustness to adversarial corruptions of any order of magnitude and optimality across a substantial range of these corruption levels. Gossip algorithms distribute information in a scalable and efficient way by having random pairs of nodes exchange small messages. Value aggregation problems are of particular interest in this setting, as they occur frequently in practice, and many elegant algorithms have been proposed for computing aggregates and statistics such as averages and quantiles. An important and well-studied advantage of gossip algorithms is their robustness to message delays, network churn, and unreliable message transmissions. However, these crucial robustness guarantees only hold if all nodes follow the protocol and no messages are corrupted. In this paper, we remedy this by providing a framework to model both adversarial participants and message corruptions in gossip-style communications by allowing an adversary to control a small fraction of the nodes or corrupt messages arbitrarily. Despite this very powerful and general corruption model, we show that robust gossip algorithms can be designed for many important aggregation problems. Our algorithms guarantee that almost all nodes converge to an approximately correct answer with optimal efficiency and essentially as fast as without corruptions. The design of adversarially-robust gossip algorithms poses completely new challenges. Despite this, our algorithms remain very simple variations of known non-robust algorithms with often only subtle changes to avoid non-compliant nodes gaining too much influence over outcomes. While our algorithms remain simple, their analysis is much more complex and often requires a completely different approach than the non-adversarial setting.

We study push-pull rumour spreading in ultra-small-world models for social networks where the degrees follow a power-law distribution. In a non-geometric setting, Fountoulakis, Panagiotou and Sauerwald have shown that rumours always spread ultra-fast (SODA 2012). On the other hand, Janssen and Mehrabian have found that rumours spread slowly in a spatial preferential attachment model (SIDMA 2017). We study the question systematically for the model of Geometric Inhomogeneous Random Graphs (GIRGs), which has been found to be a good theoretical and empirical fit for social networks. Our results are two-fold: first, with classical Euclidean geometry slow, fast and ultra-fast (i.e., polynomial, polylogarithmic and doubly logarithmic number of rounds) rumour spreading may occur, depending on the exponent of the power law and the strength of the geometry in the network, and we fully characterise the phase boundaries between these regimes. The regimes do not coincide with the graph distance regimes, i.e., polylogarithmic or even polynomial rumour spreading may occur even if graph distances are doubly logarithmic. We expect these results to hold with little effort for related models, e.g. Scale-Free Percolation. Second, we show that rumour spreading is always (at least) fast in a nonmetric geometry. The considered non-metric geometry allows to model social connections where resemblance of vertices in a single attribute, such as familial kinship, already strongly indicates the presence of an edge. Classical Euclidean geometry fails to capture such ties.

We present the first rigorous analysis of decentralized geometric routing in Geometric Inhomogeneous Random Graphs (GIRGs), a weight-agnostic variant of the greedy routing protocol. While greedy routing in GIRGs is known to explain the algorithmic small-world phenomenon by finding ultra-short paths of length Θ(log log n), it assumes additional knowledge of vertex weights beyond geometry, an assumption that is often restrictive or unavailable. We investigate whether the underlying geometry alone is sufficient for efficient navigation. We prove that for power-law weight exponent τ ∈ (2,3) and geometric decay parameter α > τ-1, geometric routing succeeds with constant probability and finds ultra-short paths of length Θ(log log n), matching the optimal asymptotic guarantees for greedy routing. Our analysis further reveals that, upon success, both protocols follow a similar two-phase trajectory, consisting of a rapid ascent to the heavy vertices, followed by efficient navigation to the target. These results demonstrate that, in the appropriate regime, the network’s geometry alone implicitly guides the path to the target through its high-weight core.

We study the (1:s+1) success rule for controlling the population size of the (1,λ)-EA. It was shown by Hevia Fajardo and Sudholt that this parameter control mechanism can run into problems for large s if the fitness landscape is too easy. They conjectured that this problem is worst for the OneMax benchmark, since in some well-established sense OneMax is known to be the easiest fitness landscape. In this paper, we disprove this conjecture. We show that there exist s and ɛ such that the self-adjusting (1,λ)-EA with the (1:s+1)-rule optimizes OneMax efficiently when started with ɛn zero-bits, but does not find the optimum in polynomial time on Dynamic BinVal. Hence, we show that there are landscapes where the problem of the (1:s+1)-rule for controlling the population size of the (1,λ)-EA is more severe than for OneMax. The key insight is that, while OneMax is the easiest function for decreasing the distance to the optimum, it is not the easiest fitness landscape with respect to finding fitness-improving steps.

We study the (1,λ)-EA with mutation rate c/n for c≤1, where the population size is adaptively controlled with the (1:s+1)-success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c=1 is efficient on OneMax for s<1, but inefficient if s≥18. Surprisingly, the hardest part is not close to the optimum, but rather at linear distance. We show that this behavior is not specific to OneMax. If s is small, then the algorithm is efficient on all monotone functions, and if s is large, then it needs super-polynomial time on all monotone functions. In the former case, for c<1 we show a O(n) upper bound for the number of generations and O(nlog⁡n) for the number of function evaluations, and for c=1 we show O(nlog⁡n) generations and O(n2log⁡log⁡n) evaluations. We also show formally that optimization is always fast, regardless of s, if the algorithm starts in proximity of the optimum. All results also hold in a dynamic environment where the fitness function changes in each generation. An extended abstract, containing only the results without proofs, has been published at the PPSN conference [1].