Deliverables of the Complex Systems Program

Papers

2009

1. C. Dabrowski and F. Hunt, Using Markov Chain Analysis to Study Dynamic Behavior in Large-Scale Grid Systems, to appear in 7th Australasian Symposium on Grid Computing and e-Research, Wellington, New Zealand, 2009, 20 - 23 January
2. B. Cloteaux "Approximating the number of bases for almost all matroids", submitted to Information Processing Letters.

2008

1. F. Hunt and V. Marbukh, Dynamic Routing and Congestion Control Through Random Assignment of Routes, to appear in Proceedings of the 5th International Conference on Cybernetics and Information Technologies, Systems and Applications: CITSA 2008, Orlando FL, July 2008.
2. I. Beichl and B. Cloteaux, Generating Network Models Using the S-Metric, in Proceedings of the International Conference on Modeling, Simulation and Visualization Methods, Las Vegas, NV, July 2008, pp. 159-164.
3. I. Beichl and B. Cloteaux, Measuring the Effectiveness of the s-Metric to Produce Better Network Models, in Proceedings of the Winter Simulation Conference, Miami FL, Dec 2008, pp. 1020-1028.
4. K. Mills and C. Dabrowski, Can Economics-based Resource Allocation Prove Effective in a Computation Marketplace? in Journal of Grid Computing Special Issue on Grid Economics and Business Models. DOI (10.1007/s10723-007-9094-4)
5. D. Genin and V. Marbukh, Toward Understanding of Metastability in Large-Scale Loss Networks with Mobile Users: Emergence and Implications for Performance. in Proceedings of 12th World Multiconference on Systems, Orlando FL, June 2008.
6. V. Marbukh and K. Mills, Demand Pricing & Resource Allocation in Marketbased Compute Grids: A Model and Initial Results in Proceedings of ICN 2008, April 2008.
7. C. Dabrowski, Reliability in Grid Computing Systems. submitted to the journal Concurrency and Computation: Practice and Experience as part of a special issue on OGF work.
8. V. Marbukh, Can TCP Metastability Explain Cascading Failures and Justify Flow Admission Control in the Internet? in Proceedings of the 15th International Conference on Telecommunications (ICT'08).
9. A. Fillinger, I. Hamchi, S. Degré, L. Diduch, T. Rose, J. Fiscus and V. Stanford. Engineering the Pervasive Future: Common Middleware, Research Corpora, and Metrology. IEEE Pervasive Computing Mobile and Ubiquitous Systems. Accepted for Publication 2008.
10. L. Diduch, M. Hoarau, A. Fillinger, V. Stanford. Synchronization of Data Streams in Distributed Realtime Multimodal Signal Processing Environments on Commodity Hardware. Proceedings of the IEEE International Conference on Multimedia & Expo (ICME), Hannover, Germany, June 2008. Conference talk notes.
11. A. Fillinger, L. Diduch, I. Hamchi, M. Hoarau, S. Degré, V. Stanford. The NIST Data Flow System II: A Standardized Interface for Distributed Multimedia Applications. IEEE International Symposium on a World of Wireless, Mobile and MultiMedia? Networks (WoWMoM?), Newport Beach, California, June 2008 - Awarded best demonstration.

2007

1. V. Marbukh, Towards Understanding of Complex Communication Networks: Performance, Phase Transitions & Control to appear in a special issue of Sigmetrics "Performance Evaluation Review" DRAFT version MAMA07, June 13.
2. V. Marbukh and K. Mills, On Maximizing Provider Revenue in Market-based Compute Grids in Proceedings of ICNS07, June 2007.
3. K. Mills and C. Dabrowski, Investigating Global Behavior in Computing Grids, Self-Organizing Systems, Lecture Notes in Computer Science, Volume 4124 ISBN 978-3-540-37658-3, pp. 120-136, Oct 2007.
4. K. Mills, A Brief Survey of Self-Organization in Wireless Sensor Networks, Wireless Communications and Mobile Computing, Wiley Interscience, Vol. 7, No. 7, (pages 823-834) October 2007.
5. V. Marbukh, S. Klink, Decentralized control of large-scale networks as a game with local interactions: cross-layer TCP/IP optimization, ValueTools, 2nd International Conference on Performance Evaluation Methodologies and Tools, Nance France, Oct 2007.
6. V. Marbukh, Utility Maximization for Resolving Throughput/Reliability Trade-offs in an Unreliable Network with Multipath Routing, ValueTools, 2nd International Conference on Performance Evaluation Methodologies and Tools, Nance France, Oct 2007.
7. V. Marbukh, Metastability of fair bandwidth sharing under fluctuating demand and necessity of flow admission control in Electronics Letters, 13th September 2007, Vol 43, No 19.
8. V. Marbukh, Fair bandwidth sharing under flow arrivals/departures:effect of retransmissions on stability and performance, in ACM SIGMETRICS Performance Evaluation Review, Volume 35 Issue 2, September 2007.
9. C. Dabrowski, Investigating Resource Allocation in a Standards-Based Grid Compute Economy. National Institute of Standards and Technology: Gaithersburg, MD. Interagency Report 7463, November 2007.
10. L. Diduch R. Mueller, G. Rigoll. A framework for modular signal processing systems with high-performance requirements. Proceedings of the IEEE International Conference on Multimedia & Expo (ICME), Beijing, China, July 2007.
11. A. Fillinger, L. Diduch, I. Hamchi, S. Degré and V. Stanford. NIST smart data flow system II: speaker localization. Proceedings of the 6th international conference on Information processing in sensor networks (IPSN), Cambridge, Massachusetts, USA, 2007.

Presentations

1. V. Marbukh Towards Price Based Network Management and Provisioning, internal presentation to the CxS? Study Group, May 6, 2008.
2. J. Filliben, Sensitivity Analysis Methodology for a Complex System Computational Model, 39th Symposium on the Interface: Computing Science and Statistics, Philadelphia, PA, May 26, 2007
3. R. Pozo, A discussion of Statistical Mechanics of Complex Networks by Albert & Barbasi, internal presentation to Complex Systems Study Group, 2007.
4. V. Stanford, Time Series Prediction Forecasting the Future and Understanding the past (PPT). Santa Fe Institute Proceedings on the Studies in the Sciences of Complexity Edited by Andreas Weingend and Neil Gershenfeld. NIST Complex System Program, Perspectives on Standard Benchmark Data, In Quantifying Complex Systems, internal presentation to CxS? Study Group, Complex Systems Test Bed project. August 31, 2007.
5. D. Genin, Percolation: Theory and Applications, internal presentation to Complex Systems Study Group, 2007.
6. S. Degre, L. Diduch, A. Fillinger, I. Hamchi, V. Stanford. Complex System Simulation: Parallel agent based simulation and emergent phenomena, 2007.

Software

1. Flexi-Cluster: A Simulator for a Single Compute Cluster, V. Marbukh and K. Mills.
2. MesoNet: A Mesoscopic Simulation Model of a Router-Level Internet-like Network,
3. MesoNetHS adds six congestion-control algorithms for networks with high bandwidth-delay products; algorithms include: binary-increase control (BIC), compound TCP (CTCP), fast AQM scalable (FAST) TCP, H-TCP, high-speed TCP (HS TCP) and Scalable TCP (STCP), K. Mills, E. Schwartz and J. Yuan.
4. EconoGrid: A detailed Simulation Model of a Standards-based Grid Compute Economy, C. Dabrowski and K. Mills.
5. MesoGrid?: a mesoscopic scale simulation model of a computational grid economy, C. Dabrowski and K. Mills.
6. NGraph++: a simplified graph library for the analysis of complex networks based on ANSI/ISO C++. Includes basic graph operations (construction, intersections, subgraphs) and algorithms for computing degree distribution and clustering coefficients. R. Pozo
7. DiVisa?: a multi-dimensional visualization tool. Can read any kind of data (simulation, statistics, text or numeric, etc.), and converters have been implemented to read several data formats without need for reformatting.
8. The NIST Data Flow System II, a generic cross-platform middleware for parallel process and distributed computing.
9. Distributed processing for multiple instances of Octave or Matlab computational engines for parallel matrix algebra needed in complex system simulations. Provided with the NDFS-II.
10. Distributed simulation architectures for the study of emergent behaviors in large populations of simple agents that form complex systems. The distributed processing was shown to support very large agent population capable of solving large combinatorial optimization problems. Provided with the NDFS-II.
11. The ant colony Engine that simulates the behavior that biological ant colonies show in nature when foraging for food and finding efficient paths from the nest to the food sources. Provided with the NDFS-II.
12. B. Cloteaux , A C++ implementation of a sequential importance sampling algorithm, created by us, for estimating the number of spanning trees in a graph, Sept. 2007.
13. B. Cloteaux , A C++ implementation of various network metrics including minimum vertex cover (MC). Uses several of the kernelization techniques of Langston et al.  The kernelization method involves taking a graph G and producing a smaller graph G', the kernel, with a value k such that MC(G) = MC(G')+k.  For the smaller G' we solve for minimum vertex cover exactly, Feb. 2008.
14. B. Cloteaux , A program for generating random graphs with a given degree sequence. Took code written in R by Joseph Blitzstein at Harvard, converting it to C++, and then optimizing it with the use of novel datastructures.  These datastructures allowed the C++ program to run much larger cases than the original program. In particular, it could then handle the Autonomous Systems data from the UCLA database. Software has been released to J. Blitzstein (Harvard), C. Priebe (Johns Hopkins), J. Devinney (IDA Center for Computing Sciences), March 2008.
15. B. Cloteaux , Software to generate graphs with specified s values. These used the Monte Carlo technique of threshold acceptance, May 2008.
16. B. Cloteaux , Software to calculate the maximum s value for a set of graphs. This includes a new approximation technique we developed, namely a deterministic version of Blitzstein's algorithm to produce the upper bound, May 2008.
17. B. Cloteaux , Software to enumerate all graphs with a given degree sequence.Done for illustration purposes for small graphs, May 2008.
18. B. Cloteaux , C++ implementations of Wilson's algorithm to uniformly sample spanning trees in graphs and Welsh's Monte Carlo algorithm for counting bases of a frequent matroid, Aug. 2008.
19. B. Cloteaux , Software implementing our algorithm, based on sequential importance sampling, to approximate the coefficients of the reliability polynomial of a graph, Sept 2008.
20. B. Cloteaux , A C++ implementation of Colbourn's algorithm to estimate the coefficients of the reliability polynomial, Sept 2008.
21. B. Cloteaux , Software to estimate specific values of the reliability polynomial.  Uses Chernoff bounds to determine convergence.  It produces a graph of connected probability vs edge probability, Sept 2008.

Visualizations

1. Animation of simulation of Abilene network. C. Houard, J. Hagedorn
2. Animations of firefly and pacemaker experiments on NDFS-II testbed L. Diduch
3. Distributed Ant Colony Optimization Simulation is a new method of parallelization based on the NDFS-II middleware. I. Hamchi