Decentralized evaluation of associative and commutative functions

Author

Hsieh, C. Samuel

Author_Institution

Dept. of Comput. Sci., Vanderbilt Univ., Nashville, TN, USA

fYear

1989

fDate

5-9 Jun 1989

Firstpage

9

Lastpage

11

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(N¹c/-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;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1989., 9th International Conference on

Conference_Location

Newport Beach, CA

Print_ISBN

0-8186-1953-8

Type

conf

DOI

10.1109/ICDCS.1989.37924

Filename

37924