Scaling topology pattern matching: A distributed approach

Michael Stein, Alexander Frömmgen, Roland Kluge, Lin Wang, Augustin Wilberg, Boris Koldehofe, Max Mühlhäuser

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


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. This paper presents the first algorithm for distributed topology pattern matching, enabling pattern matching beyond the local view. Outgoing from initiating devices, our pattern matcher delegates the matching procedure to further devices in the network. Exploring major contextual parameters of our algorithm, we show that the optimal local view size depends on scenario-specific conditions. Our pattern matcher provides the flexibility for adaptations of the local view size at runtime. Making use of this flexibility, we optimize the execution of an established pattern-based algorithm and evaluate our pattern matcher in two topology control case studies for the Internet of Things. By scaling the view size of each device in a distributed way, our adaptive approach achieves significant communication cost savings in face of dynamic conditions.

Original languageEnglish
Title of host publicationProceedings of the 33rd Annual ACM Symposium on Applied Computing, SAC 2018
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450351911
Publication statusPublished - 9 Apr 2018
Externally publishedYes
Event33rd Annual ACM Symposium on Applied Computing, SAC 2018 - Pau, France
Duration: 9 Apr 201813 Apr 2018

Publication series

NameProceedings of the ACM Symposium on Applied Computing


Conference33rd Annual ACM Symposium on Applied Computing, SAC 2018


  • Graph pattern matching
  • Locality control
  • Topology control


Dive into the research topics of 'Scaling topology pattern matching: A distributed approach'. Together they form a unique fingerprint.

Cite this