Cambridge Distributed Computing Principles Algorithms and Systems

Cover......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Dedication......Page 7 Contents......Page 9 Background......Page 17 Readership......Page 18 Access to resources......Page 19 1.1 Definition......Page 21 1.2 Relation to computer system components......Page 22 1.3 Motivation......Page 23 1.4.1 Characteristics of parallel systems......Page 25 1.4.2 Flynn’s taxonomy......Page 30 Coupling......Page 31 Granularity of a program......Page 32 1.5 Message-passing systems versus shared memory systems......Page 33 1.6.1 Blocking/non-blocking, synchronous/asynchronous primitives......Page 34 1.6.2 Processor synchrony......Page 38 1.7 Synchronous versus asynchronous executions......Page 39 1.7.3 Emulations......Page 41 1.8.1 Distributed systems challenges from a system perspective......Page 42 Time and global state in a distributed system......Page 44 Synchronization/coordination mechanisms......Page 45 Data replication, consistency models, and caching......Page 46 Distributed shared memory abstraction......Page 47 Reliable and fault-tolerant distributed systems......Page 48 Load balancing......Page 49 Mobile systems......Page 50 Ubiquitous or pervasive computing......Page 51 Distributed agents......Page 52 1.9 Selection and coverage of topics......Page 53 1.10 Chapter summary......Page 54 1.11 Exercises......Page 55 1.12 Notes on references......Page 56 References......Page 57 2.1 A distributed program......Page 59 2.2 A model of distributed executions......Page 60 Causal precedence relation......Page 61 2.3 Models of communication networks......Page 62 2.4 Global state of a distributed system......Page 63 2.4.1 Global state......Page 64 2.5 Cuts of a distributed computation......Page 65 2.6 Past and future cones of an event......Page 66 2.7 Models of process communications......Page 67 2.10 Notes on references......Page 68 References......Page 69 3.1 Introduction......Page 70 3.2.2 Implementing logical clocks......Page 72 3.3.1 Definition......Page 73 No strong consistency......Page 74 3.4.1 definition......Page 75 Isomorphism......Page 76 3.4.3 On the size of vector clocks......Page 77 3.5 Efficient implementations of vector clocks......Page 79 3.5.1 Singhal–Kshemkalyani’s differential technique......Page 80 3.5.2 Fowler–Zwaenepoel’s direct-dependency technique......Page 82 3.6 Jard–Jourdan’s adaptive technique......Page 85 3.7.1 Definition......Page 88 3.8 Virtual time......Page 89 3.8.1 Virtual time definition......Page 90 3.8.2 Comparison with Lamport’s logical clocks......Page 91 3.8.3 Time warp mechanism......Page 92 Antimessages and the rollback mechanism......Page 93 Global virtual time......Page 95 Memory management and flow control......Page 96 Snapshots and crash recovery......Page 97 3.9.1 Motivation......Page 98 3.9.2 Definitions and terminology......Page 99 Clock offset and delay estimation......Page 100 3.10 Chapter summary......Page 101 References......Page 104 4.1 Introduction......Page 107 4.2.1 System model......Page 110 4.2.3 Interpretation in terms of cuts......Page 111 4.2.4 Issues in recording a global state......Page 112 4.3.1 Chandy–Lamport algorithm......Page 113 The algorithm......Page 114 4.3.2 Properties of the recorded global state......Page 115 4.4.1 Spezialetti–Kearns algorithm......Page 117 Efficient dissemination of the recorded snapshot......Page 118 4.4.2 Venkatesan’s incremental snapshot algorithm......Page 119 4.4.3 Helary’s wave synchronization method......Page 120 4.5 Snapshot algorithms for non-FIFO channels......Page 121 4.5.1 Lai–Yang algorithm......Page 122 4.5.2 Li et al.’s algorithm......Page 123 4.5.3 Mattern’s algorithm......Page 125 4.6 Snapshots in a causal delivery system......Page 126 4.6.2 Channel state recording in Acharya–Badrinath algorithm......Page 127 4.6.3 Channel state recording in Alagar–Venkatesan algorithm......Page 128 4.7 Monitoring global state......Page 129 4.8 Necessary and sufficient conditions for consistent global snapshots......Page 130 Difference between a zigzag path and a causal path......Page 132 Consistent global snapshots......Page 133 4.9 Finding consistent global snapshots in a distributed computation......Page 134 First observation......Page 135 Second observation......Page 136 Third observation......Page 137 4.9.2 Manivannan–Netzer–Singhal algorithm for enumerating consistent snapshots......Page 138 Construction of an R-graph......Page 139 4.10 Chapter summary......Page 141 4.12 Notes on references......Page 142 References......Page 143 5.1 Topology abstraction and overlays......Page 146 5.2.1 Application executions and control algorithm executions......Page 148 5.2.3 Symmetric and asymmetric algorithms......Page 149 5.2.6 Adaptive algorithms......Page 150 5.2.8 Execution inhibition......Page 151 5.2.9 Synchronous and asynchronous systems......Page 152 Process failure models [26]......Page 153 5.2.12 Wait-free algorithms......Page 154 5.3 Complexity measures and metrics......Page 155 5.4 Program structure......Page 157 5.5.1 Synchronous single-initiator spanning tree algorithm using flooding......Page 158 5.5.2 Asynchronous single-initiator spanning tree algorithm using flooding......Page 160 Design 1......Page 163 Design 2......Page 165 5.5.4 Asynchronous concurrent-initiator depth first search spanning tree algorithm......Page 166 5.5.5 Broadcast and convergecast on a tree......Page 168 5.5.6 Single source shortest path algorithm: synchronous Bellman–Ford......Page 169 5.5.7 Distance vector routing......Page 170 5.5.9 All sources shortest paths: asynchronous distributed Floyd–Warshall......Page 171 Asynchronous algorithm (Algorithm 5.9)......Page 175 Synchronous algorithm (Algorithm 5.10)......Page 176 5.5.11 Minimum-weight spanning tree (MST) algorithm in a synchronous system......Page 177 5.5.12 Minimum-weight spanning tree (MST) in an asynchronous system......Page 182 General observations on synchronous and asynchronous algorithms......Page 183 A simple synchronizer......Page 184 The synchronizer......Page 185 The synchronizer......Page 186 5.7 Maximal independent set (MIS)......Page 189 5.8 Connected dominating set......Page 191 5.9 Compact routing tables......Page 192 5.10 Leader election......Page 194 5.11 Challenges in designing distributed graph algorithms......Page 195 5.12.1 Problem definition......Page 196 Read......Page 197 5.12.4 Converging to an replication scheme......Page 198 5.13 Chapter summary......Page 202 5.14 Exercises......Page 203 5.15 Notes on references......Page 205 References......Page 206 Notation......Page 209 6.1.1 Asynchronous executions......Page 210 6.1.3 Causally ordered (CO) executions......Page 211 6.1.4 Synchronous execution (SYNC)......Page 214 6.2 Asynchronous execution with synchronous communication......Page 215 6.2.1 Executions realizable with synchronous communication (RSC)......Page 216 Asynchronous programs on synchronous systems......Page 219 6.3 Synchronous program order on an asynchronous system......Page 220 6.3.1 Rendezvous......Page 221 6.3.2 Algorithm for binary rendezvous......Page 222 6.4 Group communication......Page 225 6.5 Causal order (CO)......Page 226 6.5.1 The Raynal–Schiper–Toueg algorithm [22]......Page 227 6.5 Causal order (CO)......Page 228 Multicast M43......Page 233 Processing at P6......Page 234 6.6 Total order......Page 235 Sender......Page 236 Complexity......Page 238 6.7 A nomenclature for multicast......Page 240 6.8 Propagation trees for multicast......Page 241 6.9 Classification of application-level multicast algorithms......Page 245 Privilege-based algorithms......Page 246 Destination agreement algorithms......Page 247 6.10 Semantics of fault-tolerant group communication......Page 248 6.11.1 Reverse path forwarding (RPF) for constrained flooding......Page 250 Steiner tree problem......Page 251 6.11.3 Multicast cost functions......Page 252 Delay-bounded minimal Steiner tree problem......Page 253 6.11.5 Core-based trees......Page 255 6.13 Exercises......Page 256 6.14 Notes on references......Page 258 References......Page 259 7.1 Introduction......Page 261 7.2 System model of a distributed computation......Page 262 7.3.2 Formal description......Page 263 7.3.3 Discussion......Page 264 Basic idea......Page 265 7.4.2 Correctness of the algorithm......Page 266 7.5 A spanning-tree-based termination detection algorithm......Page 267 A problem with the algorithm......Page 268 The basic idea......Page 269 The algorithm description......Page 270 7.5.4 An example......Page 271 7.6 Message-optimal termination detection......Page 273 7.6.1 The main idea......Page 274 7.6.2 Formal description of the algorithm......Page 275 7.7 Termination detection in a very general distributed computing model......Page 277 7.7.2 Notation......Page 278 Informal description......Page 279 Formal description......Page 280 Informal description......Page 281 Formal description......Page 282 Assumptions......Page 283 7.8.2 A naive counting method......Page 284 7.8.3 The four counter method......Page 285 7.8.4 The sceptic algorithm......Page 286 Formal description......Page 287 7.8.6 Vector counters method......Page 288 Formal description......Page 290 7.9 Termination detection in a faulty distributed system......Page 292 The concept of flow invariant......Page 293 7.9.2 Taking snapshots......Page 294 Data structures......Page 295 7.9.2 Taking snapshots......Page 296 7.9.4 Performance analysis......Page 298 7.11 Exercises......Page 299 References......Page 300 8.1 The muddy children puzzle......Page 302 8.2.1 Knowledge operators......Page 303 8.2.2 The muddy children puzzle again......Page 304 8.2.3 Kripke structures......Page 305 Scenario A......Page 307 8.2.5 Properties of knowledge......Page 308 8.3 Knowledge in synchronous systems......Page 309 8.4.1 Logic and definitions......Page 310 8.4.2 Agreement in asynchronous systems......Page 311 Eventual common knowledge......Page 312 8.4.4 Concurrent common knowledge......Page 313 Three-phase send-inhibitory algorithm......Page 315 Complexity......Page 316 8.5 Knowledge transfer......Page 318 8.6 Knowledge and clocks......Page 320 8.7 Chapter summary......Page 321 8.8 Exercises......Page 322 References......Page 323 9.1 Introduction......Page 325 9.2.1 System model......Page 326 9.2.3 Performance metrics......Page 327 Best and worst case performance......Page 328 9.3 Lamport’s algorithm......Page 329 Correctness......Page 330 9.4 Ricart–Agrawala algorithm......Page 332 Correctness......Page 333 9.5 Singhal’s dynamic information-structure algorithm......Page 335 Data structures......Page 336 9.5.1 Description of the algorithm......Page 337 Achieving mutual exclusion......Page 339 Low load condition......Page 340 9.6 Lodha and Kshemkalyani’s fair mutual exclusion algorithm......Page 341 9.6.2 Description of the algorithm......Page 342 9.6.4 Message complexity......Page 345 9.7 Quorum-based mutual exclusion algorithms......Page 347 9.8 Maekawa’s algorithm......Page 348 Correctness......Page 349 Handling deadlocks......Page 350 9.9.1 Constructing a tree-structured quorum......Page 351 9.9.4 Examples of tree-structured quorums......Page 353 9.9.5 The algorithm for distributed mutual exclusion......Page 355 9.11 Suzuki–Kasami’s broadcast algorithm......Page 356 Performance......Page 358 9.12 Raymond’s tree-based algorithm......Page 359 9.12.1 The HOLDER variables......Page 360 Data structures......Page 361 MAKE_REQUEST......Page 362 Message overtaking......Page 363 Deadlock is impossible......Page 364 Starvation is impossible......Page 365 9.12.5 Cost and performance analysis......Page 366 9.12.7 Node failures and recovery......Page 367 9.14 Exercises......Page 368 9.15 Notes on references......Page 369 References......Page 370 10.2 System model......Page 372 10.3.1 Deadlock handling strategies......Page 373 Detection of deadlocks......Page 374 10.4 Models of deadlocks......Page 375 10.4.3 The OR model......Page 376 10.4.5 The p model......Page 377 10.5.1 Path-pushing algorithms......Page 378 10.5.4 Global state detection-based algorithms......Page 379 10.6 Mitchell and Merritt’s algorithm for the single-resource model......Page 380 10.7 Chandy–Misra–Haas algorithm for the AND model......Page 382 The algorithm......Page 383 Basic idea......Page 384 10.9 Kshemkalyani–Singhal algorithm for the P-out-of- model......Page 385 10.9.1 Informal description of the algorithm......Page 387 The problem of termination detection......Page 388 10.9.2 The algorithm......Page 389 10.10 Chapter summary......Page 394 10.12 Notes on references......Page 395 References......Page 396 11.1 Stable and unstable predicates......Page 399 Termination [20]......Page 400 11.2 Modalities on predicates......Page 402 11.3 Centralized algorithm for relational predicates......Page 404 11.4 Conjunctive predicates......Page 408 11.4.1 Interval-based centralized algorithm for conjunctive predicates......Page 409 11.4.2 Global state-based centralized algorithm for , where is conjunctive......Page 412 11.5.1 Distributed state-based token algorithm for, Possibly (Phi) where Phi is conjunctive......Page 415 11.5.2 Distributed interval-based token algorithm for Definitely (Phi), where is conjunctive......Page 417 11.5.3 Distributed interval-based piggybacking algorithm for Possibly (Phi), where Phi is conjuctive......Page 421 11.6 Further classification of predicates......Page 424 11.7 Chapter summary......Page 425 11.8 Exercises......Page 426 11.9 Notes on references......Page 427 References......Page 428 12.1 Abstraction and advantages......Page 430 12.2 Memory consistency models......Page 433 12.2.1 Strict consistency/atomic consistency/linearizability......Page 434 Implementations......Page 435 12.2.2 Sequential consistency......Page 437 Implementations......Page 438 Local-write algorithm......Page 439 12.2.3 Causal consistency......Page 440 12.2.4 PRAM (pipelined RAM) or processor consistency......Page 442 12.2.5 Slow memory......Page 443 12.2.7 Other models based on synchronization instructions......Page 444 Release consistency [12]......Page 445 Entry consistency [9]......Page 446 12.3.1 Lamport’s bakery algorithm......Page 447 12.3.2 Lamport’s WRWR mechanism and fast mutual exclusion......Page 449 12.3.3 Hardware support for mutual exclusion......Page 452 12.5 Register hierarchy and wait-free simulations......Page 454 12.5.1 Construction 1: SRSW safe to MRSW safe......Page 457 12.5.3 Construction 3: boolean MRSW safe to integer-valued MRSW safe......Page 458 12.5.4 Construction 4: boolean MRSW safe to boolean MRSW regular......Page 459 12.5.5 Construction 5: boolean MRSW regular to integer-valued MRSW regular......Page 460 12.5.6 Construction 6: boolean MRSW regular to integer-valued MRSW atomic......Page 462 12.5.7 Construction 7: integer MRSW atomic to integer MRMW atomic......Page 464 12.5.8 Construction 8: integer SRSW atomic to integer MRSW atomic......Page 465 Achieving linearizability......Page 466 12.6 Wait-free atomic snapshots of shared objects......Page 467 12.7 Chapter summary......Page 471 12.8 Exercises......Page 472 12.9 Notes on references......Page 473 References......Page 474 13.1 Introduction......Page 476 13.2.1 System model......Page 477 13.2.3 Consistent system states......Page 478 13.2.4 Interactions with the outside world......Page 479 13.2.5 Different types of messages......Page 480 Duplicate messages......Page 481 13.3 Issues in failure recovery......Page 482 13.4.1 Uncoordinated checkpointing......Page 484 13.4.2 Coordinated checkpointing......Page 485 Non-blocking checkpoint coordination......Page 486 13.4.3 Impossibility of min-process non-blocking checkpointing......Page 487 13.4.4 Communication-induced checkpointing......Page 488 Model-based checkpointing......Page 489 13.5.1 Deterministic and non-deterministic events......Page 490 The no-orphans consistency condition......Page 491 13.5.2 Pessimistic logging......Page 492 13.5.3 Optimistic logging......Page 493 13.5.4 Causal logging......Page 494 Second phase......Page 496 13.6.2 The rollback recovery algorithm......Page 497 13.7 Juang–Venkatesan algorithm for asynchronous checkpointing and recovery......Page 498 13.7.1 System model and assumptions......Page 499 Basic idea......Page 500 Description of the algorithm......Page 501 13.8 Manivannan–Singhal quasi-synchronous checkpointing algorithm......Page 503 Properties......Page 504 An explanation......Page 506 Handling the replay of messages......Page 509 Handling of received messages......Page 510 Features......Page 511 Notation......Page 512 13.9.2 Informal description of the algorithm......Page 513 Handling in-transit orphan messages......Page 514 The rollback protocol......Page 515 13.9.4 Correctness proof......Page 517 13.10 Helary–Mostefaoui–Netzer–Raynal communication-induced protocol......Page 519 To checkpoint or not to checkpoint?......Page 520 Reducing the number of forced checkpoints......Page 521 13.10.2 The checkpointing protocol......Page 523 13.11 Chapter summary......Page 525 13.13 Notes on references......Page 526 References......Page 527 14.1 Problem definition......Page 530 The Byzantine agreement problem......Page 532 The interactive consistency problem......Page 533 14.2 Overview of results......Page 534 14.3 Agreement in a failure-free system (synchronous or asynchronous)......Page 535 14.4.1 Consensus algorithm for crash failures (synchronous system)......Page 536 14.4.3 Upper bound on Byzantine processes......Page 537 Byzantine agreement tree algorithm: exponential (synchronous system)......Page 539 Phase-king algorithm for consensus: polynomial (synchronous system)......Page 546 14.5.1 Impossibility result for the consensus problem......Page 549 14.5.2 Terminating reliable broadcast......Page 551 14.5.4 k-set consensus......Page 552 Algorithm outline......Page 553 Notation......Page 555 Convergence rate of approximation......Page 556 Correctness......Page 557 Problem definition......Page 558 Algorithm......Page 559 Correctness......Page 562 14.6.1 Impossibility result......Page 564 14.6.2 Consensus numbers and consensus hierarchy [14]......Page 567 FIFO queue......Page 569 Compare&Swap......Page 570 Read–modify–write abstraction......Page 571 14.6.3 Universality of consensus objects [14]......Page 572 A non-blocking universal algorithm......Page 573 14.6.4 Shared memory k-set consensus......Page 576 14.6.5 Shared memory renaming......Page 577 14.6.6 Shared memory renaming using splitters......Page 580 14.7 Chapter summary......Page 582 14.8 Exercises......Page 583 14.9 Notes on references......Page 584 References......Page 585 15.1 Introduction......Page 587 15.2.1 The system model......Page 588 15.2.2 Failure detectors......Page 589 Completeness......Page 590 Eventual accuracy......Page 591 15.2.5 Reducibility of failure detectors......Page 592 15.2.6 Reducing weak failure detector W to a strong failure detector S......Page 593 A correctness argument......Page 594 15.2.7 Reducing an eventually weak failure detector . to an eventually strong failure detector…......Page 595 An explanation of the algorithm......Page 596 15.3 The consensus problem......Page 597 15.3.2 A solution using strong failure detector S......Page 598 An explanation of the algorithm......Page 599 15.3.3 A solution using eventually strong failure detector…......Page 600 An explanation of the algorithm......Page 602 15.4 Atomic broadcast......Page 603 An explanation of the algorithm......Page 604 15.6 The weakest failure detectors to solve fundamental agreement problems......Page 605 15.6.1 Realistic failure detectors......Page 606 15.6.2 The weakest failure detector for consensus......Page 608 15.7 An implementation of a failure detector......Page 609 15.8 An adaptive failure detection protocol......Page 611 Assumptions......Page 612 The protocol FDL......Page 613 Properties of FDL......Page 615 References......Page 616 16.1 Introduction......Page 618 16.2.1 Basis of authentication......Page 619 16.2.4 Notation......Page 620 16.2.5 Design principles for cryptographic protocols......Page 621 16.3 Protocols based on symmetric cryptosystems......Page 622 Weaknesses......Page 623 Weaknesses......Page 624 16.3.4 A protocol based on an authentication server......Page 625 16.3.5 One-time password scheme......Page 626 Protocol description......Page 627 16.3.6 Otway–Rees protocol......Page 629 Weaknesses......Page 630 The authentication protocol......Page 631 Weaknesses......Page 634 16.4.1 The basic protocol......Page 635 16.4.2 A modified protocol with a certification authority......Page 636 16.4.3 Needham and Schroeder protocol......Page 637 An impersonation attack on the protocol......Page 638 16.4.4 SSL protocol......Page 639 SSL handshake protocol......Page 640 How SSL provides authentication......Page 641 16.5 Password-based authentication......Page 642 16.5.1 Encrypted key exchange (EKE) protocol......Page 643 16.5.2 Secure remote password (SRP) protocol......Page 644 16.6 Authentication protocol failures......Page 645 16.7 Chapter summary......Page 646 16.9 Notes on references......Page 647 References......Page 648 17.1 Introduction......Page 651 17.2 System model......Page 652 17.3 Definition of self-stabilization......Page 654 17.3.1 Randomized and probabilistic self-stabilization......Page 655 Dijkstra’s self-stabilizing token ring system......Page 656 First solution......Page 657 Second solution......Page 658 Ghosh’s solution......Page 661 17.4.2 Uniform vs. non-uniform networks......Page 662 17.4.3 Central and distributed demons......Page 663 17.4.4 Reducing the number of states in a token ring......Page 664 17.4.6 Mutual exclusion......Page 665 17.4.7 Costs of self-stabilization......Page 666 17.5.1 Layering and modularization......Page 667 Topology-based primitives......Page 668 17.6 Communication protocols......Page 669 17.7 Self-stabilizing distributed spanning trees......Page 670 17.8.1 Dolev, Israeli, and Moran algorithm......Page 672 17.8.3 Arora and Gouda algorithm for spanning-tree construction......Page 675 17.8.5 Afek and Bremler algorithm for spanning-tree construction......Page 676 17.9 An anonymous self-stabilizing algorithm for 1-maximal independent set in trees......Page 677 Description of algorithm......Page 678 17.10 A probabilistic self-stabilizing leader election algorithm......Page 680 17.11.1 Compilers for sequential programs......Page 682 17.11.2 Compilers for asynchronous message passing systems......Page 683 17.11.3 Compilers for asynchronous shared memory systems......Page 684 Fault tolerance......Page 685 Symmetry......Page 687 17.14 Limitations of self-stabilization......Page 688 Pseudo-stabilization......Page 689 17.16 Exercises......Page 690 References......Page 691 18.1 Introduction......Page 697 18.1.2 Application layer overlays......Page 698 18.2 Data indexing and overlays......Page 699 Structured overlays......Page 700 18.3.1 Unstructured overlays: properties......Page 701 18.3.3 Search in Gnutella and unstructured overlays......Page 702 Search strategies......Page 703 18.3.4 Replication strategies......Page 704 18.3.5 Implementing replication strategies......Page 707 18.4.1 Overview......Page 708 18.4.2 Simple lookup......Page 709 18.4.3 Scalable lookup......Page 710 Node joins......Page 711 Node failures and departures......Page 714 18.5.1 Overview......Page 715 18.5.2 CAN initialization......Page 716 18.5.3 CAN routing......Page 717 18.5.4 CAN maintainence......Page 718 18.5.5 CAN optimizations......Page 720 18.6.1 Overview......Page 721 Prefix routing......Page 722 Router Table......Page 723 18.6.3 Object publication and object search......Page 725 18.6.4 Node insertion......Page 726 18.6.5 Node deletion......Page 727 18.7.1 Fairness: a game theory application......Page 728 18.7.2 Trust or reputation management......Page 729 Routing rule......Page 730 18.8.2 Bounds on DHT storage and routing distance......Page 731 18.9 Graph structures of complex networks......Page 732 18.10.1 Basic laws and their definitions......Page 734 18.10.2 Properties of the Internet......Page 735 Classification of scale-free networks......Page 737 Impact on network diameter......Page 738 Impact on network partitioning......Page 739 18.12 Small-world networks......Page 740 18.13 Scale-free networks......Page 741 18.13.1 Master-equation approach......Page 742 18.14 Evolving networks......Page 743 Continuum theory analysis......Page 745 18.16 Exercises......Page 747 18.17 Notes on references......Page 748 References......Page 749 Index......Page 751 Few branches of mathematics have been more influential in the social sciences than game theory. In recent years, it has become an essential tool for all social scientists studying the strategic behaviour of competing individuals, firms and countries. However, the mathematical complexity of game theory is often very intimidating for students who have only a basic understanding of mathematics. Insights into Game Theory addresses this problem by providing students with an understanding of the key concepts and ideas of game theory without using formal mathematical notation. The authors use four very different topics (college admission, social justice and majority voting, coalitions and co-operative games, and a bankruptcy problem from the Talmud) to investigate four areas of game theory. The result is a fascinating introduction to the world of game theory and its increasingly important role in the social sciences