Computing with data non-determinism

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing with data non-determinism: Wait time management for peer-to-peer systems

Source

Computer Communications archive
Volume 31 , Issue 3 (February 2008) table of contents

Pages 629-642

Year of Publication: 2008

ISSN:0140-3664

Authors

Javed I. Khan	Media Communications and Networking Research Laboratory, Department of Math & Computer Science, Kent State University, 233 MSB, Kent, OH 44242, USA
Asrar U. Haque	Media Communications and Networking Research Laboratory, Department of Math & Computer Science, Kent State University, 233 MSB, Kent, OH 44242, USA

Publisher

Butterworth-Heinemann Newton, MA, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1016/j.comcom.2007.08.047

ABSTRACT

One of the unusual challenges faced by peer-to-peer algorithms as opposed to classical distributed algorithms is that these have to compute with data non-determinism where there is no guarantee that data from a particular node will be delivered in time or delivered at all. Each distributed component not only has to work in such environment, but also has to decide how long to wait for peers to respond. A large wait can inordinately delay entire computation. A smaller wait can reduce the coverage of the algorithm and drastically degenerate the quality of final result produced. In this paper, we investigate a set of wait management schemas which tries to minimize the overall completion time and maximize the quality of solution. We present detail analyses of the schemas for various scenarios including large power law networks and forms of non-responsiveness. The work promises dramatic improvement in peer-to-peer search and other computations.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	[1]	Matthew S. Allen , Rich Wolski , James S. Plank, Adaptive Timeout Discovery Using the Network Weather Service, Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, p.35, July 24-26, 2002
	[2]	Jianfei Cai, Wenning Zhan, Zhihai He, Optimal Retransmission Timeout Selection For Delay-Constrained Multimedia Communications, International Conference on Image Processing, October 2004, vol. 3, pp. 2035-2038, doi:10.1109/ICIP.2004.1421483.
	[3]	Lavy Libman , Ariel Orda, Optimal retrial and timeout strategies for accessing network resources, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.551-564, August 2002 [doi>10.1109/TNET.2002.801412]
	[4]	M. Grossglauser, Optimal deterministic timeouts for reliable scalable multicast, in: IEEE Infocom'96, (1996) 1425-1441.
	[5]	Tian Bu , Nick Duffield , Francesco Lo Presti , Don Towsley, Network tomography on general topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
	[6]	N.G. Duffield, F. Lo Presti, Multicast Inference of Packet Delay Variance at Interior Networks Links, in: Proc. Infocom'2000, Tel Aviv, Israel, (2000) 26-30.
	[7]	Adams, A., Bu, T., Caceres, R., Duffield, N., Friedman, T., Horowitz, J., Lo Presti, F., Moon, S.B., Paxson, V. and Towsley, D., The use of end-to-end multicast measurements for characterizing internal network behavior. IEEE Communications Magazine.
	[8]	F. Lo Presti, N.G. Duffield, J, Horowitz, D. Towsley, Multicast-Based Inference of Network-Internal Delay Distributions, preprint, AT&T Labs and University of Massachusetts (1999).
	[9]	Tian Bu , Nick Duffield , Francesco Lo Presti , Don Towsley, Network tomography on general topologies, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
	[10]	M.J. Coates, R. Nowak, Network Delay Distribution Inference from End-to-end Unicast Measurement, in: Proc. of the IEEE International Conference on Acoustics, Speech, and Signal Processing (2001).
	[11]	Shih, Meng-Fu and Hero, Alfred, Unicast-Based Inference of Network Link Delay Distributions with Finite Mixture Models. IEEE Transaction on Signal Processing. v51. 2219-2228.
	[12]	Nick G. Duffield , Joseph Horowitz , Francesco Lo Presti , Donald F. Towsley, Network Delay Tomography from End-to-End Unicast Measurements, Proceedings of the Thyrrhenian International Workshop on Digital Communications: Evolutionary Trends of the Internet, p.576-595, September 17-20, 2001
	[13]	K.G. Anagnostakis, M.B. Greenwald, Direct measurement versus indirect inference for determining networkinternal delays, in: Proceedings of Performance (2002).
	[14]	Y. Shavitt, X. Sun, A. Wool, B. Yener. Computing the unmeasured: an algebraic approach to mapping the Internet, in: Proc. IEEE Infocom, Anchorage, AK (2001).
	[15]	K.G. Anagnostakis, M. Greenwald, R. Ryger, Cing: Measuring network-internal delay using only existing infrastructure, in: Proc. IEEE Infocom, San Francisco, CA (2003).
	[17]	Calvert, Kenneth L., Griffioen, James, Mullins, Billy, Sehgal, Amit and Wen, Su, Concast: Design and implementation of an active network service. IEEE Journal on Selected Areas of Communications. v19 i3. 404-409.
	[18]	Wolf, Tilman and Choi, Sumi Yunsun, Aggregated hierarchical multicast for active networks. Proceedings of IEEE MILCOM.
	[19]	David Tucker, Survey of Searching Methods in Internet Peer-to-Peer Systems. Available from: http://www.medianet.kent.edu/surveys/IAD03F-dtucker/index.html.
	[20]	Alok Prakash, A Survey of Advanced Search in P2P Networks. Available from: http://www.medianet.kent.edu/surveys/IAD06S-p2psearch-alok/index.html.
	[21]	Javed I. Khan , Asrar U. Haque, An Active Programmable Harness for Measurement of Composite Network States, Proceedings of the First International Conference on Networking-Part 2, p.628-638, July 09-13, 2001
	[22]	Javed I. Khan, Asrar U. Haque, Maximizing Lifetime of Power Limited Network with Active Minimum Spanning Tree Aggregation, in: Proceedings of the 17th Parallel and Distributed Computing and Systems, PDCS 2004, MIT, Cambridge, USA, ACTA Press, ISBN: 0-88986-421-7, November 9-11, 2004, v.439-055.
	[23]	Asrar U. Haque, Javed I. Khan, Optimum Bounded Wait Communication for Systems with Distributed Autonomous Components, Technical Report, Kent State University, August 2006. Available from: http://medianet.kent.edu/techreports.html.