How long it takes for an ordinary node with an ordinary ID to output?

DOI10.1007/978-3-319-72050-0_16zbMath1437.68021arXiv1704.05739OpenAlexW2607170537WikidataQ128539944 ScholiaQ128539944MaRDI QIDQ5916003

Laurent Feuilloley

Publication date: 12 April 2018

Published in: Theoretical Computer Science, Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.05739

zbMATH Keywords

colouringaverage complexitydistributed network algorithmLCLrandom identifiers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items

Node and edge averaged complexities of local graph problems ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ How long it takes for an ordinary node with an ordinary ID to output?

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• What Can be Computed Locally?
• Introduction to Testing Graph Properties
• Randomized minimum spanning tree algorithms using exponentially fewer random bits
• Distributed (∆+1)-coloring in sublogarithmic rounds
• A lower bound for the distributed Lovász local lemma
• Brief Announcement
• LCL Problems on Grids
• Towards a complexity theory for local distributed computing
• Limits of local algorithms over sparse random graphs
• How long it takes for an ordinary node with an ordinary ID to output?

This page was built for publication: How long it takes for an ordinary node with an ordinary ID to output?