NDLI: On serializability of iterated transactions

Please wait, while we are loading the content...

Language constructs and support systems for distributed computing

Distributed communication via global buffer

Language concepts for distributed processing of large arrays

Dynamic systems and their distributed termination

UIDs as internal names in a distributed file system

Testing incomplete specifications of distributed systems

Distributed multi-destination routing: The constraints of local information

Efficient schemes for parallel communication

Randomized parallel communication (Preliminary Version)

Distributed allocation with pools of servers

Real time resource allocation in distributed systems

Finding safe paths in a faulty environment

Four combinators for concurrency

A refinement of Kahn's semantics to handle non-determinism and communication (Extended Abstract)

On the distribution of an assertion

Bounds on information exchange for Byzantine Agreement

Understanding and using asynchronous message passing (Preliminary Version)

Can message buffers be characterized in linear temporal logic?

A distributed algorithm for detecting resource deadlocks in distributed systems

On-the-fly deadlock prevention

Edge locks and deadlock avoidance in distributed systems

Why control of the concurrency level in distributed systems is more fundamental than deadlock management

On serializability of iterated transactions

Proving safety and liveness of communicating processes with examples

Concurrency control algorithms for multiversion database systems

A multi-version concurrency scheme with no rollbacks

A distributed transaction processing protocol based on majority consensus

N-processors graphs distributively achieve perfect matchings in O(log2N) beats

On parallel searching (Extended Abstract)

Folding and unrolling systolic arrays (Preliminary Version)

On serializability of iterated transactions

Content Provider	ACM Digital Library
Author	Roucairol, G. Fle, M. P.
Abstract	In the literature on serializability (see [1]), a transaction is considered to be a finite sequence of operations. As a step towards the handling of more complex evolutions of processes, we assume in this paper that the sequence of operations performed by a transaction may be infinitely often repeated as for instance, might behave a pre-existing service process in an operating system. (Remark that the classical “critical section” problem can be viewed as a particular case of the serializability problem). Therefore, a behaviour of a system of transactions will be understood herein as an infinite behaviour. The equivalence which is generally used is such that two behaviours are said equivalent if the relative ordering of so-called conflicting operations is the same in both behaviours ; this notion of conflict being deduced from the way operations of different transactions access to shared data. If we call correct a behaviour which is equivalent in that sense to a sequential behaviour, we shall say (section 3) that a system of transactions is maximally concurrent if its set of possible behaviours is the set of correct ones. In section 4, we characterize a maximally concurrent system by a property of the prefixes of its behaviours. This property extends a result from Papadimitriou [6] and allows us to point out that the classical “two phases locking” synchronization algorithm [2] does not guaranty maximal concurrency. This property will also be used in section 5 in order to show that the language of the prefixes of behaviours of a maximally concurrent system is a regular language (main result). It means that the serializability of iterated transactions can be finitely controlled. In section 6, we consider the problem of fair serializability. We describe a synchronization algorithm allowing only those behaviours which are correct and fair (every transaction is performed infinitely often). In that case, this algorithm needs an unbounded amount of memory. The use of this algorithm is illustrated in order to provide a starvation-free synchronization to the well-known five philosophers problem.
Starting Page	194
Ending Page	200
Page Count	7
File Format	PDF
ISBN	0897910818
DOI	10.1145/800220.806697
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1982-08-18
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Specifying Strict Serializability of Iterated Transactions in Propositional Temporal Logic

Specifying Strict Serializability of Iterated Transactions in Propositional Temporal Logic

Safe open-nested transactions through ownership ( SPAA '08 )

On the serializability of transactions in shared dataspaces with temporary data

Algebraic Specification of Serializability for Partitioned Transactions

On Herbrand semantics and conflict serializability of read-write transactions (extended abstract)

Specifying Strict Serializability of Iterated Transactions in Propositional Temporal Logic

A CTL Specification of Serializability for Transactions Accessing Uniform Data

Specifying strict serializability of iterated transactions in propositional temporal logic.

On serializability of iterated transactions

Similar Documents

Specifying Strict Serializability of Iterated Transactions in Propositional Temporal Logic

Specifying Strict Serializability of Iterated Transactions in Propositional Temporal Logic

Safe open-nested transactions through ownership ( SPAA '08 )

On the serializability of transactions in shared dataspaces with temporary data

Algebraic Specification of Serializability for Partitioned Transactions

On Herbrand semantics and conflict serializability of read-write transactions (extended abstract)

Specifying Strict Serializability of Iterated Transactions in Propositional Temporal Logic

A CTL Specification of Serializability for Transactions Accessing Uniform Data

Specifying strict serializability of iterated transactions in propositional temporal logic.

On serializability of iterated transactions