Models for Concurrency (Algebra, Logic and Applications, Vol 11)

✍ Scribed by Uri Abraham

• Publisher: CRC Press
• Year: 2020
• Tongue: English
• Leaves: 249
• Edition: 1
• Category: Library

✦ Synopsis

Concurrent systems are generally understood in terms of behavioral notions. Models for Concurrency analyzes the subject in terms of events and their temporal relationship rather than on global states. It presents a comprehensive analysis of model theory applied to concurrent protocols, and seeks to provide a theory of concurrency that is both intuitively appealing and rigorously based on mathematical foundations.
The book is divided into three main sections. The first introduces the required concepts from model theory, details the structures that are used to model concurrency, gives an in-depth description and explanation of the semantics of a simple language that allows concurrent execution of sequential programs, and deals with the question of resolving executions into higher-level and lower-level granularities. The second and third sections apply the theory developed to practical examples, and an exposition of the producer/consumer problem with details of two solutions is given. The author also deals with message passing, as opposed to shared memory.

✦ Table of Contents

Cover
Half Title
Title Page
Copyright Page
Table of Contents
Preface
Part 1 Semantics of distributed protocols
1. Elements of model theory
1. Structures
1.1. Examples of multi-sorted structures
2. First-order languages and satisfaction
2.1. Satisfaction
2.2. Logical implication
2.3. Substructures and reducts
2.4. Composite structures
3. An example: a mutual exclusion protocol
3.1. Proof of the Mutual Exclusion property
2. System executions
1. Time and interval orderings
1.1. Finiteness conditions
2. Definition of system executions
2.1. Global time
2.2. Parallel composition of systems
3. Higher and lower-level events
3.1. Beginning of events
4. Specification of registers and communication devices
4.1. Specifying communication devices
5. Achilles and the Tortoise
5.1. Concurrency
5.2. Zeno‘s paradox
3. Semantics of concurrent protocols
1. A protocol language and its flowcharts
1.1. Serial and concurrent procedures
1.2. Flowcharts of protocols
1.3. States and transitions
2. Semantics of flowcharts
2.1. Histories and executions of flowcharts
2.2. External semantics
3. Histories as structures
4. The Pitcher/Catcher example
4. Correctness of protocols
1. Mutual exclusion revisited
5. Higher-level events
1. Pitcher/Catcher revisited
2. Procedure calls
3. KanGaroo and LoGaroo
3.1. Formalizing the proof
4. The Aimless Protocols
4.1. Higher-level relations
5. Local registers
Part 2 Shared-variable communication
6. On the Producer/Consumer problem: buffers and semaphores
1. The Producer/Consumer problem
2. Buffer cells
3. Semaphores
3.1. The textbook specification
3.2. Abstract specification of semaphores
4. Load/unload with semaphores
5. A Multiple Process Mutual Exclusion Protocol
7. Circular buffers
1. Unbounded sequence numbers
1.1. The function activate
1.2. Safety
1.3. Liveness
2. Bounded sequence numbers
Part 3 Message Communication
8. Specification of channels
1. Channels
1.1. Capacity of a channel
2. A redressing protocol
3. Sliding Window Axioms
4. A Multiple Producer Protocol
9. A sliding window protocol
1. Protocol analysis and definition and higher-level events
1.1. Higher-level functions
2. The Sliding Window Axioms hold
2.1. Complete SEND/RECEIVE/ACK events
3. Correctness of the protocol
10. Broadcasting and causal ordering
1. Send/Receive Network Signature
2. Message Domain
3. Causality
4. Causality preservation and deliveries
4.1. Uniform deliveries
5. Time-stamp vectors
11. Uniform delivery in group communication
1. A generic Uniform Delivery Protocol
1.1. The Time-Stamp Vector Axioms are satisfied
1.2. Data Buffers
1.3. The All-Ack Protocol
2. Correctness of the generic protocol
3. The Early Delivery Protocol
4. A worked-out example
Epilogue: Formal and informal correctness proofs
References
Index