Title :
Decentralized evaluation of associative and commutative functions
Author :
Hsieh, C. Samuel
Author_Institution :
Dept. of Comput. Sci., Vanderbilt Univ., Nashville, TN, USA
Abstract :
A family of distributed algorithms for decentralized evaluation of associative and commutative functions is presented. It is shown that if N is the member of processes which cooperate to evaluate such a function, then for each positive integer c⩽1 there is an algorithm in the family that carries out the computation in c rounds of message exchange and requires a total of cN(N1c/-1) messages to be sent. Using c as a design parameter, this family of algorithms permits a tradeoff between the number of rounds of message exchange and the total number of messages passed among the processes. The class of functions considered underlies many decentralized protocols, such as decentralized extrema finding and distributed transaction commit
Keywords :
distributed processing; message switching; protocols; associative functions; commutative functions; computation; decentralized evaluation; decentralized extrema finding; decentralized protocols; design parameter; distributed algorithms; distributed transaction commit; message exchange; rounds; Algorithm design and analysis; Centralized control; Clocks; Communication networks; Communication system control; Computer networks; Computer science; Distributed algorithms; Protocols; Telecommunication network reliability;
Conference_Titel :
Distributed Computing Systems, 1989., 9th International Conference on
Conference_Location :
Newport Beach, CA
Print_ISBN :
0-8186-1953-8
DOI :
10.1109/ICDCS.1989.37924
