Thesis Statement: "Availability-dependent global predicates can be efficiently and scalably realized for a class of distributed services, in spite of specific selfish and colluding behaviors, using local and decentralized protocols". Several types of large-scale distributed systems spanning the Internet have to deal with availability variations among their constituent nodes. In dealing with churn and low availability nodes, we believe it is important to link the availability of a node to the service the node receives "from" the distributed system. In other words, high availability has to be incentivized with better service. There are two types of requirements for this problem. First, metrics such as message overhead, CPU usage, memory overhead and latency need to be optimized to achieve scalability and efficiency. Secondly, in open distributed systems spanning multiple organizations, the protocols have to tolerate selfish and colluding nodes, i.e., low availability nodes that attempt to receive better service. This thesis approaches this problem by "explicitly" linking each node's service to its availability, via the notion of a "global predicate". We present a class of novel distributed protocols that achieve a given availability-dependent global predicate, efficiently and scalably. These protocols execute in a fully decentralized manner, realizing the global predicates in an emergent fashion. Predicate satisfaction is resilient to churn, and to selfish and colluding nodes. The eventual goal of the predicates is to help incentivize nodes to improve their availability in order to get better service. Our approach includes using random and consistent techniques to build overlays, as well as probabilistic local actions such as message forwarding, monitoring, and auditing. This combination of techniques leads to realizing the predicates, and to probabilistic tolerance to failures, both churn-related as well as from selfish and colluding behaviors. Concretely, this thesis makes three major contributions that are closely related to each other. First we present AVMON, the first distributed availability monitoring service. AVMON builds random and consistent overlays for accurate and decentralized monitoring of the long term availability of each node. Second, we present AVMEM, the first availability-aware overlay. Nodes in AVMEM build their membership by using a globally assigned predicate, leveraging our AVMON work. On top of AVMEM we implement management functions that query nodes based on their availability--range/threshold multicast and range/threshold anycast. Finally, we present AVCOL, the first availability-aware network aggregation system that realizes availability-dependent predicates. The predicates specify the probability that a node's aggregate becomes part of the global aggregate, as a function of the node's availability. We evaluate our systems through mathematical analysis, and thorough experimentation. We carry out our experiments using synthetic and real system traces. Our results demonstrate the probabilistic correctness, scalability, fault-tolerance, and efficiency of our protocols. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]