Content area
The study of parallel algorithms has become of wider interest in recent years due to the physical hardware limitations that processors have begun to approach within the past decade. In this dissertation, we seek to expand our understanding of existing parallel algorithms, develop new methods and data structures, and solve problems inherent to distributed systems. In the first chapter, we consider an analysis of peeling an IBLT in parallel, and show that by trading off an additional logarithmic amount of space, we are able to show with overwhelming probability, the IBLT will be successfully peeled in 2 rounds of peeling. We then use the IBLT data structure in the second chapter to solve an issue in a cloud storage setting, where a client and server work together to efficiently recover any data a server may have either been lost or corrupted. Then in the third chapter, we introduce a new model of cache-efficient parallel computing, the Fork-Join I/O Model, which accounts for both I/O efficiency and the asynchronous nature of most parallel systems. We develop a new search tree data structure for this model of computation and show that it is span efficient and work optimal.