Performing work in broadcast networks

BS Chlebus, DR Kowalski, Andrzej Lingas

    Research output: Contribution to journalArticlepeer-review

    12 Citations (SciVal)

    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 < 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.
    Original languageEnglish
    Pages (from-to)435-451
    JournalDistributed Computing
    Volume18
    Issue number6
    DOIs
    Publication statusPublished - 2006

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • adversary
    • multiple-access channel
    • fail-stop failure
    • independent tasks
    • distributed algorithm

    Fingerprint

    Dive into the research topics of 'Performing work in broadcast networks'. Together they form a unique fingerprint.

    Cite this