Zahra Nikdel

Topic

Ergodicity in Software Systems

Department of Electrical and Computer Engineering

Date & location

• Friday, August 30, 2024
• 9:00 A.M.
• Virtual Defence

Examining Committee

Supervisory Committee

• Dr. Stephen Neville, Department of Electrical and Computer Engineering, University of Victoria (Supervisor)
• Dr. Michael McGuire, Department of Electrical and Computer Engineering, UVic (Member)
• Dr. Sudhakar Ganti, Department of Computer Science, UVic (Outside Member)

External Examiner

• Dr. Hamzeh Khazaei, Department of Electrical Engineering and Computer Science, York University

Chair of Oral Examination

• Dr. Justin Albert, Department of Physics and Astronomy, UVic

Abstract

This dissertation applies dynamical systems theory (DST) to formally investigate the statistical run-time performance predictability of arbitrary scale software-centric systems, ranging from small-scale embedded systems to modern large-scale cloud-deployed container and virtual machine based distributed systems. The research focuses on verifying Birkhoff’s Ergodic Theorem (BET) compliance for queuing network (QN) models of deployed software systems against BET-compliant Poisson and bursty incoming workloads. The approach applies a previously developed extension of Maurer’s Turing-reducible computer model, termed the Extended Maurer Model (EMM), as the requisite bridge between classical QN software system models and the DST-based BET tenets underlying classical Markovian QN analysis approaches. Moreover, it is shown that as the EMM describes a σ-finite measure space, a known ergodicity equivalency theorem can be used to develop a formal DST analysis approach to prove when BET left-hand and right-hand side conditions can be met for run-time software systems performance measures. More specifically, formally proving recurrence holds within large-scale systems, as required by classical Markovian analyses, has remained an open problem. By comparison, this research shows that this issue can be addressed by instead assessing when and why: i) wandering sets of non-zero measure arise and ii) event space variations and non-invariant DST measures arise, given (i) and (ii) are mathematically known to be equivalent to assessing recurrence within σ-finite measure spaces.

This theoretical DST analysis of QNs defined over the EMM representation of runtime software system behaviors then leads to the development of four pragmatically easily measurable and implementable software engineering design rules that can be used to assess when and why a given deployed software system will (or will not) exhibit statistically predictable run-time behaviors. These design rules are then applied to develop a sufficiently rich cloud-deployed software system simulation framework, which includes incoming statistical workloads, cloud networking fabric, physical server, virtual machine, and container deployment regimes, fair and real-time OS scheduling, and background physical server workloads. This simulation framework is then used to validate the DST theory BET-compliance analysis insights through a detailed set of software system run-time deployment
scenarios, both for an industry-held exemplar system and for emerging industry deployment trends.

To our knowledge, this is the first set of research to formally assess run-time software system BET-compliance for systems of arbitrary scale and complexities. Moreover, it is the first work to show, through theory and simulation-based validation, that modern software systems exist as highly complex dynamical systems that can concurrently admit BET-compliant and BET non-compliant performance measures, while also admitting measures that can dynamically transition back and forth between BET-compliance and non-compliance as the system runs. As engineering can be summarily defined in terms of the need to build systems and solutions that behave predictably in their real-world operation under all likely deployment scenarios and environments, the developed novel insight into the core DST complexity of software systems helps to partially explain why the software engineering of modern industry-scale software systems has remained a challenging and largely open problem, outside of specific quite tailored regimes, i.e., the regimes that can be seen to follow this dissertation’s developed software engineering design rules.

The issue of BET-compliance has wide applicability across many areas, spanning statistical run-time performance predictability, control theory, machine learning (ML) and artificial intelligence (AI), quantum computing, etc. The insights and theoretical framework developed in this research have wide potential applicability beyond just the core software engineering need to develop and deploy software systems that behave predictably, in the sense of remaining within a defined set of statistical behavioral bounds. More particularly, emerging areas of potentially applicable research include: the use of formal control theory approaches within cloud elastic services; the safety and operationally critical aspects of Smart Cities, Smart Grids, autonomous vehicles and vehicle networks; when, why, and how AI/ML approaches can be applied to accurately predict software system run-time behaviors; BET-compliance within cybersecurity focused regimes and solutions; etc. As such, we hope this work will be seen as a useful and insightful contribution to advancing the formal engineering of software-centric systems and solutions.