Conventionally, to support varying power demand, the utility company must prepare to supply more electricity than actually needed, which causes inefficiency and waste. With the increasing penetration of renewable energy which is intermittent and stochastic, how to balance the power generation and demand becomes even more challenging. Demand response, which reschedules part of the elastic load in users' side, is a promising technology to increase power generation efficiency and reduce costs. However, how to coordinate all the distributed heterogeneous elastic loads efficiently is a major challenge and sparks numerous research efforts. In this thesis, we investigate different methods to provide demand response and improve power grid efficiency. First, we consider how to schedule the charging process of all the Plugged-in Hybrid Electrical Vehicles (PHEVs) so that demand peaks caused by PHEV charging are flattened. Existing solutions are either centralized which may not be scalable, or decentralized based on real-time pricing (RTP) which may not be applicable immediately for many markets. Our proposed PHEV charging approach does not need complicated, centralized control and can be executed online in a distributed manner. In addition, we extend our approach and apply it to the distribution grid to solve the bus congestion and voltage drop problems by controlling the access probability of PHEVs. One of the advantages of our algorithm is that it does not need accurate predictions on base load and future users' behaviors. Furthermore, it is deployable even when the grid size is large. Different from PHEVs, whose future arrivals are hard to predict, there is another category of elastic load, such as Heating Ventilation and Air-Conditioning (HVAC) systems, whose future status can be predicted based on the current status and control actions. How to minimize the power generation cost using this kind of elastic load is also an interesting topic to the power companies. Existing work usually used HVAC to do the load following or load shaping based on given control signals or objectives. However, optimal external control signals may not always be available. Without such control signals, how to make a tradeoff between the fluctuation of non-renewable power generation and the limited demand response potential of the elastic load, and to guarantee user comfort level, is still an open problem. To solve this problem, we first model the temperature evolution process of a room and propose an approach to estimate the key parameters of the model. Then, based on the model predictive control, a centralized and a distributed algorithm are proposed to minimize the fluctuation and maximize the user comfort level. In addition, we propose a dynamic water level adjustment algorithm to make the demand response always available in two directions. Extensive simulations based on practical data sets show that the proposed algorithms can effectively reduce the load fluctuation. Both randomized PHEV charging and HVAC control algorithms discussed above belong to direct or centralized load shaping, which has been heavily investigated. However, it is usually not clear how the users are compensated by providing load shaping services. In the last part of this thesis, we investigate indirect load shaping in a distributed manner. On one hand, we aim to reduce the users' energy cost by investigating how to fully utilize the battery pack and the water tank for the Combined Heat and Power (CHP) systems. We first formulate the queueing models for the CHP systems, and then propose an algorithm based on the Lyapunov optimization technique which does not need any statistical information about the system dynamics. The optimal control actions can be obtained by solving a non-convex optimization problem. We then discuss when it can be converted into a convex optimization problem. On the other hand, based on the users' reaction model, we propose an algorithm, with a time complexity of O(log n), to determine the RTP for the power company to effectively coordinate all the CHP systems and provide distributed load shaping services. / Graduate