Browse Prior Art Database

Byzantine Agreement Via Periodic Exchange of Tables

IP.com Disclosure Number: IPCOM000042275D
Original Publication Date: 1984-May-01
Included in the Prior Art Database: 2005-Feb-03
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Aghili, H: AUTHOR [+2]

Abstract

This invention relates to a method for achieving Byzantine Agreement among networking CPUs which periodically exchange tables by modifying the tables in order to support Byzantine message traffic. Involved is shared memory for ensuring consistency of replicated data and/or tables. The advantage of this method is that it requires no extra messages over those already being exchanged so long as the space available in the tables being exchanged is not exceeded. Of course, the total number of messages involved in the exchange of the tables will usually be much larger than the minimum number of messages required for Byzantine Agreement, but if these messages are being sent anyway, there will be no extra cost.

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

Page 1 of 2

Byzantine Agreement Via Periodic Exchange of Tables

This invention relates to a method for achieving Byzantine Agreement among networking CPUs which periodically exchange tables by modifying the tables in order to support Byzantine message traffic. Involved is shared memory for ensuring consistency of replicated data and/or tables. The advantage of this method is that it requires no extra messages over those already being exchanged so long as the space available in the tables being exchanged is not exceeded. Of course, the total number of messages involved in the exchange of the tables will usually be much larger than the minimum number of messages required for Byzantine Agreement, but if these messages are being sent anyway, there will be no extra cost. Thus, the type of agreement ideally suited to this method is one involving the transmission of some value normally stored in the exchange tables. This method is not suited to the transmission of large numbers of messages or lengthy messages that might arise, for example, in applications of Byzantine Agreement to Distributed Transaction Management as described in the IBM Technical Disclosure Bulletin 26, 4250-4251 (January 1984). Periodic Exchange Network There is assumed an environment consisting of a network of processors with at least t+1 connectivity where t will be the Byzantine reliability of the agreement. Each processor periodically sends a message to each of its immediate neighbors requesting a response in the form of an exchange table. Each processor is assumed to know the period of each of the other processors (this can be achieved by making the period of each processor an entry in the table). The exchange table can be viewed as a virtually shared memory. Each entry in the table is accompanied by a time of generation field. When a processor receives a copy of the exchange table, it updates those fields in its table that have earlier times of generation than the corresponding fields on the copy (assuming that the entries on the copy are authentic). There is also assumed an authentication field that accompanies each entry and serves as the vehicle for an authentication protocol. Immediate Byzantine Agreement There is assumed a unit of time that is greater than the maximum period and sufficient for a value to disperse from any processor of the network to all others. It is also presupposed that this unit allows for any deviation in clocks of the processors. As additional constraints, there is a period exchange table with entries partitioned into sets owned by one processor and only the owner of an entry is allowed to independently change its val...