We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in Õ(n) rounds and each node is awake during only poly(log n) rounds. When a node is not awake, it performs no computations or communications and spends no energy.

We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the maximal matching to these updates in poly(łog n) depth and using poly(łog n) amortized work per update. That is, the amortized work for processing a batch of k updates is k poly(łog n), while all this work is done in poly(łog n) depth, with high probability. This can be seen as a parallel counterpart of the sequential dynamic algorithms for constant-approximate and maximal matching [Onak and Rubinfeld STOC'10; Baswana, Gupta, and Sen FOCS'11; and Solomon FOCS'16]. Our algorithm readily generalizes to maximal matching in hypergraphs of rank r---where each hyperedge has at most r endpoints---with a poly(r) increase in work, while retaining the poly(łog n) depth.

We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm A that has time complexity T and message complexity M in the synchronous message-passing model (subject to some care in defining the model), the synchronizer provides a distributed algorithm A′ that runs in the asynchronous message-passing model with time complexity T · poly(log n) and message complexity (M + m) · poly(log n). Here, n and m denote the number of nodes and edges in the network, respectively. The synchronizer is deterministic in the sense that if algorithm A is deterministic, then so is algorithm A′. Previously, only a randomized synchronizer with near-optimal overheads was known by seminal results of Awerbuch, Patt-Shamir, Peleg, and Saks [STOC 1992] and Awerbuch and Peleg [FOCS 1990]. We also point out and fix some inaccuracies in these prior works.