Reliable broadcasts and communication models: tradeoffs and lower bounds (Q1112599): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Ozalp Babaoglu / rank | |||
Property / author | |||
Property / author: Ozalp Babaoglu / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient fault-tolerant routings in networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Authenticated Algorithms for Byzantine Agreement / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3666268 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A lower bound for the time to assure interactive consistency / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Byzantine Generals Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4319638 / rank | |||
Normal rank |
Revision as of 11:12, 19 June 2024
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
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