Scaling topology pattern matching
Michael Stein, Alexander Frömmgen, Roland Kluge, Lin Wang, Augustin Wilberg, Boris Koldehofe, Max Mühlhäuser · 2018
Graph pattern matching in network topologies is a building block of many distributed algorithms. Based on a limited local view of the topology, pattern-based algorithms substantiate the decision-making of each device on the occurrence of graph patterns in its surrounding topology. Existing pattern-based algorithms require that each device has a sufficiently large local view to match patterns without support of other devices. In practical environments, the local view is often restricted to one hop. Thus, algorithms matching non-trivial patterns are locked out from such environments today.