Context Adaptive Cooperation
As shown by Reliable Broadcast and Consensus, cooperation among a set of independent computing entities (sequential processes) is a central issue in distributed computing. Considering -process asynchronous message-passing systems where some processes can be Byzantine, this paper introduces a new cooperation abstraction denoted Context-Adaptive Cooperation (CAC). While Reliable Broadcast is a one-to- cooperation abstraction and Consensus is an -to- cooperation abstraction, CAC is a -to- cooperation abstraction where the parameter () depends on the run and remains unknown to the processes. Moreover, the correct processes accept the same set of pairs ( is the value proposed by ) from the proposer processes, where and, as , remains unknown to the processes (except in specific cases). Those values are accepted one at a time in different orders at each process. Furthermore, CAC provides the processes with an imperfect oracle that gives information about the values that they may accept in the future. In a very interesting way, the CAC abstraction is particularly efficient in favorable circumstances. To illustrate its practical use, the paper describes in detail two applications that benefit from the abstraction: a fast consensus implementation under low contention (named Cascading Consensus), and a novel naming problem.