Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Performing work in broadcast networks

Chlebus, BS ; Kowalski, DR and Lingas, Andrzej LU (2006) In Distributed Computing 18(6). p.435-451
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 multiple-access 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 multiple-access 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 failure-prone stations prior to the start of an execution of the algorithm. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
adversary, multiple-access channel, fail-stop failure, independent tasks, distributed algorithm
in
Distributed Computing
volume
18
issue
6
pages
435 - 451
publisher
Springer
external identifiers
  • wos:000238681000003
  • scopus:33744774192
ISSN
0178-2770
DOI
10.1007/s00446-005-0153-4
project
VR 2005-4085
language
English
LU publication?
yes
id
ec8be40a-7739-4f47-b33e-212a2a9c3aaa (old id 404592)
date added to LUP
2016-04-01 12:16:40
date last changed
2021-09-29 01:48:33
@article{ec8be40a-7739-4f47-b33e-212a2a9c3aaa,
  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 multiple-access 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 &lt; 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 failure-prone stations prior to the start of an execution of the algorithm.},
  author       = {Chlebus, BS and Kowalski, DR and Lingas, Andrzej},
  issn         = {0178-2770},
  language     = {eng},
  number       = {6},
  pages        = {435--451},
  publisher    = {Springer},
  series       = {Distributed Computing},
  title        = {Performing work in broadcast networks},
  url          = {http://dx.doi.org/10.1007/s00446-005-0153-4},
  doi          = {10.1007/s00446-005-0153-4},
  volume       = {18},
  year         = {2006},
}