Efficient Implementation of Synchronous Communication OverAsynchronous Networks

Report ID: 
1993-04
Authors: 
Manhoi Choy and Ambuj K. Singh
Date: 
1993-02-01 04:00:00

Abstract

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.

Document

File 1993-04.ps