Performing work in broadcast networks
(2006) In Distributed Computing 18(6). p.435451 Abstract
 We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multipleaccess channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Omega(t + p root t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work O(t + p root t). Another algorithm, for... (More)
 We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multipleaccess channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Omega(t + p root t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work O(t + p root t). Another algorithm, for the channel without collision detection, performs work O(t + p root t + p min {f, t}), where f < p is the number of failures. This algorithm is proved to be optimal, provided that the adversary is restricted in failing no more than f stations. Finally, we consider the question if randomization helps against weaker adversaries for the channel without collision detection. A randomized algorithm is developed which performs the expected minimum amount O(t + p root t) of work, provided that the adversary may fail a constant fraction of stations and it has to select failureprone stations prior to the start of an execution of the algorithm. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/404592
 author
 Chlebus, BS ; Kowalski, DR and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2006
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 adversary, multipleaccess channel, failstop failure, independent tasks, distributed algorithm
 in
 Distributed Computing
 volume
 18
 issue
 6
 pages
 435  451
 publisher
 Springer
 external identifiers

 wos:000238681000003
 scopus:33744774192
 ISSN
 01782770
 DOI
 10.1007/s0044600501534
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 ec8be40a77394f47b33e212a2a9c3aaa (old id 404592)
 date added to LUP
 20160401 12:16:40
 date last changed
 20210929 01:48:33
@article{ec8be40a77394f47b33e212a2a9c3aaa, abstract = {We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multipleaccess channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Omega(t + p root t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work O(t + p root t). Another algorithm, for the channel without collision detection, performs work O(t + p root t + p min {f, t}), where f < p is the number of failures. This algorithm is proved to be optimal, provided that the adversary is restricted in failing no more than f stations. Finally, we consider the question if randomization helps against weaker adversaries for the channel without collision detection. A randomized algorithm is developed which performs the expected minimum amount O(t + p root t) of work, provided that the adversary may fail a constant fraction of stations and it has to select failureprone stations prior to the start of an execution of the algorithm.}, author = {Chlebus, BS and Kowalski, DR and Lingas, Andrzej}, issn = {01782770}, language = {eng}, number = {6}, pages = {435451}, publisher = {Springer}, series = {Distributed Computing}, title = {Performing work in broadcast networks}, url = {http://dx.doi.org/10.1007/s0044600501534}, doi = {10.1007/s0044600501534}, volume = {18}, year = {2006}, }