COMPUTING ASSOCIATIVE FUNCTIONS DISTRIBUTIVELY IN SPITE OF LINK FAILURES

Repeated computation of associative functions is central to many async hronous distributed algorithms reported in the literature. We present efficient distributed algorithms for computing associative functions i n spite of undetectable link failures in non-partitioned distributed s ystems. Two distributed; algorithms are presented for function computa tion assuming that the distributed system is preprocessed by a one-tim e preprocessing step that uses O(\E\ \V\) messages (where \E\ and \V\ are the number of links and the number of nodes of the system, respect ively). The first algorithm tolerates single link failures using O(\V\ log \V\) messages and the second algorithm, which is an extension of the first algorithm, copes with the simultaneous failure of k links us ing O(k\E\ log \V\) messages. Efficient computation of associative fun ctions in the presence of multiple link failures has been an open prob lem, and our work solves this open problem. (C) 1994 Academic Press, I nc.