I consider Distributed Hash Tables (DHTs) based on a [0,1) ring. The whole ring is partitioned among the peers so, that each peer is responsible for an interval and that each point in [0,1) is attributed to a peer. When a piece of information is to be published or found, a global hash function is computed on its name, yielding a point in [0,1). The peer responsible for the interval containing this point is also responsible for the considered piece of information. Network construction and routing, based on a hypercube and/or a de Bruijn graph, enable to find the sought-after point in logarithmic time (in the number of present peers).
I present distributed algorithms which assure that the intervals, for which peers are responsible, are of equal lengths, up to constant factors. The main difficulty in this problem is that the dynamics of the system are unpredictable. Therefore, I present two schemes. The first one is able to balance any system in logarithmic time but has unbounded communication cost. The second one has communication cost only by a logarithmic factor larger than any scheme keeping the system connected, but balances the system with some delay.
We will discuss and compare several policies to place replicas in tree networks, subject to server capacity. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers.
One major contribution is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. We establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program.
As the size of distributed systems keeps growing, the peer to peer communication paradigm has been identified as the key to scalability. In a peer to peer overlay, no entity has a global knowledge of the system.
As much as this property is essential to ensure the scalability, monitoring the system under such circumstances is a complex task. Yet, estimating the size of the system is a core functionality for many distributed applications to parameter setting or monitoring purposes. In this talk, we first introduce existing approaches that estimate the system size in a fully decentralized way. We then propose two new algorithms, based on random walks. Candidate approaches are generally applicable irrespective of the underlying structure of the peer to peer overlay. A comparative study follows, reporting the head to head comparison of those algorithms, highlighting significant differences in cost and accuracy.
Distributed systems are now both very large and highly dynamic. Peer to peer overlay networks have been proved efficient to cope with this new deal that traditional approaches can no longer accommodate. While the challenge of organizing peers in an overlay network has generated a lot of interest leading to a large number of solutions, maintaining critical data in such a network remains an open issue. In this paper, we are interested in defining the portion of nodes and frequency one has to probe, given the churn observed in the system, in order to achieve a given probability of maintaining the persistence of some critical data. More specifically, we provide a clear result relating the size and the frequency of the probing set along with its proof as well as an analysis of the way of leveraging such an information in a large scale dynamic distributed system.
Multiple applications that execute on an heterogeneous platform compete for CPU and network resources. Local fair sharing of resources may result in a bad application-level fairness and efficiency. Hence, applications should collaborate to ensure a good use of resources. In this talk, we focus on tree-shaped platform under the multi-port model and aim at scheduling multiple task collections in steady-state. Task collections are sets of identical and independent tasks. After having defined the notion of fairness for this problem, we focus on the proportional fairness that seems to be the most relevant definition in this context.
We present some Lagrangian Optimization basic results and explain how this relates to our problem. Then, we present how this technique, coupled with some distributed gradient technique, can lead to a distributed algorithm (thus suited for large-scale platforms) which maintains proportional fairness between the applications while maximizing the usage of the platform. This distributed algorithm can be seen as a bargain between applications and resources. We present some early simulation results and explain how this technique can be generalized to more general platforms.
Recently there has been an increasing interest to harness the potential of P2P technology to design and build rich environments where services are provided and multiple applications can be supported in a flexible and dynamic manner. In such a context, resource assignment to services and applications is crucial. Current approaches require significant "manual-mode" operations and/or rely on centralized servers to maintain resource availability. Such approaches are neither scalable nor robust enough. Our contribution towards the solution of this problem is proposing and evaluating a gossip-based protocol to automatically partition the available nodes into "slices", also taking into account specific attributes of the nodes. These slices can be assigned to run services or applications in a fully selforganizing but controlled manner. The main advantages of the proposed protocol are extreme scalability and robustness. We present approximative theoretical models and extensive empirical analysis of the proposed protocol.