Efficient Implementation of Synchronous Communication OverAsynchronous Networks

The implementation of synchronous communication primitives over asynchronousmessage-passing networks is investigated. Efficient algorithms are presentedfor the committee coordination problem and its more dynamic version called thefirst-order interaction problem. A new notion of strong fairness called$1$-$sf$ and algorithms achieving it are described. It is further shown thatany stronger notion of fairness cannot be implemented.