Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip for exchanging information computing in an arbitrarily connected network of nodes. The topology such networks changes continuously new nodes join old leave the network. Algorithms need be robust against topology. Additionally, sensor operate under limited computational, communication, energy resources. These constraints have motivated design "gossip" algorithms:...

We provide a systematic study of the problem finding source rumor in network. model spreading network with popular susceptible-infected (SI) and then construct an estimator for source. This is based upon novel topological quantity which we term centrality. establish that this maximum likelihood (ML) class graphs. find following surprising threshold phenomenon: on trees grow faster than line, always has nontrivial detection probability, whereas like probability will go to 0 as grows....

Gupta and Kumar (2000) introduced a random network model for studying the way throughput scales in wireless when nodes are fixed, showed that per source-destination pair is /spl otimes/(1//spl radic/nlogn). Grossglauser Tse (2001) mobile it possible to have constant or otimes/(1) scaling pair. The focus of this paper on characterizing delay determining throughput-delay trade-off such fixed ad hoc networks. For Gupta-Kumar model, we show optimal given by D(n) = otimes/(nT(n)), where T(n)...

Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip for computation information exchange in an arbitrarily connected network of nodes. Nodes such networks operate under limited computational, communication energy resources. These constraints naturally give rise "gossip" algorithms: schemes which distribute the computational burden a node communicates with randomly chosen neighbor. We analyze averaging...

An ideal datacenter network should provide several properties, including low median and tail latency, high utilization (throughput), fair allocation of resources between users or applications, deadline-aware scheduling, congestion (loss) avoidance. Current networks inherit the principles that went into design Internet, where packet transmission path selection decisions are distributed among endpoints routers. Instead, we propose each sender delegate control---to a centralized arbiter---of...

Gupta and Kumar (2000) introduced a random model to study throughput scaling in wireless network with static nodes, showed that the per source-destination pair is Theta(1/radic(nlogn)). Grossglauser Tse (2001) when nodes are mobile it possible have constant pair. In most applications, delay also key metric of performance. It expected high achieved at cost one can be improved other. The focus this paper on studying tradeoff for networks general framework. Optimal throughput-delay laws...

Crowdsourcing systems, in which numerous tasks are electronically distributed to “information pieceworkers,” have emerged as an effective paradigm for human-powered solving of large-scale problems domains such image classification, data entry, optical character recognition, recommendation, and proofreading. Because these low-paid workers can be unreliable, nearly all systems must devise schemes increase confidence their answers, typically by assigning each task multiple times combining the...

Choice models today are ubiquitous across a range of applications in operations and marketing. Real-world implementations many these face the formidable stumbling block simply identifying “right” model choice to use. Because inherently high-dimensional objects, typical approach dealing with this problem is positing, priori, parametric that one believes adequately captures behavior. This can be substantially suboptimal scenarios where cares about using learned make fine-grained predictions;...

The popularity of Aloha-like algorithms for resolution contention between multiple entities accessing common resources is due to their extreme simplicity and distributed nature. Example applications such include Ethernet recently emerging wireless multi-access networks. Despite a long exciting history more than four decades, the question designing an algorithm that essentially as simple Aloha while being efficient has remained unresolved.

The theory of network coding promises significant benefits in performance, especially lossy networks and multicast multipath scenarios. To realize these practice, we need to understand how across packets interacts with the acknowledgment (ACK)-based flow control mechanism that forms a central part today's Internet protocols such as transmission protocol (TCP). Current approaches rateless codes batch-based are not compatible TCP's retransmission sliding-window mechanisms. In this paper,...

The question of aggregating pairwise comparisons to obtain a global ranking over collection objects has been interest for very long time: be it online gamers (e.g., MSR’s TrueSkill system) and chess players, social opinions, or deciding which product sell based on transactions. In most settings, in addition obtaining ranking, finding ‘scores’ each object player’s rating) is understanding the intensity preferences. this paper, we propose Rank Centrality, an iterative rank aggregation...

A major challenge in the design of wireless networks is need for distributed scheduling algorithms that will efficiently share common spectrum. Recently, a few which node can converse with at most single neighbor time have been presented. These guarantee 50% maximum possible throughput. We present first framework guarantees throughput . It based on combination matching algorithm and an compares merges successive solutions. The comparison be done by deterministic or randomized gossip...

In a vertical representation of market-basket database, each item is associated with column values representing the transactions in which it present. The association-rule mining algorithms that have been recently proposed for this show performance improvements over their classical horizontal counterparts, but are either efficient only certain database sizes, or assume particular characteristics contents, applicable to specific kinds schemas. We present here new algorithm called VIPER,...

A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The has the feature encoding process truly online, as opposed to a block-by-block approach. setup assumes packet erasure broadcast channel with stochastic arrivals full feedback, but scheme potentially applicable more general lossy link-by-link feedback. guarantees physical size at sender tracks backlog in degrees of freedom (also called virtual size). notion node "seeing"...

We propose a mechanism that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, source transmits random linear combinations of packets currently in congestion window. At heart scheme is new interpretation ACKs - sink acknowledges every degree freedom (i.e., combination reveals one unit information) even if it does not reveal an original packet immediately. Such enable TCP-like sliding-window approach...

Max-product "belief propagation" is an iterative, local, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of discrete probability distribution specified by graphical model. Despite spectacular success in many application areas such as iterative decoding, computer vision and combinatorial optimization which involve graphs with cycles, theoretical results about both correctness convergence are known few cases (Weiss-Freeman Wainwright, Yeddidia-Weiss-Freeman,...

We provide a systematic study of the problem finding source computer virus in network. model spreading network with variant popular SIR and then construct an estimator for source. This is based upon novel combinatorial quantity which we term rumor centrality. establish that this ML class graphs. find following surprising threshold phenomenon: on trees grow faster than line, always has non-trivial detection probability, whereas like probability will go to 0 as grows. Simulations performed...

One popular hardware device for performing fast routing lookups and packet classification is a ternary content-addressable memory (TCAM). This paper proposes two algorithms to manage the TCAM such that incremental update times remain small in worst case.

Motivated by applications to sensor, peer-to-peer, and ad-hoc networks, we study the problem of computing functions values at nodes in a network totally distributed manner. In particular, consider separable functions, which can be written as linear combinations individual variables. Known iterative algorithms for averaging used compute normalized such but these do not extend general computation actual functions.The main contribution this paper is design randomized algorithm based on...

The problem of computing functions values at the nodes in a network fully distributed manner, where do not have unique identities and make decisions based only on local information, has applications sensor, peer-to-peer, ad hoc networks. task separable functions, which can be written as linear combinations individual variables, is studied this context. Known iterative algorithms for averaging used to compute normalized such but these extend, general, computation actual functions. main...

This paper provides proofs of the rate stability, Harris recurrence, and ε-optimality carrier sense multiple access (CSMA) algorithms where random (or backoff) parameter each node is adjusted dynamically. These require only local information they are easy to implement. The setup a network wireless nodes with fixed conflict graph that identifies pairs whose simultaneous transmissions conflict. studies two algorithms. first algorithm schedules keep up given arrival rates packets. second...