Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs

DOI10.1016/j.tcs.2016.11.018zbMath1382.68017OpenAlexW2549442734MaRDI QIDQ1686112

Klaus-Tycho Foerster, Roger Wattenhofer, Thomas Luedi, Jochen Seidel

Publication date: 20 December 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.11.018

zbMATH Keywords

acyclicitysoftware-defined networking\(s\)-\(t\) reachabilitylocal checking

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (8)

Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ A hierarchy of local decision ⋮ Randomized proof-labeling schemes ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Fast distributed algorithms for testing graph properties ⋮ Approximate proof-labeling schemes ⋮ Proof labeling schemes for reachability-related problems in directed graphs

Cites Work

• Unnamed Item
• The local detection paradigm and its applications to self-stabilization
• Node labels in local decision
• Optimal consistent network updates in polynomial time
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Bounds in the propagation of selection into logic programs
• Distributed verification of minimum spanning trees
• Randomized distributed decision
• Proof labeling schemes
• Scheduling Loop-free Network Updates
• Randomized Proof-Labeling Schemes
• Transiently Consistent SDN Updates: Being Greedy is Hard
• Locally checkable proofs
• Anonymous networks
• Distributedly Testing Cycle-Freeness
• Reachability is harder for directed than for undirected finite graphs
• Distributed Verification and Hardness of Distributed Approximation
• What can be decided locally without identifiers?
• What can be computed locally?
• Towards a complexity theory for local distributed computing
• On the Impact of Identifiers on Local Decision

This page was built for publication: Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs