Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Distributed algorithms for finding centers and medians in networks
Korach E., Rotem D., Santoro N. ACM Transactions on Programming Languages and Systems6 (3):380-401,1984.Type:Article
Date Reviewed: Mar 1 1985

Many distributed algorithms for computing a property :G p in a network :G v of processors have been proposed in the recent literature. This paper describes two such algorithms for computing centres and medians in networks. Both algorithms are provided for synchronous (asynchronous) tree networks and general networks. Lower bounds and optimality of tree-center and tee-median algorithms have been proved. For both these algorithms the message complexity (i.e., the number of messages exchanged) is O(n:9Ie) and the time complexity is O(n), where n is the number of nodes and e is the number of edges in the network. The paper is well written and the algorithms are clearly described. The reviewer recommends this paper for everyone working on distributed algorithms.

Reviewer:  M. S. Krishnamoorthy Review #: CR108698
Bookmark and Share
 
Network Topology (C.2.1 ... )
 
 
Distributed Applications (C.2.4 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Network Topology": Date
A protocol-less scheme for bridging between IEEE 802 local area networks
Kummer P., Tasker R., Linge N., Ball E. Computer Networks and ISDN Systems 12(2): 81-87, 1987. Type: Article
Jul 1 1988
Packet, circuit, and virtual circuit switching
Gerla M., Prentice-Hall, Inc., Upper Saddle River, NJ, 1986. Type: Book (9789780131650503)
Feb 1 1987
FDDI: an introduction to Fiber Distributed Data Interface
Michael W., William J. J., Pieper K., Digital Press, Newton, MA, 1993. Type: Book (9781555580933)
Nov 1 1993
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy