Theoretical Results Regarding High Level Architecture Data Distribution
Management

Abstract:

The High Level Architecture (HLA) is an architecture for constructing
distributed simulations.  The Data Distribution Management (DDM) services
of HLA reduce the amount of data delivered to an HLA federate by allowing
communications connections to be based on federates' expressions of data
production and requirements.  HLA Run-Time Infrastructure determines
the data connections in a federation based on those expressions (called
"matching") and configures the network infrastructure to deliver data
along those connections (called "connecting").   The definition of HLA
in general, and DDM in particular, has changed from the previous DoD
1.3 version to the new IEEE 1516 version of the HLA specifications.
Three theorems regarding HLA DDM are proven.

Theorem 1:   A lower bound for any algorithm performing HLA DDM matching
is in ((n log n); this is proven by reduction from BINARY SEARCH.
Theorem 2:  The multicast grouping problem, which is often used for
HLA DDM connecting, is NP-complete; this is proven by transformation
from 3-PARTITION.  Theorem 3:  The new IEEE 1516 specification of HLA
DDM is at least as powerful, in terms of representable configurations,
as the old DoD 1.3 specification of HLA DDM; this is proven by exhibiting
an equivalence-preserving transformation from DDM 1.3 configurations to
DDM 1516 configurations.

Biography:

Mikel D. Petty is Chief Scientist of the Virginia Modeling, Analysis and
Simulation Center of Old Dominion University.  He worked previously at
the University of Central Florida's Institute for Simulation and Training.
He has been performing and leading modeling and simulation research since
1990.  He received a Ph.D. from the University of Central Florida (UCF) in

1997, an M.S.  from UCF in 1988, and a B.S. from the California State
University Sacramento in 1980, all in Computer Science.  His research
interests are in distributed simulation interoperability, computer
generated forces, multi-resolution simulation, and applications of
computational geometry to simulation.  During 10 years in the research
field he has published 80 research papers in those areas and has been
awarded over 35 research contracts.