Synchronization algorithms and concurrent programming

Title:

Personal Author:

Taubenfeld, Gadi

Publication Information:

England : Pearson Education Limited, 2006

Physical Description:

xv, 423 p. : ill. ; 24 cm.

ISBN:

9780131972599

Subject Term:

Electronic data processing -- Distributed processing

Parallel programming (Computer science)

Computer algorithms

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010204507	QA76.9.D5 T38 2006	Open Access Book	Book	Searching... Unknown

The first textbook that focuses purely on Synchronization - a fundamental challenge in Computer Science that is fast becoming a major performance and design issue for concurrent programming on modern architectures, and for the design of distributed systems.

Author Notes

Gadi Taubenfeld is an Associate Professor of Computer Science at the Interdisciplinary Center in Herzliya, Israel

Preface	p. xiii
Key Features	p. xv
Chapter 1 Introduction	p. 1
1.1 Concurrent and Distributed Computing	p. 1
1.1.1 Data Communication and Synchronization	p. 2
1.1.2 Contention, Cooperation, and Resource Allocation	p. 2
1.2 Synchronization: Two Examples	p. 3
1.2.1 Why is Synchronization Difficult?	p. 3
1.2.2 Too Much Milk	p. 4
1.2.3 The Coordinated Attack Problem	p. 8
1.3 The Mutual Exclusion Problem	p. 10
1.3.1 The Problem	p. 11
1.3.2 Comments	p. 13
1.4 Complexity Measures	p. 14
1.4.1 Counting Steps	p. 14
1.4.2 Counting Time Units	p. 15
1.4.3 Counting Remote Memory Accesses	p. 16
1.4.4 Space Complexity	p. 17
1.5 Processes, Threads and Scheduling	p. 17
1.5.1 Processes	p. 17
1.5.2 Threads	p. 18
1.5.3 Scheduling	p. 19
1.6 Bibliographic Notes	p. 22
1.7 Problems	p. 23
Chapter 2 Mutual Exclusion Using Atomic Registers: Basic Topics	p. 31
2.1 Algorithms for Two Processes	p. 31
2.1.1 Peterson's Algorithm	p. 32
2.1.2 Kessels' Single-writer Algorithm	p. 35
2.2 Tournament Algorithms	p. 37
2.2.1 A Solution Based on Peterson's Algorithm	p. 38
2.2.2 A Solution Based on Kessels' Algorithm	p. 40
2.3 A Fast Mutual Exclusion Algorithm	p. 42
2.3.1 Lamport's Fast Algorithm	p. 42
2.3.2 A Simple Observation	p. 46
2.4 Starvation-free Algorithms	p. 47
2.4.1 Basic Definitions	p. 48
2.4.2 The Bakery Algorithm	p. 49
2.4.3 The Black-White Bakery Algorithm	p. 55
2.5 Tight Space Bounds	p. 58
2.5.1 A Lower Bound	p. 59
2.5.2 An Upper Bound: The One-bit Algorithm	p. 63
2.5.3 Computing with Infinitely Many Processes	p. 66
2.6 Automatic Discovery of Algorithms	p. 68
2.6.1 Three Algorithms	p. 69
2.6.2 More Results	p. 70
2.7 Bibliographic Notes	p. 71
2.8 Problems	p. 74
Chapter 3 Mutual Exclusion Using Atomic Registers: Advanced Topics	p. 97
3.1 Local Spinning Algorithms	p. 97
3.1.1 Local Spinning	p. 98
3.1.2 The Local Spinning Black-White Bakery Algorithm	p. 99
3.1.3 A Local Spinning Tournament Algorithm	p. 101
3.2 Adaptive Algorithms	p. 104
3.2.1 Basic Definitions	p. 104
3.2.2 A Simple Adaptive Algorithm	p. 105
3.2.3 An Adaptive Tournament Algorithm	p. 110
3.2.4 The Adaptive Black-White Bakery Algorithm	p. 116
3.2.5 An Impossibility Result	p. 119
3.3 Fault-tolerant Algorithms	p. 122
3.3.1 Defining Fault-tolerance	p. 123
3.3.2 A Fault-tolerant Algorithm	p. 124
3.3.3 Self-stabilization	p. 127
3.4 Symmetric Algorithms	p. 129
3.4.1 Symmetric Deadlock-free Algorithms	p. 130
3.4.2 Symmetric Starvation-free Algorithms	p. 132
3.4.3 Observations about Concurrency	p. 132
3.5 Bibliographic Notes	p. 133
3.6 Problems	p. 136
Chapter 4 Blocking and Non-blocking Synchronization	p. 147
4.1 Synchronization Primitives	p. 147
4.1.1 Atomic Operations	p. 148
4.1.2 Objects	p. 150
4.1.3 Non-atomic Registers	p. 152
4.2 Collision Avoidance using Test-and-set Bits	p. 153
4.2.1 A Trivial Deadlock-free Algorithm	p. 153
4.2.2 Using a Test-and-test-and-set Bit	p. 154
4.2.3 Collision Avoidance Locks	p. 155
4.2.4 A Fast Starvation-free Algorithm	p. 156
4.3 The Ticket Algorithm using RMW Objects	p. 157
4.3.1 The Ticket Algorithm	p. 158
4.3.2 A Simple Lower Bound	p. 159
4.4 Local Spinning using Strong Primitives	p. 160
4.4.1 Anderson's Queue-based Algorithm	p. 160
4.4.2 Graunke and Thakkar Queue-based Algorithm	p. 163
4.4.3 The MCS Queue-based Algorithm	p. 165
4.5 Concurrent Data Structures	p. 169
4.5.1 Non-blocking and Wait-free Synchronization	p. 170
4.5.2 A Non-blocking Concurrent Queue Algorithm	p. 171
4.6 Semaphores	p. 176
4.6.1 Constant Space Starvation-free Algorithm	p. 178
4.6.2 Correctness Proof	p. 179
4.7 Monitors	p. 181
4.8 Fairness of Shared Objects	p. 183
4.8.1 Fairness Properties	p. 183
4.8.2 Basic Results	p. 184
4.8.3 Algorithms	p. 186
4.9 Bibliographic Notes	p. 189
4.10 Problems	p. 194
Chapter 5 Barrier Synchronization	p. 203
5.1 Barriers	p. 203
5.2 Atomic Counter	p. 204
5.2.1 A Simple Counter Barrier	p. 204
5.2.2 A Local Spinning Counter Barrier	p. 206
5.2.3 A Barrier without Shared Memory Initialization	p. 206
5.3 Test-and-set Bits	p. 207
5.3.1 A Constant Space Barrier	p. 207
5.3.2 An Asymmetric Barrier without Memory Initialization	p. 208
5.4 Combining Tree Barriers	p. 210
5.5 A Tree-based Barrier	p. 212
5.6 The Dissemination Barrier	p. 213
5.7 The See-Saw Barrier	p. 215
5.7.1 The Algorithm	p. 215
5.7.2 Correctness Proof	p. 218
5.8 Semaphores	p. 219
5.9 Bibliographic Notes	p. 221
5.10 Problems	p. 222
Chapter 6 The l-exclusion Problem	p. 227
6.1 The Problem	p. 227
6.2 Algorithms Using Atomic Registers	p. 229
6.2.1 An l-starvation-free Algorithm	p. 229
6.2.2 An Unbounded FIFO-enabling Algorithm	p. 231
6.3 Using a Single Read-modify-write Register	p. 234
6.3.1 The Counter Algorithm	p. 234
6.3.2 The Numbered Ticket Algorithm	p. 235
6.3.3 The Unbounded Colored Ticket Algorithm	p. 236
6.3.4 The Bounded Colored Ticket Algorithm	p. 238
6.4 The l-assignment Problem	p. 241
6.5 Bibliographic Notes	p. 243
6.6 Problems	p. 245
Chapter 7 Multiple Resources	p. 249
7.1 Deadlocks	p. 249
7.2 Deadlock Prevention	p. 252
7.2.1 Two Phase Locking and Timestamping-ordering	p. 252
7.2.2 The Total Order Theorem	p. 253
7.3 Deadlock Avoidance: The Problem of Deadly Embrace	p. 255
7.3.1 The Problem	p. 255
7.3.2 The Banker's Algorithm	p. 256
7.4 The Dining Philosophers Problem	p. 259
7.4.1 The Problem	p. 259
7.4.2 Preliminaries	p. 260
7.4.3 Concurrency and Robustness	p. 262
7.5 Hold and Wait Strategy	p. 263
7.5.1 The LR Algorithm	p. 263
7.5.2 The LLR Algorithm	p. 265
7.5.3 A Lower Bound	p. 267
7.5.4 Relating Concurrency and Robustness	p. 268
7.6 Wait and Release Strategy	p. 269
7.7 Randomized Algorithms	p. 271
7.7.1 The Free Philosophers Algorithm	p. 272
7.7.2 The Courteous Philosophers Algorithm	p. 272
7.8 Bibliographic Notes	p. 274
7.9 Problems	p. 276
Chapters 8 Classical Synchronization Problems	p. 281
8.1 The Producer-Consumer Problem	p. 281
8.1.1 Atomic Registers	p. 282
8.1.2 Atomic Counter	p. 283
8.1.3 General Semaphores	p. 284
8.1.4 Binary Semaphores	p. 284
8.1.5 Monitors	p. 286
8.1.6 Sleep and Wakeup	p. 287
8.2 Readers and Writers	p. 288
8.2.1 Semaphores	p. 289
8.2.2 Monitors	p. 290
8.3 The Sleeping Barber	p. 292
8.4 The Cigarette Smoker's Problem	p. 294
8.5 More Synchronization Problems	p. 297
8.5.1 Group Mutual Exclusion and Room Synchronization	p. 297
8.5.2 Concurrent Reading and Writing of Clocks	p. 298
8.5.3 The Choice Coordination Problem	p. 299
8.5.4 The H[subscript 2]O Problem	p. 300
8.5.5 The Roller Coaster Problem	p. 300
8.6 Bibliographic Notes	p. 301
8.7 Problems	p. 303
Chapter 9 Consensus	p. 307
9.1 The Problem	p. 307
9.2 Three Simple Consensus Algorithms	p. 308
9.2.1 A Single 3-valued Read-modify-write Register	p. 308
9.2.2 Two Processes, Two Read-modify-write Bits	p. 309
9.2.3 Many Processes, Four Read-modify-write Bits	p. 310
9.3 Consensus without Memory Initialization	p. 311
9.3.1 The Algorithm	p. 312
9.3.2 Correctness Proof	p. 314
9.4 Reaching Consensus Using a Shared Queue	p. 316
9.5 Impossibility of Consensus with One Faulty Process	p. 318
9.5.1 A Formal Model	p. 318
9.5.2 Basic Observations	p. 320
9.5.3 The Impossibility Theorem	p. 321
9.6 The Relative Power of Synchronization Primitives	p. 325
9.7 The Universality of Consensus	p. 328
9.7.1 Basic Definitions	p. 328
9.7.2 A Universal Construction	p. 330
9.8 Bibliographic Notes	p. 334
9.9 Problems	p. 336
Chapter 10 Timing-based Algorithms	p. 343
10.1 Timing-based Systems	p. 343
10.2 Mutual Exclusion with Known Delays	p. 345
10.3 Fast Mutual Exclusion with Known Delays	p. 347
10.3.1 The Algorithm	p. 347
10.3.2 Correctness Proof	p. 348
10.4 Consensus with Known Delays	p. 352
10.5 Fast Consensus with Known Delays	p. 353
10.5.1 The Algorithm	p. 353
10.5.2 Correctness Proof	p. 354
10.6 Fast Consensus with Unknown Delays	p. 355
10.6.1 The Algorithm	p. 355
10.6.2 Correctness Proof	p. 357
10.7 Fast Mutual Exclusion with Unknown Delays	p. 359
10.7.1 The Algorithm	p. 359
10.7.2 Correctness Proof	p. 361
10.7.3 Time Complexity	p. 363
10.8 Bibliographic Notes	p. 365
10.9 Problems	p. 366
Bibliography	p. 373
Index	p. 417

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents