Message optimal fully decentralised evaluation of associative and commutative functions

Decentralised protocols can be characterised by successive rounds of message interchanges. We show that at least kN([N¹k/]-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([N¹ k/]-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