Browse Prior Art Database

Distributed Locally-Driven Update Commit Algorithm

IP.com Disclosure Number: IPCOM000012323D
Published in the IP.com Journal: Volume 3 Issue 5 (2003-05-25)
Included in the Prior Art Database: 2003-May-25
Document File: 3 page(s) / 127K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

A Distributed Replicated System (DRS) consists of a number of computing sites, each providing the same application and containing replicas of the same data items. The problem that typically arises in such a system is the tradeoff between replica consistency and performance (site response time). Replica consistency, or more precisely, inconsistency, is quantified by the misread probability, Pm , and site response time is represented by the waiting time, t, before a read request can be processed. This tradeoff is a general problem in the DRS. The lower the misread probability gets, the longer the waiting time becomes and vice versa. In the ideal case, these two parameters are zero. Since this can never be fulfilled, the general requirement is that both parameters should be minimized as much as possible. A number of techniques have been proposed in the literature coping with this tradeoff.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 3

S

© SIEMENS AG 2003 file: 2003J03833.doc page: 1

Distributed Locally-Driven Update Commit Algorithm

Idea: Marjan Bozinovski, DK-Aalborg; Robert Seidel, DE-Munich

A Distributed Replicated System (DRS) consists of a number of computing sites, each providing the same application and containing replicas of the same data items. The problem that typically arises in such a system is the tradeoff between replica consistency and performance (site response time). Replica consistency, or more precisely, inconsistency, is quantified by the "misread probability", Pm , and site response time is represented by the "waiting time", [g116] , before a read request can be processed. This tradeoff is a general problem in the DRS. The lower the misread probability gets, the longer the waiting time becomes and vice versa. In the ideal case, these two parameters are zero. Since this can never be fulfilled, the general requirement is that both parameters should be minimized as much as possible. A number of techniques have been proposed in the literature coping with this tradeoff.

A proposal shown in this text consists of one main invention and two sub-inventions stemming from the main invention. The main invention is introduced in the Update Commit Algorithm (UCA). The core of this invention is to delay a read request processing at a site by an appropriate time interval referred to as the "waiting time", keeping in mind the inverse proportional relation between the misread probability and waiting time. By choosing the adequate value of the waiting time, any misread probability can be achieved.

The idea of delaying the read processing stems from the following reasoning. The arrival time of a read request is considered to be the reference time. Only the State Update Messages (SUMs) in the queue of uncommitted SUMs (referred to as the Total Order List, TOL), that happened before this reference time and arrived at the site before the moment of commitment, are taken into account. The peer sites also produce SUMs, and it takes some time until they arrive at the site. If the site waits for sufficiently long time, all the SUMs that happened before the reference time eventually arrive and the read operation will be correct. On the contrary, if the site does not wait for sufficiently long time, the probability of having a misread becomes non-zero.

There are two sub-inventions, meaning two proposals for update commit algorithms, derived from the main invention. The first proposed UCA controls the predefined QoS (Quality of Service) waiting time per site, hereafter referred to as "UCA with predefined QoS waiting time [g116]qos". The second proposed UCA controls the predefined QoS misread probability per site, hereafter referred to as "UCA with predefined QoS misread probability Pqos".

The schematic drawing that summarizes the basic principle of the invention is shown in Figure 1. When a read request arrives as shown in Figure 1, the processing of the read request is...