Index

α synchronizer, 226

β synchronizer, 230

γ synchronizer, 230

abort, 233

ACID properties, 254

agreement, 240, 248

AlphaSynch.java, 229

anonymous ring, 210

asynchronous recovery, 272

asynchrony of events, 235

atomic, 66

atomic snapshots, 76

atomicity, 254

Attemptl.java, 20

Attempt2.java, 21

Attempt3.java, 2 1

bakery algorithm, 24

Bakery.java, 25

barrier synchronization, 187

BCell.java, 49

binary semaphore, 31

BinarySemaphore.java, 32

bivalent, 236

bivalent state, 79

BoundedBuffer.java, 35

BoundedBufferMonitor.java, 45

broadcast, 213, 215

busy wait, 31

Byzantine failure, 239

Byzantine General Agreement, 243

Camera.java, 152

CameraLinker.java, 158

CameraTester.java, 160

CamUser.java, 152

causal consistency, 60

causal ordering, 192, 193

causal total order, 203

CausalLinker.java, 195

CausalMessage.java, 194

Cell.java, 50

CentMutex.java, 134

centralized algorithm, 203

CentSensor.java, 167

Chang-Roberts algorithm, 210

Chat.java, 197

checker process, 166

checkpoint, 263

checkpointing, 268

CircToken.java, 145

clocks, 111, 115

clustering, 230

commit, 233

common knowledge, 247

communication-induced checkpointing, 264, 267

commute property, 235

CompSwap.java, 82

CompSwapConsensus.java, 83

concurrent, 115

concurrent object, 53

concurrent queue, 86

concurrent system, 54

condition variables, 42

conditional synchronization, 33

conflict graph, 140

Conriector.java, 102

consensus, 78, 233, 239

consensus number, 79

Consensus.java, 78, 242

ConsensusTester.java, 243

consistency, 254

consistent cut, 166

consistent interval, 185

convergecast, 215

coordinated checkpoints, 263

coordinating general problem, 248

counting semaphores, 32

CountingSemaphore.java, 33

CQueue.java, 86

crash, 239

critical region, 18

critical section, 18, 130

critical state, 79

crumbling wall, 144

DatagramClient. java, 95

datagrams, 92

DatagramServer.java, 93

DatagramSocket, 90

deadlock, 49, 209

deadlocks, 188

debugging, 164

Dekker.java, 29

diffusing computation, 180

Dijkstra and Scholten’s algorithm, 180

dining philosopher, 39

DiningMonitor.java, 47

DiningPhilosopher.java, 41

DinMutex.java, 143

direct-dependency clocks, 122

DirectClock.java, 122

directly precedes, 123

disjunctive normal form, 164

disjunctive predicate, 165

distributed commit, 257

distributed computation, 111, 114

distributed database, 233

distributed objects, 196

distributed systems, 1

DistSensor.java, 174

domain name system, 89

domino effect, 264

DSTerm.java, 183

durability, 255

Election.java, 209

events, 114

failure detection, 112

fairness, 130

fault-tolerant vector clock, 270

Fibonacci.java, 14

FIFO consistency, 62

Fixed dependency after send, 268

flooding algorithm, 213

FooBar.java, 12

fork, 9

FuncUser.java, 217

global checkpoint, 263

global functions, 215

global properties, 164

global snapshot, 151

global snapshot algorithm, 149

global state, 150

GlobalFunc.java, 218

GlobalFuncTester.java, 219

GlobalService.java, 216

grid quorum system, 146

happened-before diagrams, 115

happened-before model, 150

happened-before relation, 114

HelloWorldThread.java, 11

history, 54

HWMutex.java, 28

InetAddress, 89

initial independence, 234

interface definition language, 8

interleaving model, 114

invocation, 54

isolation, 254

KingBGA.java, 245

knowledge, 244

Lamport’s Algorithm for Total Order, 204

LamportClock.java, 117

LamportMutex.java, 137

leader election, 209

legal, 54

lightweight processes, 9

linearizable, 57

Linker, 100

Linker.java, 104

ListenerThread.java, 132

ListQueue.java, 48

liveness, 130

LLSC.java, 84

locally stable, 185

location transparency, 101

lock-free, 65

Lock.java, 18, 130

LockFreeSnapshot.java, 77

LockTester.java, 131

logging, 256

logical clock, 116

majority voting system, 144

marker, 152

matrix clock, 125

MatrixClock.java, 124

maximum recoverable state, 276

message ordering, 191

minimal rollback, 276

monitor, 42

MRMW Register, 74

MRSW Register, 73, 74

MRSW.java, 75

Msg.java, 103

MsgHandler.java, 130

multicast messages, 203

MultiValued.java, 72

MultiWriter.j, 76

mutual exclusion, 18, 129, 203, 280

MyThread.java, 19

name server, 96

Name.java, 99

NameRmiClient.java, 109

NameServer.java, 98

NameService.java, 105

NameServiceImpl.java, 106

NameTable.java, 97

nondeterminism, 191

normal, 62

object serialization, 107

ObjPointer.java, 83

occurred before, 54

omission model, 239

optimistic logging, 269

orphan, 270

parallel system, 1

pessimistic logging, 268

Peterson’s algorithm, 21

Peterson Algorithm.java, 22

Philosopher.java, 40

pointer-swinging, 84

private workspace, 256

process, 8

process-time diagrams, 115

Process.java, 133

producer-consumer problem, 33

ProducerConsumer.java, 37

progress, 22

pulse, 221

quorum, 144

RAMutex.java, 139

reader-writer problem, 36

ReaderWriter.java, 38

receive omission, 239

RecvCamera.java, 155

regular, 66

Regular SRSW Register, 70

RegularBoolean.java, 71

reliable communication, 246

remote method invocations, 101

remote procedure calls, 101

replicated state machines, 205

Resource.java, 41

response, 54

restarts, 270

RestartTask.java, 282

Ricart and Agrawala’s algorithm, 136

ring, 209

RingLeader.java, 211

rmiregistry, 107

rollback, 270

rollback-dependency trackability, 267

run, 115

safe, 66

Safe SRSW Register, 70

SafeBoolean.java, 70

safety, 130

self-stabilizing, 279

semaphore, 31

send omission, 239

SenderCamera.java, 159

Sensor.java, 165

SensorCircToken.java, 170

SensorTester.java, 171

SensorUser.java, 165

SeqMessage.java, 156

SeqQueue.java, 85

sequential consistency, 55

sequential history, 54

serializability, 255

shared clock, 112

shared memory, 112

ShortestPath.java, 179

simple synchronizer, 223

SimpleSynch.java, 224

Skeen’s algorithm, 204

space-time diagrams, 115

spanning tree, 181, 216, 285

SpanTree.java, 214

SRSW Boolean Register, 71

SRSW Multivalued Register, 71

SRSW Register, 73

stable predicate, 163

StableBottom.java, 283

StableNormal.java, 284

StableSpanNonroot.java, 287

StableSpanRoot.java, 286

StableTreeTester.java, 288

starvation-freedom, 22

symmetry, 210

Synch.java, 28

SynchBfsTree.java, 227

SynchLinker.java, 202

synchronizer, 221

Synchronizer.java, 222

synchronous ordering, 196

TermDetector.java, 179

terminating reliable broadcast, 238

termination, 181, 240

TermShortestPath.java, 184

TermToken.java, 186

TestAndSet.java, 27, 81

TestSetConsensus.java, 82

threads, 9

time-based model, 150

Topology.java, 100

total order, 203

transaction, 233, 253

Transmission Control Protocol, 90

tree-based quorum system, 147

Tree.java, 226

triangular quorum system, 146

two-phase commit, 257

two-phase locking, 256

TwoPhaseCoord.java, 259

TwoPhaseParticipant.java, 260

universal, 78

universal construction, 84

Universal Datagram Protocol, 90

universal object, 79

validity, 240

VCLinker.java, 120

vector clock, 118

VectorClock.java, 119

version end-table, 272

wait, 9

wait-for graph, 188

wait-free, 65

weak conjunctive predicate, 166

wheel coterie, 146

z-consistent, 265

zigzag relation, 265