Early Local Decisions in Distributed Agreement

When devising a distributed agreement algorithm, it is common to minimize the time complexity of global decisions, which is typically measured as the number of communication rounds needed for all correct processes to decide. In practice, what we might want to minimize is the time complexity of local decisions, which we define as the number of communication rounds needed for at least one correct process to decide. The motivation of this paper is to figure out whether there is any difference between local and global decision bounds, and if there is, whether the same algorithm can match both bounds. We address these questions for several models and various agreement problems. We show that, in a synchronous model with crash failures, the local decision bound is generally strictly smaller than the global decision bound, and rather surprisingly, depending on the number of failures that occur, these bounds cannot both be achieved by a single algorithm. In synchronous runs of the eventually synchronous model however, we show that the local decision bound is the same as the global bound. All our bounds are tight, i.e., we give optimal algorithms to match each of our bounds.