The computational complexity of the high level architecture data distribution management matching and connecting processes

The High Level Architecture (HLA) is an architecture standard for constructing federations of distributed simulations that exchange data at run-time. HLA includes interest management capabilities (known as “Data Distribution Management”) that reduce the data sent during a federation execution using the simulationsʹ run-time declarations describing the data they plan to send and wish to receive. The total computation associated with Data Distribution Management during the execution of a federation can be separated into four processes: declaring, matching, connecting, and routing. These processes are defined and the computational complexities of the matching and connecting processes during a federation execution are determined. The matching process requires total time with a lower bound in Ω(nlogn) and an upper bound in O(n2), where n is the number of run-time data distribution actions performed by the simulations. The commonly used approach to implementing the connecting process, multicast grouping, contains a problem that is NP-complete.