The discrete incremental voting process (DIV), introduced by Cooper, Radzik, and Shiraga [OPODIS '23], operates on an undirected graph where each node has an integer opinion. In one step a randomly selected node interacts with its randomly selected neighbor and changes its opinion by 1 towards the neighbor's opinion. The final consensus opinion has expectation equal to the degree-weighted average of the initial opinions. We show that for graphs with n nodes, conductance Φ, and the ratio of the average to smallest degree γ, if the maximal difference between initial opinions is K, then the expected convergence time is O(n (K log(Kn) + γn)/Φ2). This bound is essentially optimal for graphs of bounded expansion. We also show that for regular graphs, if the second largest eigenvalue (in absolute value) is o(1/log2 n) and K is o(n/log2 n), then w.h.p. DIV converges to the rounded initial average opinion.

We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given n anonymous agents, and the goal is to assign each agent a unique rank in {1,…,n}. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well.Ranking requires at least n states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only n+O(logn) states. Our protocol stabilizes in O(n2logn) interactions w.h.p. and in expectation, using n + O(log2n) states in total. Our stabilization time is asymptotically optimal (see Burman et al., PODC ’21). In comparison to the currently best known ranking protocol by Burman et al., which requires n + Ω(n) states, our result exponentially improves the number of overhead states.

We consider the distributed and parallel construction of low-diameter decompositions with strong diameter. We present algorithms for arbitrary undirected, weighted graphs and also for undirected, weighted graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor K_r. Our algorithms work in the PRAM, CONGEST, and the novel HYBRID communication model and are competitive in all relevant parameters. Given 𝒟 > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter 𝒟. For an arbitrary graph, an edge e ∈ E of length 𝓁_e is cut between two clusters with probability O(𝓁_e⋅log(n)/𝒟). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(𝓁_e⋅log(log n)/𝒟). In either case, the decompositions can be computed in Õ(1) depth and Õ(m) work in the PRAM and Õ(1) time in the HYBRID model. In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC '22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting.

We consider the problem of self-stabilizing leader election in the population model by Angluin et al. (JDistComp '06). The population model is a well-established and powerful model for asynchronous, distributed computation with a large number of applications. For self-stabilizing leader election, the population of n anonymous agents, interacting in uniformly random pairs, must stabilize with a single leader from any possible initial configuration.

Abstract. In an influential article, Papadimitriou [ On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 163–169] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with [Formula: see text] variables in [Formula: see text] expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (see, e.g., [Hoos and Stützle, J. Autom. Reason., 24 (2000), pp. 421–481]). In the present article, we analyze the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [ SIAM J. Comput., 36 (2007) pp. 1248–1263], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.

We consider the problem of computing a compact routing scheme for a weighted undirected planar graph G := (V, E, w) in several models. For a given parameter ϵ > 0, we compute a routing scheme with stretch 1 + ϵ and labels and routing tables of size Õ(ϵ−1). In CONGEST, the construction takes Õ(ϵ−3 · HD) time, where HD denotes the network's hop-diameter. Further, it takes Õ(ϵ−3) time in a PRAM with O(n) processors and the novel HYBRID model. Thus, our algorithms are almost optimal in all relevant parameters. To achieve these results, we extend the divide-and-conquer framework of Li and Parter [STOC '19] and combine it with state-of-the-art distributed distance approximation algorithms [STOC '22].

Abstract This article shows how to construct an overlay network of constant degree and diameter $$O(\log n)$$ O ( log n ) in $$O(\log n)$$ O ( log n ) time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. Suppose the initial network’s graph is weakly connected and has constant degree. In that case, our algorithm constructs the desired topology with each node sending and receiving only $$O(\log n)$$ O ( log n ) messages in each round in $$O(\log n)$$ O ( log n ) time w.h.p., which beats the currently best $$O(\log ^{3/2} n)$$ O ( log 3 / 2 n ) time algorithm of Götte et al. (International colloquium on structural information and communication complexity (SIROCCO), Springer, 2019). Since the problem cannot be solved faster than by using pointer jumping for $$O(\log n)$$ O ( log n ) rounds (which would even require each node to communicate $$\Omega (n)$$ Ω ( n ) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of Kwok and Lau (Approximation, randomization, and combinatorial optimization. Algorithms and techniques (APPROX/RANDOM 2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014). Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks (Augustine et al. in Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, SIAM, 2020). Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm’s execution. For an (undirected) graph G with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in $$O(\log n)$$ O ( log n ) time w.h.p. Furthermore, we show how to compute an MIS in $$O(\log d + \log \log n)$$ O ( log d + log log n ) time w.h.p., where d is the initial degree of G .

We present a new model for (asynchronous) byzantine reliable broadcast to investigate the potential of secret collusion between honest players. To model the collusion, we assume that each honest player has k > 1 distinct communication identities over which they can send and receive messages. A player can obtain these identities - for example - by joining a distributed system under several aliases.

We show how to construct an overlay network of constant degree and diameter O(log n) in time O(log n) starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of and establish new connections by sending node identifiers. If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in time O(log n), w.h.p., which beats the currently best O(log3/2 n) time algorithm of [Götte et al., SIROCCO'19]. Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Ω(n) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX'14].

We investigate the maintenance of overlay networks under massive churn where an adversary may churn a constant fraction αn of nodes over the course of O(logn) rounds. In particular, the adversary has an almost up-to-date information of the network topology as it can observe an only slightly outdated topology that is at least 2 rounds old. Other than that, we only have the provably minimal restriction that new nodes can only join the network via nodes that have taken part in the network for at least one round. Our contributions are as follows: First, we show that it is impossible to maintain a connected topology if the adversary has up-to-date information about the nodes' connections. As our main result, we present an algorithm that constructs a new overlay - completely independent of all previous overlays - every 2 rounds. Furthermore, each node sends and receives only O(log3n) messages in each round. As part of our solution, we propose the Linearized DeBruijn Swarm (LDS), a highly churn resistant overlay, which will be maintained by the algorithm. However, our approaches can be transferred to a variety of classical P2P topologies where nodes are mapped into the [0,1)-interval.