Low overhead analysis of large distributed data sets is necessary for current data centers and for future sensor networks. In such systems, each node holds some data value, e.g., a local sensor read, and a concise pic...
详细信息
ISBN:
(纸本)9781605588889
Low overhead analysis of large distributed data sets is necessary for current data centers and for future sensor networks. In such systems, each node holds some data value, e.g., a local sensor read, and a concise picture of the global system state needs to be obtained. In resource-constrained environments like sensor networks, this needs to be done without collecting all the data at any location, i.e., in a distributed manner. To this end, we define the distributed classification problem, in which numerous interconnected nodes compute a classification of their data, i.e., partition these values into multiple collections, and describe each collection concisely. We present a generic algorithm that solves the distributed classification problem and may be implemented in various topologies, using different classification types. For example, the generic algorithm can be instantiated to classify values according to distance, like the famous k-means classification algorithm. However, the distance criterion is often not sufficient to provide good classification results. We present an instantiation of the generic algorithm that describes the values as a Gaussian Mixture (a set of weighted normal distributions), and uses machine learning tools for classification decisions. Simulations show the robustness and speed of this algorithm. We prove that any implementation of the generic algorithm converges over any connected topology, classification criterion and collection representation, in fully asynchronous settings.
We start by defining a pruning process involving sellers on one side and buyers on the other. the goal is to quickly select a subset of the sellers so that the products that these sellers bring to the market has small...
详细信息
ISBN:
(纸本)9781605588889
We start by defining a pruning process involving sellers on one side and buyers on the other. the goal is to quickly select a subset of the sellers so that the products that these sellers bring to the market has small cost ratio, i.e., the ratio of the total cost of the selected sellers' products to amount that interested buyers are willing to pay. As modeled here, the pruning process can be used to speed up distributed implementations of greedy algorithms (e.g., for minimum dominating set, facility location, etc). We present a randomized instance of the pruning process that, for any positive k, runs in O(k) communication rounds with O(log N)-sized messages, yielding a cost ratio of O(N-c/k). Here N is the product of the number of sellers and number of buyers and c is a small constant. Using this O(k)-round pruning algorithm as the basis, we derive several simple, greedy, O(k)-round distributed approximation algorithms for AIDS and facility location (both metric and non-metric versions). Our algorithms achieve optimal approximation ratios in polylogarithmic rounds and shave a "logarithmic factor" off the best, known, approximation factor, typically achieved using LP-rounding techniques.
this paper addresses partial information spreading among n nodes of a network. As opposed to traditional information spreading, where each node has a message that must be received by all nodes, we propose a relaxed re...
详细信息
ISBN:
(纸本)9781605588889
this paper addresses partial information spreading among n nodes of a network. As opposed to traditional information spreading, where each node has a message that must be received by all nodes, we propose a relaxed requirement, where only n/c nodes need to receive each message, and every node should receive n/c messages, for some c >= 1. As a key tool in our study we introduce the novel concept of weak conductance, a generalization of classic graph conductance which allows to analyze the time required for partial information spreading. We show the power of weak conductance as a measure of how well-knit the components of a graph are, by giving an example of a graph family for which the conductance is O(n(-2)), while the weak conductance is as large as 1/2. For such graphs, weak conductance can be used to show that partial information spreading requires time complexity of O(log n). Finally, we demonstrate the usefulness of partial information spreading in solving the maximum coverage problem, which naturally arises in circuit layout, job scheduling and facility location, as well as in distributed resource allocation with a global budget constraint. Our algorithm yields a constant approximation factor and a constant deviation from the given budget. For graphs with a constant weak conductance, this implies a scalable time complexity for solving a problem with a global constraint.
We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only (O) over tilde(root n) bits, where n is the total number of processors. Our algorithm succeeds with high pr...
详细信息
ISBN:
(纸本)9781605588889
We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only (O) over tilde(root n) bits, where n is the total number of processors. Our algorithm succeeds with high probability against an adaptive adversary, which can take over processors at any time during the protocol, up to the point of taking over arbitrarily close to a 1/3 fraction. We assume synchronous communication but a rushing adversary. Moreover, our algorithm works in the presence of flooding: processors controlled by the adversary can send out any number of messages. We assume the existence of private channels between all pairs of processors but make no other cryptographic assumptions. Finally, our algorithm has latency that is polylogarithmic in n. To the best of our knowledge, ours is the first algorithm to solve Byzantine agreement against an adaptive adversary, while requiring o(n(2)) total bits of communication.
distributed consensus can be achieved on asynchronous communication networks when assisted by quantum mechanics. this contradicts the FLP impossibility result by achieving consensus in the presence of faults.
ISBN:
(纸本)9781595939890
distributed consensus can be achieved on asynchronous communication networks when assisted by quantum mechanics. this contradicts the FLP impossibility result by achieving consensus in the presence of faults.
暂无评论