Network Management and Search in Loosely Coupled Distributed Systems
Loosely coupled distributed systems are those in which nodes can join, leave,
or fail at high rates without centralized control and network connections or
topology can be highly unstable. Examples include self-organizing Internet
overlay networks, wireless networks, and local-area machine clusters
without centrally coordinated management. This project studies several
problems on network management and search in loosely coupled distributed
systems. On network management, we consider scalable network structure
management (NSDI'04), random membership subset management (INFOCOM'05, Trans. on Computers),
and non-uniform information dissemination (ICNP'03). Exploiting the data
popularity skewness in real-world applications, we investigate popularity-driven
adaptive distributed data management, specifically for object replication degree
customization (EuroSys'08), correlated object placement (ICDCS'08), and
Bloom filter hash number customization (PODC'08). In addition to network
management, we also study the support for search, an extremely effective
utility for many higher-level distributed services. Our study includes
peer-to-peer full-text keyword search (WebDB'05) and object search (IPTPS'06).
Project Members:
Ross Camara, undergraduate researcher at University of Rochester (graduated)
John Heidkamp, undergraduate researcher at University of Rochester (graduated)
Pin Lu, Microsoft Inc.
Justin Moore, undergraduate researcher at University of Rochester (graduated)
Amy L. Murphy, Center for Scientific and Technological Research (IRST), Bruno Kessler Foundation (FBK), Italy
Kai Shen, University of Rochester
Ming Zhong, Google Inc.
Contact:
Kai Shen
(kshen@cs.rochester.edu)
Support:
This project is supported by the National Science Foundation under
Grant No. 0312925. Link to the award abstract.
Note:
Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the National Science Foundation.
Publications:
-
Ming Zhong, Pin Lu, Kai Shen, and Joel Seiferas,
"Optimizing Data Popularity Conscious Bloom Filters".
To appear in Proc. of the 27th ACM Symposium on Principles of Distributed Computing (PODC'08),
Toronto, Canada, August 2008.
Abstract.
Postscript version.
PDF version.
-
Ming Zhong, Kai Shen, and Joel Seiferas,
"Correlation-Aware Object Placement for Multi-Object Operations".
In Proc. of the 28th International Conference on Distributed Computing Systems (ICDCS'08),
Beijing, China, June 2008.
Abstract.
Postscript version.
PDF version.
Conference talk slides in Powerpoint.
-
Ming Zhong, Kai Shen, and Joel Seiferas,
"The Convergence-Guaranteed Random Walk and Its Applications in Peer-to-Peer Networks".
In IEEE Transactions on Computers, Volume 57, Number 5, Pages 619-633, May 2008.
Abstract.
Postscript version.
PDF version.
-
Ming Zhong, Kai Shen, and Joel Seiferas,
"Replication Degree Customization for High Availability".
In Proc. of the Third EuroSys Conference (EuroSys'08),
Pages 55-68, Glasgow, Scotland, April 2008.
Abstract.
Postscript version.
PDF version.
Conference talk slides in Powerpoint.
-
Ming Zhong,
"Exploiting Object Usage Nonuniformity in Distributed Data Management".
PhD Dissertation, Department of Computer Science, University of Rochester, 2007.
-
Ming Zhong and Kai Shen,
"Random Walk Based Node Sampling in Self-Organizing Networks".
In ACM SIGOPS Operating Systems Review, Volume 40, Number 3, Pages 49-55, July 2006.
Abstract.
Postscript version.
PDF version.
-
Ming Zhong and Kai Shen,
"Popularity-Biased Random Walks for Peer-to-Peer Search under the Square-Root Principle".
In Proc. of the 5th International Workshop on Peer-to-Peer Systems (IPTPS'06),
Santa Barbara, CA, February 2006.
Abstract.
Postscript version.
PDF version.
-
Ming Zhong, Justin Moore, Kai Shen, and Amy L. Murphy,
"An Evaluation and Comparison of Current Peer-to-Peer Full-Text Keyword Search Techniques".
In Proc. of the 8th International Workshop on the Web & Databases (WebDB'05),
Held along with SIGMOD, Baltimore MD, June 2005.
Abstract.
Postscript version.
PDF version.
-
Ming Zhong, Kai Shen, and Joel Seiferas,
"Non-uniform Random Membership Management in Peer-to-Peer Networks".
In Proc. of the IEEE INFOCOM, Miami FL, March 2005.
Abstract.
Postscript version.
PDF version.
-
Kai Shen, Lingkun Chu, and Tao Yang,
"Supporting Cluster-based Network Services on Functionally Symmetric Software Architecture".
In Proc. of SC2004: High Performance Computing, Networking and Storage Conference, Pittsburgh PA, November 2004.
Abstract.
Postscript version.
PDF version.
-
Kai Shen and Yuan Sun,
"Distributed Hashtable on Pre-Structured Overlay Networks".
In Proc. of the 9th International Workshop on Web Caching and Content Distribution (WCW'04), Pages 63-81, Beijing, China, October 2004.
Abstract.
Postscript version.
PDF version.
-
Kai Shen,
"Structure Management for Scalable Overlay Service Construction".
In Proc. of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI'04),
Pages 281-294, San Francisco CA, March 2004.
Abstract.
Postscript version.
PDF version.
HTML version.
Conference talk slides in Powerpoint.
-
Kai Shen, Tao Yang, and Lingkun Chu,
"Clustering Support and Replication Management for Scalable Network Services".
In the IEEE Transactions on Parallel and Distributed Systems - Special Issue on Middleware, Volume 14, Number 11, Pages 1168-1179, November 2003.
Abstract.
Postscript version.
PDF version.
-
Sameer Tilak, Amy Murphy, and Wendi Heinzelman,
"Non-uniform Information Dissemination for Sensor Networks".
In Proc. of the 11th IEEE International Conference on Network Protocols,
Pages 295-304, Atlanta GA, November 2003.
Link to publisher's site.
Demo and Research Artifact:
-
Ming Zhong, Kai Shen, and John Heidkamp,
"A Random Membership Sampler Based on Guided Random Walks".
Demo at the Third USENIX Workshop on Real Large Distributed Systems (WORLDS '06),
Seattle WA, November 2006.
Demo description.
Click next link for on-line demo.
-
As part of this project, we collected a dataset of Web pages for our research on distributed
keyword searching. The dataset contains around 3.7 million
Web pages cataloged by the DMOZ Web directory (http://www.dmoz.com). Please contact us
if you would like to use this dataset in your research. We do not post it on-line due
to its large size.