Probabilistic reliable dissemination in large-scale systems

The growth of the Internet raises new challenges for the design of distributed systems and applications. In the context of group communication protocols, gossip-based schemes have attracted interest as they are scalable, easy to deploy, and resilient to network and process failures. However, traditional gossip-based protocols have two major drawbacks: 1) they rely on each peer having knowledge of the global membership; and 2) being oblivious to the network topology, they can impose a high load on network links when applied to wide-area settings. In this paper, we provide a theoretical analysis of gossip-based protocols which relates their reliability to key system parameters (the system size, failure rates, and number of gossip targets). The results provide guidelines for the design of practical protocols. In particular, they show how reliability can be maintained while alleviating drawback by: 1) providing each peer with only a small subset of the total membership information and drawback; and 2) organizing members into a hierarchical structure that reflects their proximity according to some network-related metric. We validate the analytical results by simulations and verify that the hierarchical gossip protocol considerably reduces the load on the network compared to the original, non-hierarchical protocol.     

A manufacturing system with general stationary failure process:stability and IPA of hedging control policies

This paper concerns a new methodology for the adaptive optimization of piecewise deterministic non-Markovian systems via a simple example of interest in manufacturing. This methodology takes into account the fact that piecewise deterministic systems are rarely Markovian and that classical control theory based on dynamic programming of Markovian systems cannot provide quantitative answers in most realistic situations. The example considered is that of a single-machine/single-part production system, from the point of view of the control theory by Kimemia and Gershwin (1983). We obtain stochastic gradient estimates via the perturbation analysis of Ho and Cao (1991) by the “regenerative” method of Konstantopoulos and Zazanis (1992), in view of stochastic optimization. Its mathematical justification requires a careful study of the “regenerative” structure of the process. In particular, we give the necessary and sufficient conditions of stability of this system via the method of Loynes (1962)     

Epidemic information dissemination in distributed systems

Easy to deploy, robust, and highly resilient to failures, epidemic algorithms are a potentially effective mechanism for propagating information in large peer-to-peer systems deployed on Internet or ad hoc networks. It is possible to adjust the parameters of epidemic algorithm to achieve high reliability despite process crashes and disconnections, packet losses, and a dynamic network topology. Although researchers have used epidemic algorithms in applications such as failure detection, data aggregation, resource discovery and monitoring, and database replication, their general applicability to practical, Internet-wide systems remains open to question. We describe four key problems: membership maintenance, network awareness, buffer management, and message filtering, and suggest some preliminary approaches to address them.     

Stability of distributed congestion control with heterogeneousfeedback delays

We investigate how congestion control can achieve efficient usage of network resources in the presence of heterogeneous communication delays between network users and resources. To this end, we consider a fluid flow model of network behavior. We study the stability of the system's behavior under small perturbations around the target equilibrium point (local stability). We establish several criteria for stability of certain linear delay-differential equations, via a technique which essentially reduces the question to studying stability of ordinary differential equations. These results are then used to derive sufficient conditions for local stability of the network congestion control problem. The same issue has been studied by Johari et al. (2001), where the authors propose a conjecture according to which local stability can be ensured in a distributed way. The correctness of the conjecture was established by Johari et al., only in degenerate cases where feedback delays coincide. Our results show that a modified form of the conjecture holds true for arbitrary feedback delays     

Push-to-Peer Video-on-Demand System: Design and Evaluation

We propose Push-to-Peer, a peer-to-peer system to cooperatively stream video. The main departure from previous work is that content is proactively pushed to peers, and persistently stored before the actual peer-to-peer transfers. The initial content placement increases content availability and improves the use of peer uplink bandwidth. Our specific contributions are: (i) content placement and associated pull policies that allow the optimal use of uplink bandwidth; (ii) performance analysis of such policies in controlled environments such as DSL networks under ISP control; (iii) a distributed load balancing strategy for selection of serving peers.     

Bandwidth sharing: objectives and algorithms

This paper concerns the design of distributed algorithms for sharing network bandwidth resources among contending flows. The classical fairness notion is the so-called max-min fairness. The alternative proportional fairness criterion has recently been introduced by F. Kelly (see Eur. Trans. Telecommun., vol.8, p.33-7, 1997); we introduce a third criterion, which is naturally interpreted in terms of the delays experienced by ongoing transfers. We prove that fixed-size window control can achieve fair bandwidth sharing according to any of these criteria, provided scheduling at each link is performed in an appropriate manner. We then consider a distributed random scheme where each traffic source varies its sending rate randomly, based on binary feedback information from the network. We show how to select the source behavior so as to achieve an equilibrium distribution concentrated around the considered fair rate allocations. This stochastic analysis is then used to assess the asymptotic behavior of deterministic rate adaption procedures