Design of Availability-Dependent Distributed Services in Large-Scale Uncooperative Settings.
Ramsés Morales · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2009
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