Reliable broadcasts and communication models: tradeoffs and lower bounds (Q1112599)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Reliable broadcasts and communication models: tradeoffs and lower bounds
scientific article

    Statements

    Reliable broadcasts and communication models: tradeoffs and lower bounds (English)
    0 references
    0 references
    0 references
    0 references
    1988
    0 references
    Reliable broadcast is a mechanism by which a processor in a distributed system disseminates a value to all other processors in the presence of both communication and processor failures. Protocols to achieve reliable broadcast are at the heart of most fault-tolerant applications. We characterize the execution time of reliable broadcast protocols as a function of the communication model. This model includes similar communication structures such as fully-connected point-to-point graphs, linear chains, rings, broadcast networks (such as Ethernet) and buses. We derive a parameterized protocol that implements reliable broadcast for any member within this class. We obtain lower bound results that show the optimality of our protocols. The lower bound results identify a time complexity gap between systems where processors may only fail to send messages, and systems where processors may fail both to send and to receive messages. The tradeoffs that our results reveal between performance, resiliency and network cost offer many new alternatives previously not considered in designing fault-tolerant systems.
    0 references
    distributed systems
    0 references
    Byzantine agreement
    0 references
    hardware/software tradeoff
    0 references
    reliable broadcast
    0 references
    protocols
    0 references
    communication model
    0 references
    broadcast networks
    0 references
    lower bound results
    0 references
    time complexity
    0 references
    fault-tolerant systems
    0 references

    Identifiers