Back to Search
Start Over
Set-constrained delivery broadcast: A communication abstraction for read/write implementable distributed objects.
- Source :
-
Theoretical Computer Science . Sep2021, Vol. 886, p49-68. 20p. - Publication Year :
- 2021
-
Abstract
- • New fault-tolerant communication abstraction. • Simple implementations of read/write implementable objects. • Efficient implementations of snapshots and lattice agreement. This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ′ , no process delivers first a set of messages including m ′ and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data types), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*BROADCASTING industry
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 886
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 152313601
- Full Text :
- https://doi.org/10.1016/j.tcs.2021.06.044