Data science and Complex networks szeminárium

Mean estimation, also known as average consensus, is an important
computational primitive in decentralized systems. When the average of
large vectors has to be computed, like in distributed data mining
applications, reducing the communication cost becomes a key design
goal. One way of reducing communication cost is to add dynamic
stateful encoders and decoders to traditional mean estimation
protocols. In this approach, each element of a vector message is
encoded in a few bits (often only one bit) and decoded by the
recipient node. However, due to this encoding and decoding mechanism,
these protocols are much more sensitive to benign failure such as
message drop and message delay. Properties such as mass conservation
are harder to guarantee. Accordingly, known approaches are formulated
under strong assumptions such as reliable communication, atomic
non-overlapping transactions or even full synchrony. In this work, we
propose a communication efficient algorithm that supports known codecs
even if transactions overlap and the nodes are not synchronized. The
algorithm is based on push-pull averaging, with novel features to
support fault tolerance and compression. As an independent
contribution, we also propose a novel codec, called the pivot codec.
We demonstrate experimentally that our algorithm improves the
performance of existing codecs and the novel pivot codec dominates the
competing codecs in the scenarios we studied.