Browse Prior Art Database

Asynchronous Start Byzantine Agreement

IP.com Disclosure Number: IPCOM000038583D
Original Publication Date: 1987-Feb-01
Included in the Prior Art Database: 2005-Jan-31
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+4]

Abstract

This invention relates to a method for reducing message traffic in a multi-node network by folding over multiple occurring Byzantine Agreements in favor of the one earliest in time. This invention allows a Byzantine Agreement indicating that some event has occurred to be initiated asynchronously by one or more processors without incurring the full message cost of processing all such agreements independently. When such initiations happen within a short interval of time, the agreements they precipitate can be merged into one agreement with time of generation corresponding to the earliest of the initiations. Let X be the earliest initiation for such merged agreement.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Asynchronous Start Byzantine Agreement

This invention relates to a method for reducing message traffic in a multi-node network by folding over multiple occurring Byzantine Agreements in favor of the one earliest in time. This invention allows a Byzantine Agreement indicating that some event has occurred to be initiated asynchronously by one or more processors without incurring the full message cost of processing all such agreements independently. When such initiations happen within a short interval of time, the agreements they precipitate can be merged into one agreement with time of generation corresponding to the earliest of the initiations. Let X be the earliest initiation for such merged agreement. Then within the time required to achieve one Byzantine Agreement after X, all correct processors will agree on the value X as the earliest beginning for this merged agreement. The set of such earliest times partitions time into intervals in which the initiations differ by, at most, the time for one Byzantine Agreement.

Let d be the phase duration used for Byzantine Agreement. Each processor keeps a table of special events. Corresponding to each event is an entry in the table for the time of generation of a Byzantine Agreement on that event. This entry is initially set to -+.

If a message indicating event E is received for processing as part of a Byzantine Agreement, its time of generation is compared with the table entry for E. Agreement Merge Filter Let the table entry be Te .

Let the time of generation of the message be Tm . If Te+(t+1)d<Tm, then TeETm, the count for merged events of type E is incremented by 1, and the message is processed. If Te<Tm<Te+(t+1)d, then the message is ignored. _ _ If Te-(t+1)d<Tm<Te, then TeETm, and th...