scientific article; zbMATH DE number 4050992
[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.
- Fast distributed algorithms to make mutually coordinated decisions in stringent real time
- A derivation of distributed implementation of Warshall's algorithm
- Efficient asynchronous distributed symmetry breaking
- Constant space and non-constant time in distributed computing
- Efficient distributed algorithms by using the archimedean time assumption
- scientific article; zbMATH DE number 7561283 (Why is no real title available?)
- Time vs bits
- New classes of distributed time complexity
- Distributed protocols against mobile eavesdroppers
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)