scientific article; zbMATH DE number 4050992

From MaRDI portal
Publication:3787481





[For the entire collection see Zbl 0635.00015.] This work examines the effect of limited asynchrony on three fundamental problems of distributed computation: The problem of symmetry breaking in a logical ring, that of mutual exclusion, and the problem of readers and writers. We assume our distributed system to be Archimedean in the sense that processors know upper and lower bounds on the message delays and processor speeds. We use the knowledge of these bounds to get algorithms for the above mentioned problems which well improve the efficiency of algorithms presented by previous research. For the symmetry breaking problem we get a protocol which admits arbitrary initiation, and uses only linear number of message bits and linear time on the average. For the mutual exclusion problem we break the lower bound on the number of messages which holds in case of unrestricted asynchrony. We also find an important difference between Archimedean and synchronous networks. Our algorithms are practical in the sense that any existing distributed system up to now follows the Archimedean time assumption.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787481)