Abstract:
In the last years, the round elimination technique has been successfully used to prove many lower bounds for the LOCAL model of distributed computing. In 2019, Brandt proved that this technique can be theoretically automated: given a locally checkable problem Π that can be solved in T rounds of communication, it is possible to mechanically define a problem Π′ that requires T − 1 rounds, and by repeating this procedure many times one can obtain interesting lower and upper bounds.In this work, we show that this technique can be automated also in practice: round eliminator is a computer program where we can feed our favorite locally checkable problem and obtain lower (and sometimes upper) bounds for it, automatically.