Browsing by Author "YUAN, SY"

Now showing 1 - 1 of 1

MESSAGE OPTIMAL FULLY DECENTRALIZED EVALUATION OF ASSOCIATIVE AND COMMUTATIVE FUNCTIONS
(1994-07-01)
YUAN, SY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science
Decentralised protocols can be characterised by successive rounds of message interchanges. In this article, we show that at least kN(right perpendicular N1/k left perpendicular - 1) messages are required for fully decentralised evaluating functions that are both associative and commutative if k rounds of message interchanges are used in an N-node system. We then present a family of fully decentralised algorithms that requires, at most, a total of kN(inverted right perpendicular N1/k inverted left perpendicular - 1) messages to be sent with k rounds of message interchanges. Therefore, the family of algorithms is optimal with respect to the total number of messages exchanged among the processing nodes. The problems which can be modelled as an evaluation of associative and commutative functions include extrema findings and distributed transaction commitments.