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.

Assigning applicants to posts in the presence of the preferences of applicants and quotas associated with posts is extensively investigated. For a post, lower quota guarantees, and upper quota limits the number of applicants assigned to it. Typically, quotas are assumed to be fixed, which need not be the case in practice. We address this by introducing a soft quota setting, in which every post is associated with two values – lower target and upper target which together denote a range for the intended number of applicants in any assignment. Unlike the fixed quota setting, we allow the number of applicants assigned to a post to fall outside the range. This leads to assignments with deviation. Here, we study the problem of computing an assignment that has two orthogonal optimization objectives – minimizing the deviation (maximum or total) w.r.t. soft quotas and ensuring optimality w.r.t. preferences of applicants (rank-maximality or fairness). The order in which these objectives are considered, the different possibilities to optimize deviation combined with the well-studied notions of optimality w.r.t. preferences open up a range of optimization problems of practical importance. We present efficient algorithms based on flow-networks to solve these optimization problems.