MESSAGE OPTIMAL FULLY DECENTRALIZED EVALUATION OF ASSOCIATIVE AND COMMUTATIVE FUNCTIONS

Abstract

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.