The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems
JOURNAL OF STATISTICAL PHYSICS
Authors: Budzynski, Louise; Semerjian, Guilhem
Abstract
Random constraint satisfaction problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of k-uniform hypergraphs with a density alpha of constraints, and the q-coloring of random graphs with average degree c. We show that in the large k, q limit the clustering transition occurs for alpha = 2(k-1)/k (ln k + ln ln k + gamma(d) + o(1)), c = q(ln q + ln ln q + gamma(d) + o(1)), where gamma(d) is the same constant for both models. We characterize gamma(d) via a functional equation, solve the latter numerically to estimate gamma(d) approximate to 0.871, and obtain an analytic lowerbound gamma(d) >= 1 + ln(2(root 2 - 1)) approximate to 0.812. Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at gamma(r) = 1.
Cost-aware Multi Data-Center Bulk Transfers in the Cloud from a Customer-Side Perspective
IEEE TRANSACTIONS ON CLOUD COMPUTING
Authors: Luis Garcia-Dorado, Jose; Rao, Sanjay G.
Abstract
Many cloud applications (e.g., data backup and replication, video distribution) require dissemination of large volumes of data from a source data-center to multiple geographically distributed data-centers. Given the high costs of wide-area bandwidth, the overall cost of inter-data-center communication is a major concern in such scenarios. While previous works have focused on optimizing the costs of bulk transfer, most of them use the charging models of Internet service providers, typically based on the 95th percentile of bandwidth consumption. However, public Cloud Service Providers (CSP) follow very different models to charge their customers. First, the cost for transmission is flat and depends on the location of the source and receiver data-centers. Second, CSPs offer discounts once customer transfers exceed certain volume thresholds per data-center. We present a systematic framework, CloudMPcast, that exploits these two aspects of cloud pricing schemes. CloudMPcast constructs overlay distribution trees for bulk-data transfer that both optimizes dollar costs of distribution, and ensures end-to-end data transfer times are not affected. CloudMPCast monitors TCP throughputs between data-centers and only proposes alternative trees that respect original transfer times. After an extensive measurement study, the cost savings range from 10 to 60 percent for both Azure and EC2 infrastructures, which potentially translates to millions of dollars a year assuming realistic demands.