A path-based framework for analyzing large markov models

Reliability and dependability modeling can be employed during many stages of analysis of a computing system to gain insights into its critical behaviors. To provide useful results, realistic models of systems are often necessarily large and complex. Numerical analysis of these models presents a formidable challenge because the sizes of their state-space descriptions grow exponentially in proportion to the sizes of the models. On the other hand, simulation of the models requires analysis of many trajectories in order to compute statistically correct solutions. This dissertation presents a novel framework for performing both numerical analysis and simulation. The new numerical approach computes bounds on the solutions of transient measures in large continuous-time Markov chains (CTMCs). It extends existing path-based and uniformization-based methods by identifying sets of paths that are equivalent with respect to a reward measure and related to one another via a simple structural relationship. This relationship makes it possible for the approach to explore multiple paths at the same time,· thus significantly increasing the number of paths that can be explored in a given amount of time. Furthermore, the use of a structured representation for the state space and the direct computation of the desired reward measure (without ever storing the solution vector) allow it to analyze very large models using a very small amount of storage. Often, path-based techniques must compute many paths to obtain tight bounds. In addition to presenting the basic path-based approach, we also present algorithms for computing more paths and tighter bounds quickly. One resulting approach is based on the concept of path composition whereby precomputed subpaths are composed to compute the whole paths efficiently. Another approach is based on selecting important paths (among a set of many paths) for evaluation. Many path-based techniques suffer from having to evaluate many (unimportant) paths. Evaluating the important ones helps to compute tight bounds efficiently and quickly.

Exporting the racial republic: African colonization, national citizenship, and the transformation of U.S. expansion, 1776-1864

The effort to create a colony of African Americans on the west coast of Africa was one of the most celebrated and influential movements in the United States during the first half of the 19th century. While historians have often viewed African colonization through the lens of domestic anti-slavery politics, colonization grew from an imperial impulse which promised to transform the identities of black colonists and indigenous Africans by helping them to build a democratic nation from the foundation of a settler colony. By proposing that persons of African descent could eventually become self-governing subjects, the liberal framework behind colonization offered the possibility of black citizenship rights, but only within racially homogenous nation-states, which some proponents of colonization imagined might lead to a “United States of Africa.” This dissertation examines how the notion of expanding democratic ideals through the export of racial nationhood was crucial to the appeal of colonization. It reveals how colonization surfaced in several crucial debates about race, citizenship, and empire in the antebellum United States by examining discussions about African Americans’ revolutionary claims to political rights, the bounds of US territorial expansion, the removal of native populations in North America, and the racialization of national citizenship, both at home and abroad. By examining African colonization from these perspectives, this dissertation argues that the United States’ efforts to construct a liberal democracy defined by white racial identity were directly connected to the nation’s emerging identity as a defender and exporter of political liberty throughout the world.