Browse Prior Art Database

Attempt/Veto Protocol

IP.com Disclosure Number: IPCOM000059698D
Original Publication Date: 1986-Jan-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Aghili, H: AUTHOR [+3]

Abstract

This invention relates to a method for the distributed performance of actions in consistent order in the presence of faults.

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

Page 1 of 2

Attempt/Veto Protocol

This invention relates to a method for the distributed performance of actions in consistent order in the presence of faults.

Given a set of processors communicating via a point-to-point network of communication links, the invention provides algorithms for allowing any process to initiate an action, for a correctly initiated action to be performed on all correct processors within a bounded amount of time from its initiation, for the action to be performed on all correct processors at the same local clock time, and for all actions to be performed in the same order at every correct processor.

Provision is also made for a unilateral abort of an action by any process at any correct processor. It is assumed that the local clocks of all participating processors are maintained in such a way that they are always synchronized to within a known finite bound DMAX. The actions to be performed are arbitrary and not limited by the algorithms discussed here, but for definiteness, consider the example of updates to a replicated table. The method will meet the requirement that the table of values as of a given clock time on one processor will be identical to that of another as of the same local clock time. The method assumes the existence of a protocol for reaching Byzantine Agreement, and it provides the same reliability: it may be tuned to tolerate a specific number of faults or any number up to partition of the network of correct processors. A key difference between the method and a straightforward extension of known Byzantine Agreement protocols is the provision of end-to-end acknowledgement and unilateral abort by processes outside the scope of the processes that actually perform the Byzantine broadcast. The principal method step involves decoupling the signaling of receipt of a valid Byzantine message from the signaling of the time to perform the action specified by the message. Let BYZT be the time required to perform Byzantine broadcast in the network. An environment is assumed in which a number of processes (users) participate in the Attempt/Veto protocol by calling the interface procedures named ATTEMPT and VETO below and by receiving Byzantine broadcast messages and messages from a local ATTEMPT MONITOR. The following procedures may be called by users: ATTEMPT (A,V,L) taking as inputs an action A, a veto time V, and a list of participants L, supply an attempt identifier I and a timestamp T, and send the message <A,V,L,I,T> as a Byzantine broadcast to L plus all Attempt Managers. VETO (I) taking as input an attempt identifier I, send the message <"veto",I> to all Attempt Managers via Byzantine broadcast. The Attempt/Veto protocol consists of the procedures above plus the following tasks: ATTEMPT MANAGER on receipt of a Byzantine message, if the message is an attempt <A,V,L,I,T>, then if V=0 then PERFT = T+BYZT, if V =0 then PER...