%0 Conference Paper
%B Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval
%D 2009
%T Brute force and indexed approaches to pairwise document similarity comparisons with MapReduce
%A Jimmy Lin
%K distributed algorithms
%K hadoop
%X This paper explores the problem of computing pairwise similarity on document collections, focusing on the application of "more like this" queries in the life sciences domain. Three MapReduce algorithms are introduced: one based on brute force, a second where the problem is treated as large-scale ad hoc retrieval, and a third based on the Cartesian product of postings lists. Each algorithm supports one or more approximations that trade effectiveness for efficiency, the characteristics of which are studied experimentally. Results show that the brute force algorithm is the most efficient of the three when exact similarity is desired. However, the other two algorithms support approximations that yield large efficiency gains without significant loss of effectiveness.
%B Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval
%S SIGIR '09
%I ACM
%C New York, NY, USA
%P 155 - 162
%8 2009///
%@ 978-1-60558-483-6
%G eng
%U http://doi.acm.org/10.1145/1571941.1571970
%R 10.1145/1571941.1571970
%0 Conference Paper
%B IEEE INFOCOM 2009
%D 2009
%T Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks
%A Han,Bo
%A Kumar,V. S.A
%A Marathe,M. V
%A Parthasarathy,S.
%A Srinivasan, Aravind
%K access hash function
%K Channel allocation
%K channel assignment algorithm
%K channel capacity
%K collision avoidance
%K Computer science
%K cryptography
%K distributed algorithm
%K distributed algorithms
%K Educational institutions
%K inductive-scheduling technique
%K Interference
%K interference set
%K packet scheduling algorithm
%K Peer to peer computing
%K Radio network
%K radio networks
%K radiofrequency interference
%K random oracle methodology
%K scheduling
%K Scheduling algorithm
%K simultaneous channel allocation
%K software radio
%K software-defined radio wireless network capacity
%K telecommunication congestion control
%K telecommunication security
%K Throughput
%K wireless channels
%K Wireless networks
%X Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.
%B IEEE INFOCOM 2009
%I IEEE
%P 1521 - 1529
%8 2009/04/19/25
%@ 978-1-4244-3512-8
%G eng
%R 10.1109/INFCOM.2009.5062069
%0 Journal Article
%J IEEE Journal on Selected Areas in Communications
%D 2007
%T Efficient lookup on unstructured topologies
%A Morselli,R.
%A Bhattacharjee, Bobby
%A Marsh,M.A.
%A Srinivasan, Aravind
%K Computer science
%K DHT
%K distributed algorithms
%K Distributed computing
%K distributed hash table
%K Least squares approximation
%K LMS
%K local minima search
%K lookup protocol
%K Network topology
%K node failures
%K Peer to peer computing
%K Performance analysis
%K Protocols
%K replication strategy
%K Resilience
%K Robustness
%K table lookup
%K telecommunication network topology
%K unstructured network topology
%X We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of LMS. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size
%B IEEE Journal on Selected Areas in Communications
%V 25
%P 62 - 72
%8 2007/01//
%@ 0733-8716
%G eng
%N 1
%R 10.1109/JSAC.2007.07007
%0 Journal Article
%J Computer Networks
%D 2006
%T Cooperative peer groups in NICE
%A Sherwood,Rob
%A Lee,Seungjoon
%A Bhattacharjee, Bobby
%K distributed algorithms
%K P2P
%K Reputation base trust
%X We present a distributed scheme for trust inference in peer-to-peer networks. Our work is in the context of the NICE system, which is a platform for implementing cooperative applications over the Internet. We describe a technique for efficiently storing user reputation information in a completely decentralized manner, and show how this information can be used to efficiently identify non-cooperative users in NICE. We present a simulation-based study of our algorithms, in which we show our scheme scales to thousands of users using modest amounts of storage, processing, and bandwidth at any individual node. Lastly we show that our scheme is robust and can form cooperative groups in systems where the vast majority of users are malicious.
%B Computer Networks
%V 50
%P 523 - 544
%8 2006/03/15/
%@ 1389-1286
%G eng
%U http://www.sciencedirect.com/science/article/pii/S1389128605002185
%N 4
%R 10.1016/j.comnet.2005.07.012
%0 Conference Paper
%B Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing
%D 2005
%T Efficient lookup on unstructured topologies
%A Morselli,Ruggero
%A Bhattacharjee, Bobby
%A Srinivasan, Aravind
%A Marsh,Michael A
%K distributed algorithms
%K lookup protocols
%K peer-to-peer networks
%K random walks
%X We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT).We present analytic bounds for the worst-case performance of our protocol. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size.
%B Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing
%S PODC '05
%I ACM
%C New York, NY, USA
%P 77 - 86
%8 2005///
%@ 1-58113-994-2
%G eng
%U http://doi.acm.org/10.1145/1073814.1073828
%R 10.1145/1073814.1073828
%0 Conference Paper
%B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
%D 1994
%T Computing with very weak random sources
%A Srinivasan, Aravind
%A Zuckerman,D.
%K Application software
%K BPP simulations
%K Chor-Goldreich sources
%K computational complexity
%K Computational modeling
%K Computer science
%K Computer simulation
%K cryptography
%K distributed algorithms
%K expander constructions
%K hardness
%K MATHEMATICS
%K min-entropy
%K Physics computing
%K Polynomials
%K probability
%K R-bit string
%K randomness-efficient Leftover Hash Lemma
%K RP algorithms simulation
%K Testing
%K time-space tradeoffs
%K very weak random sources
%X For any fixed ε>0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2-R(ε). If ε>1-1/(k+1), our BPP simulations take time nO(log(k n)) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson
%B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
%I IEEE
%P 264 - 275
%8 1994/11/20/22
%@ 0-8186-6580-7
%G eng
%R 10.1109/SFCS.1994.365688
%0 Conference Paper
%B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
%D 1993
%T A distributed algorithm for ear decomposition
%A Hannenhalli, Sridhar
%A Perumalla,K.
%A Chandrasekharan,N.
%A Sridhar,R.
%K Asynchronous communication
%K asynchronous communication network
%K Automata
%K Communication networks
%K computational complexity
%K Computer networks
%K Computer science
%K decomposition graph
%K distributed algorithm
%K distributed algorithms
%K Distributed computing
%K Ear
%K ear decomposition
%K graph theory
%K message-optimal
%K network decomposition
%K sorting
%K Testing
%K time-optimal
%X A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition
%B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
%I IEEE
%P 180 - 184
%8 1993/05/27/29
%@ 0-8186-4212-2
%G eng
%R 10.1109/ICCI.1993.315382