We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the longstanding O(log n)round "barrier" achieved by Luby's algorithm, but these yield o(log n)round complexity only when the maximum degree Delta is somewhat small relative to n. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still O(log n) (via Luby's algorithm) even for moderately small Delta (i.e., for Delta = Omega(log n) and Delta = o(n)). Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby's algorithm takes O(m) messages on medge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the Theta(log n) time complexity barrier and the Theta(m) message complexity barrier in the Congest model for MIS or closelyrelated symmetry breaking problems? This papermore »
Consensus with Max Registers
We consider the problem of implementing randomized waitfree consensus from max registers under the assumption of an oblivious adversary. We show that max registers solve mvalued consensus for arbitrary m in expected O(log^* n) steps per process, beating the Omega(log m/log log m) lower bound for ordinary registers when m is large and the best previously known O(log log n) upper bound when m is small. A simple maxregister implementation based on doublecollect snapshots translates this result into an O(n log n) expected step implementation of mvalued consensus from n singlewriter registers, improving on the best previouslyknown bound of O(n log^2 n) for singlewriter registers.
 Publication Date:
 NSFPAR ID:
 10120845
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 146
 Page Range or eLocationID:
 1:11:9
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the longstanding O(log n)round “barrier” achieved by Luby’s algorithm, but these yield o(log n)round complexity only when the maximum degree is somewhat small relative to n. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still O(log n) (via Luby’s algorithm) even for moderately small (i.e., for = (log n) and = o(n)). Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby’s algorithm takes O(m) messages on medge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the (log n) time complexity barrier and the (m) message complexity barrier in the Congest model for MIS or closelyrelated symmetry breaking problems? This papermore »

We consider the problem of simulating a kvalued register in a wait free manner using binary registers as building blocks, where k > 2. We show that for any simulation using atomic binary base registers to simulate a safe kvalued register in which the read algorithm takes the optimal number of steps (log_2 k), the write algorithm must take at least log k steps in the worst case. A fortiori, the same lower bound applies when the simulated register should be regular. Previously known algorithms show that both these lower bounds are tight. We also show that in order to simulate an atomic k valued register for two readers, the optimal number of steps for the read algorithm must be strictly larger than log_2 k.

Nikhil, Bansal ; Nagarajan, Viswanath (Ed.)We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely MaxDICUT, for which random ordering makes a provable difference. Whereas a 4/9 ≈ 0.445 approximation of DICUT requires space with adversarial ordering, we show that with random ordering of constraints there exists a 0.483approximation algorithm that only needs O(log n) space. We also give new algorithms for MaxDICUT in variants of the adversarial ordering setting. Specifically, we give a twopass O(log n) space 0.483approximation algorithm for general graphs and a singlepass space 0.483approximation algorithm for boundeddegree graphs. On the negative side, we prove that CSPs where the satisfying assignments of the constraints support a onewise independent distribution require space for any nontrivial approximation, even when the constraints are randomly ordered. This was previously known only for adversarially ordered constraints. Extending the results to randomly ordered constraints requires switching the hard instances from a union of random matchings to simple ErdősRenyi random (hyper)graphs and extending tools that can perform Fourier analysis on such instances. The only CSP to have been considered previously with random ordering is MaxCUT where the ordering is notmore »

This paper revisits the kmismatch shortest unique substring finding problem and demonstrates that a technique recently presented in the context of solving the kmismatch average common substring problem can be adapted and combined with parts of the existing solution, resulting in a new algorithm which has expected time complexity of O(n log^k n), while maintaining a practical space complexity at O(kn), where n is the string length. When , which is the hard case, our new proposal significantly improves the anycase O(n^2) time complexity of the prior best method for kmismatch shortest unique substring finding. Experimental study shows that our new algorithm is practical to implement and demonstrates significant improvements in processing time compared to the prior best solution's implementation when k is small relative to n. For example, our method processes a 200 KB sample DNA sequence with k=1 in just 0.18 seconds compared to 174.37 seconds with the prior best solution. Further, it is observed that significant portions of the adapted technique can be executed in parallel, using two different simple concurrency models, resulting in further significant practical performance improvement. As an example, when using 8 cores, the parallel implementations both achieved processing times that are less thanmore »