We present some recent and ongoing work in our decentralized desktop computing grid project. Specifically, we discuss matching jobs with compute nodes in a peer-to-peer grid of heterogeneous platforms, and the implementation of our algorithms in a concrete system.

Social networks, of which webs of trust are a particular type, have been shown to be effective ways of moving information with minimal external configuration, setup, or management. For applications requiring information assurance, a web of trust is an appealing system architecture, since trust is an inherent component of both the network design and assurance. The trust in a typical web of trust is not transitive, however, making the construction of an application with strong assurance difficult or impossible. Instead, in this paper we examine a notion of weak assurance that can be provided by a web of trust, and might be “good enough” for many applications. As a motivating example, and to provide a more concrete basis for exposition, we present KeyChains, a peer-to-peer system that operates over a distributed web of trust to provide fully decentralized public key publishing and retrieval. In addition to weak assurance guarantees, KeyChains also provides an audit trail for public keys retrieved. Our analysis and simulations show that the resulting system is both efficient and secure.

Desktop grids have evolved to combine Peer-to-Peer and Grid computing techniques to improve the robustness, reliability and scalability of job execution infrastructures. However, efficiently matching incoming jobs to available system resources and achieving good load balance in a fully decentralized and heterogeneous computing environment is a challenging problem. In this paper, we extend our prior work with a new decentralized algorithm for maintaining approximate global load information, and a job pushing mechanism that uses the global information to push jobs towards underutilized portions of the system. The resulting system more effectively balances load and improves overall system throughput. Through a comparative analysis of experimental results across different system configurations and job profiles, performed via simulation, we show that our system can reliably execute Grid applications on a distributed set of resources both with low cost and with good load balance.

The goal of the work described in this paper is to design and build a scalable infrastructure for executing grid applications on a widely distributed set of resources. Such grid infrastructure must be decentralized, robust, highly available, and scalable, while efficiently mapping application instances to available resources in the system. However, current desktop grid computing platforms are typically based on a client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. Fortunately, these problems can be addressed through the capabilities promised by new techniques and approaches in peer-to-peer (P2P) systems. By employing P2P services, our system allows users to submit jobs to be run in the system and to run jobs submitted by other users on any resources available in the system, essentially allowing a group of users to form an ad-hoc set of shared resources. The initial target application areas for the desktop grid system are in astronomy and space science simulation and data analysis.

We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of LMS. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size

A protocol is given to take an ElGamal ciphertext encrypted under the key of one distributed service and produce the corresponding ciphertext encrypted under the key of another distributed service, but without the plaintext ever becoming available. Each distributed service comprises a set of servers and employs threshold cryptography to maintain its service private key. Unlike prior work, the protocol requires no assumptions about execution speeds or message delivery delays. The protocol also imposes fewer constraints on where and when various steps are performed, which can bring improvements in end-to-end performance for some applications (e.g., a trusted publish/subscribe infrastructure.) Two new building blocks employed — a distributed blinding protocol and verifiable dual encryption proofs — could have uses beyond re-encryption protocols.

We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT).We present analytic bounds for the worst-case performance of our protocol. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size.

CODEX (COrnell Data Exchange) stores secrets for subsequent access by authorized clients. It also is a vehicle for exploring the generality of a relatively new approach to building distributed services that are both fault-tolerant and attack-tolerant. Elements of that approach include: embracing the asynchronous (rather than synchronous) model of computation, use of Byzantine quorum systems for storing state, and employing proactive secret sharing with threshold cryptography for implementing confidentiality and authentication of service responses. Besides explaining the CODEX protocols, experiments to measure their performance are discussed.

This paper proposes to implement an IPv6 routing infrastructure as a self-organizing overlay network on top of the current IPv4 infrastructure. The overlay network builds upon a distributed IPv6 edge router with a master/slave architecture. We show how different slaves can be constructed to tunnel through NATs and firewalls, as well as to improve robustness of the routing infrastructure and to provide efficient and resilient implementations for features such as multicast, anycast, and mobile IP using currently available peer-to-peer (P2P) protocols. The resulting IPv6 overlay network would restore the end-to-end property of the original Internet, support evolution and dynamic updating of the protocols running on the overlay network, make available IPv6 and the associated features to network applications immediately, and provide an ideal underlying infrastructure for P2P applications, without changing networking hardware and software in the core Internet.