Sinopsis
Excerpt from Tree Locking on Changing Trees
We must now decide on a set Of Operations powerful enough to introduce arbitrary changes to the tree graph, yet restricted enough to ensure that the graph remain a tree in all intermediate states. B-tree splits and merges, for example, are clearly too restrictive in that they can only produce balanced trees and can not even change the height of any given node. Addition or removal of a single edge, on the other hand.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
"Sinopsis" puede pertenecer a otra edición de este libro.
Reseña del editor
Excerpt from Tree Locking on Changing Trees
Abstract: The tree locking protocol is a deadlock-free method of concurrency control defined and verified by Silberschatz and Kedem for data organized in a directed tree. Can the tree protocol work for applications that change the tree? We define a set of three operations capable of changing any tree to any other tree and show that the tree protocol continues to ensure serializability and deadlock-freedom in the presence of these operations.
1. Introduction
A locking protocol is a set of rules for locking data items such that any concurrent computation following those rules is guaranteed to satisfy some set of conditions. Typically, these conditions may include serializability, deadlock freedom, or order preservation, which are all rigorously defined below. For example, the two-phase protocol guarantees serializability and order preservation, but not deadlock freedom, by forbidding an action (a term we use interchangeably with "transaction") to place a new lock after releasing a lock.
In [SK80], Silberschatz and Kedem introduced a locking protocol that guaranteed serializability and deadlock freedom without requiring two-phasedness. It has since become known as the tree protocol since it is based on the assumption that that the data resides in a set of nodes organized in a directed tree. In brief, the protocol allows an action to begin by locking any node, but to place subsequent locks only on the children of its currently locked nodes, as long as it does not lock a node it has previously unlocked. No restrictions are placed on unlocking nodes.
It is an unstated assumption of the tree protocol that the tree graph remain the same throughout a computation.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
"Sobre este título" puede pertenecer a otra edición de este libro.
