Qos-aware algorithm design for distributed systems

With the fast development of networking technology, modern distributed systems are designed to provide a variety of services. In this dissertation, we focus on algorithm design for four different types of distributed systems with consideration of quality of service as well as resource constraints. We design algorithms for (i) data transmission system, (ii) geographically distributed data centers, (iii) structured peer to peer video streaming systems, and (iv) wireless sensor systems. These systems differ from each other in several dimensions: functionality, resource availability, and workload characteristics. As illustrated in this dissertation, our approaches are built on a common theme: understanding and exploitation of resource availability and workload characteristics. More specifically, in this document we focus on the following topics: for data transmission systems, we provide scheduling algorithms as well as performance bounds aimed at reducing the cost on bandwidth, which is accounted based on 95th percentile rule. For geographically distributed data centers that serve delay tolerant workloads, we design a stochastic optimization based approach for making routing and server management decisions, so as to reduce the cost of power, while maintaining quality of service. For structured peer to peer streaming systems, we provide two different peer communication algorithms that achieve different levels of trade-offs in performance metrics such as playback delay and buffer size. For wireless sensor systems, we develop an online, low resource usage anomaly detection algorithm that accurately identifies interesting events in sensor readings.