Distributed Systems : An Algorithmic Approach, Second Edition

[BOOK DESCRIPTION]

Distributed Systemsbalanced and straightforward treatment of the underlying theory and practical applications of distributed computing. As in the previous version, the language is kept as unobscured as possible-clarity is given priority over mathematical formalism. This easily digestible text: * Features significant updates that mirror the phenomenal growth of distributed systems * Explores new topics related to peer-to-peer and social networks * Includes fresh exercises, examples, and case studies Supplying a solid understanding of the key principles of distributed computing and their relationship to real-world applications, Distributed Systems: An Algorithmic Approach, Second Edition makes both an ideal textbook and a handy professional reference.

[TABLE OF CONTENTS]

Preface,                                           xxv
Acknowledgments,                                   xxvii
Author,                                            xxix
Section I Background Materials
  Chapter 1 Introduction                           3    (12)
    1.1 What Is A Distributed System?              3    (1)
    1.2 Why Distributed Systems                    4    (1)
    1.3 Examples Of Distributed Systems            5    (3)
    1.4 Important Issues In Distributed Systems    8    (2)
    1.5 Common Subproblems                         10   (1)
    1.6 Implementing A Distributed System          11   (1)
    1.7 Parallel Versus Distributed Systems        12   (1)
    1.8 Bibliographic Notes                        13   (1)
    Exercises                                      13   (2)
  Chapter 2 Interprocess Communication: An         15   (30)
  Overview
    2.1 Introduction                               15   (2)
      2.1.1 Processes And Threads                  15   (1)
      2.1.2 Client-Server Model                    16   (1)
      2.1.3 Middleware                             16   (1)
    2.2 Network Protocols                          17   (9)
      2.2.1 Ethernet                               17   (1)
      2.2.2 Wireless Networks                      18   (2)
      2.2.3 OSI Model                              20   (2)
      2.2.4 IP                                     22   (1)
      2.2.5 Transport Layer Protocols              23   (1)
      2.2.6 Interprocess Communication Using       24   (2)
      Sockets
    2.3 Naming                                     26   (3)
      2.3.1 Domain Name Service                    28   (1)
      2.3.2 Naming Service For Mobile Clients      29   (1)
    2.4 Remote Procedure Call                      29   (3)
      2.4.1 Implementing RPC                       30   (1)
      2.4.2 Sun ONC/RPC                            31   (1)
    2.5 Remote Method Invocation                   32   (1)
    2.6 Messages                                   33   (1)
      2.6.1 Transient And Persistent Messages      33   (1)
      2.6.2 Streams                                34   (1)
    2.7 Web Services                               34   (1)
    2.8 Event Notification                         35   (1)
    2.9 Virtualization: Cloud Computing            35   (5)
      2.9.1 Classification Of Cloud Services       36   (1)
      2.9.2 MapReduce                              37   (2)
      2.9.3 Hadoop                                 39   (1)
    2.10 Mobile Agents                             40   (1)
    2.11 Basic Group Communication Services        40   (1)
    2.12 Concluding Remarks                        41   (1)
    2.13 Bibliographic Notes                       41   (1)
    Exercises                                      42   (3)
Section II Foundational Topics
  Chapter 3 Models For Communication               45   (22)
    3.1 Need Fora Model                            45   (1)
    3.2 Message-Passing Model For Interprocess     45   (5)
    Communication
      3.2.1 Process Actions                        45   (1)
      3.2.2 Channels                               46   (2)
      3.2.3 Synchronous Versus Asynchronous        48   (1)
      Systems
      3.2.4 Real-Time Systems                      49   (1)
    3.3 Shared Variables                           50   (2)
      3.3.1 Linda                                  51   (1)
    3.4 Modeling Mobile Agents                     52   (1)
    3.5 Relationship Among Models                  53   (5)
      3.5.1 Strong And Weak Models                 53   (1)
      3.5.2 Implementing A FIFO Channel Using A    54   (2)
      Non-FIFO Channel
      3.5.3 Implementing Message Passing Using     56   (1)
      Shared Memory
      3.5.4 Implementing Shared Memory Using       56   (2)
      Message Passing
      3.5.5 Impossibility Result With Channels     58   (1)
    3.6 Classification Based On Special            58   (1)
    Properties
      3.6.1 Reactive Versus Transformational       58   (1)
      Systems
      3.6.2 Named Versus Anonymous Systems         59   (1)
    3.7 Complexity Measures                        59   (4)
    3.8 Concluding Remarks                         63   (1)
    3.9 Bibliographic Notes                        63   (1)
    Exercises                                      64   (3)
  Chapter 4 Representing Distributed               67   (16)
  Algorithms: Syntax And Semantics
    4.1 Introduction                               67   (1)
    4.2 Guarded Actions                            67   (3)
    4.3 Nondeterminism                             70   (1)
    4.4 Atomic Operations                          71   (2)
    4.5 Fairness                                   73   (2)
    4.6 Central Versus Distributed Schedulers      75   (3)
    4.7 Concluding Remarks                         78   (1)
    4.8 Bibliographic Notes                        78   (1)
    Exercises                                      79   (4)
  Chapter 5 Program Correctness                    83   (24)
    5.1 Introduction                               83   (1)
    5.2 Correctness Criteria                       84   (5)
      5.2.1 Safety Properties                      84   (2)
      5.2.2 Liveness Properties                    86   (3)
    5.3 Correctness Proofs                         89   (3)
      5.3.1 Quick Review Of Propositional Logic    90   (1)
      5.3.2 Brief Overview Of Predicate Logic      91   (1)
    5.4 Assertional Reasoning: Proving Safety      92   (1)
    Properties
    5.5 Proving Liveness Properties Using          93   (3)
    Well-Founded Sets
    5.6 Programming Logic                          96   (3)
    5.7 Predicate Transformers                     99   (2)
    5.8 Concluding Remarks                         101  (2)
    5.9 Bibliographic Notes                        103  (1)
    Exercises                                      103  (4)
  Chapter 6 Time In A Distributed System           107  (22)
    6.1 Introduction                               107  (2)
      6.1.1 Physical Time                          107  (1)
      6.1.2 Sequential And Concurrent Events       108  (1)
    6.2 Logical Clocks                             109  (3)
    6.3 Vector Clocks                              112  (1)
    6.4 Physical Clock Synchronization             113  (9)
      6.4.1 Preliminary Definitions                113  (3)
      6.4.2 Clock Reading Error                    116  (1)
      6.4.3 Algorithms For Internal                116  (2)
      Synchronization
      6.4.4 Algorithms For External                118  (4)
      Synchronization
    6.5 Concluding Remarks                         122  (1)
    6.6 Bibliographic Notes                        122  (1)
    Exercises                                      122  (7)
Section III Important Paradigms
  Chapter 7 Mutual Exclusion                       129  (24)
    7.1 Introduction                               129  (1)
    7.2 Solutions On Message-Passing Systems       129  (8)
      7.2.1 Lamport's Solution                     130  (2)
      7.2.2 Ricart-Agrawala's Solution             132  (1)
      7.2.3 Maekawa's Solution                     133  (4)
    7.3 Token-Passing Algorithms                   137  (2)
      7.3.1 Suzuki-Kasami Algorithm                137  (1)
      7.3.2 Raymond's Algorithm                    138  (1)
    7.4 Solutions On The Shared-Memory Model       139  (3)
      7.4.1 Peterson's Algorithm                   139  (3)
    7.5 Mutual Exclusion Using Special             142  (2)
    Instructions
      7.5.1 Solution Using Test-And-Set            142  (1)
      7.5.2 Solution Using Load-Linked And         143  (1)
      Store-Conditional
    7.6 Group Mutual Exclusion                     144  (2)
    7.7 Concluding Remarks                         146  (1)
    7.8 Bibliographic Notes                        147  (1)
    Exercises                                      148  (5)
  Chapter 8 Distributed Snapshot                   153  (16)
    8.1 Introduction                               153  (2)
    8.2 Properties Of Consistent Snapshots         155  (1)
      8.2.1 Cuts And Consistent Cuts               155  (1)
    8.3 Chandy-Lamport Algorithm                   156  (6)
      8.3.1 Two Examples                           159  (4)
        8.3.1.1 Example 1: Counting Of Tokens      159  (1)
        8.3.1.2 Example 2: Communicating State     160  (2)
        Machines
    8.4 Lai-Yang Algorithm                         162  (1)
    8.5 Distributed Debugging                      163  (2)
      8.5.1 Constructing The State Lattice         164  (1)
      8.5.2 Evaluating Predicates                  164  (1)
    8.6 Concluding Remarks                         165  (1)
    8.7 Bibliographic Notes                        165  (1)
    Exercises                                      165  (4)
  Chapter 9 Global State Collection                169  (20)
    9.1 Introduction                               169  (1)
    9.2 Elementary Algorithm For All-To-All        170  (2)
    Broadcasting
    9.3 Termination-Detection Algorithms           172  (8)
      9.3.1 Dijkstra-Scholten Algorithm            173  (3)
      9.3.2 Termination Detection On A             176  (3)
      Unidirectional Ring
      9.3.3 Credit-Recovery Algorithm For          179  (1)
      Termination Detection
    9.4 Wave Algorithms                            180  (2)
      9.4.1 Propagation Of Information With        181  (1)
      Feedback
    9.5 Distributed Deadlock Detection             182  (5)
      9.5.1 Resource Deadlock And Communication    182  (2)
      Deadlock
      9.5.2 Detection Of Resource Deadlock         184  (1)
      9.5.3 Detection Of Communication Deadlock    185  (2)
    9.6 Concluding Remarks                         187  (1)
    9.7 Bibliographic Notes                        187  (1)
    Exercises                                      188  (1)
  Chapter 10 Graph Algorithms                      189  (38)
    10.1 Introduction                              189  (1)
    10.2 Routing Algorithms                        190  (11)
      10.2.1 Computation Of Shortest Path          190  (4)
        10.2.1.1 Complexity Analysis               192  (1)
        10.2.1.2 Chandy-Misra Modification Of      193  (1)
        The Shortest Path Algorithm
      10.2.2 Distance-Vector Routing               194  (1)
      10.2.3 Link-State Routing                    195  (2)
      10.2.4 Interval Routing                      197  (3)
        10.2.4.1 Interval Routing Rule             198  (2)
      10.2.5 Prefix Routing                        200  (1)
    10.3 Graph Traversal                           201  (9)
      10.3.1 Spanning Tree Construction            202  (1)
      10.3.2 Tarry's Graph Traversal Algorithm     203  (1)
      10.3.3 Minimum Spanning Tree Construction    204  (6)
        10.3.3.1 Overall Strategy                  206  (1)
        10.3.3.2 Detecting The Least Weight        207  (3)
        Outgoing Edge
        10.3.3.3 Message Complexity                210  (1)
    10.4 Graph Coloring                            210  (4)
      10.4.1 (D + 1)-Coloring Algorithm            211  (1)
      10.4.2 6-Coloring Of Planar Graphs           212  (2)
    10.5 Cole-Vishkin Reduction Algorithm For      214  (4)
    Tree Coloring
    10.6 Maximal Independent Set: Luby's           218  (4)
    Algorithm
    10.7 Concluding Remarks                        222  (1)
    10.8 Bibliographic Notes                       223  (1)
    Exercises                                      223  (4)
  Chapter 11 Coordination Algorithms               227  (22)
    11.1 Introduction                              227  (1)
    11.2 Leader Election                           227  (9)
      11.2.1 Bully Algorithm                       228  (2)
      11.2.2 Maxima Finding On A Ring              230  (4)
        11.2.2.1 Chang-Roberts Algorithm           230  (1)
        11.2.2.2 Franklin's Algorithm              231  (1)
        11.2.2.3 Peterson's Algorithm              232  (2)
      11.2.3 Election In Arbitrary Networks        234  (1)
      11.2.4 Election In Anonymous Networks        235  (1)
    11.3 Synchronizers                             236  (7)
      11.3.1 ABD Synchronizer                      236  (1)
      11.3.2 Awerbuch's Synchronizers              237  (18)
        11.3.2.1 α-Synchronizer              237  (2)
        11.3.2.2 β-Synchronizer               239  (1)
        11.3.2.3 γ-Synchronizer              240  (2)
        11.3.2.4 Performance Of                    242  (1)
        Synchronizer-Based Algorithms
    11.4 Concluding Remarks                        243  (1)
    11.5 Bibliographic Notes                       243  (1)
    Exercises                                      244  (5)
Section IV Faults And Fault-Tolerant Systems
  Chapter 12 Fault-Tolerant Systems                249  (22)
    12.1 Introduction                              249  (1)
    12.2 Classification Of Faults                  250  (3)
    12.3 Specification Of Faults                   253  (2)
    12.4 Fault-Tolerant Systems                    255  (3)
      12.4.1 Masking Tolerance                     255  (1)
      12.4.2 Nonmasking Tolerance                  255  (1)
      12.4.3 Fail-Safe Tolerance                   256  (1)
      12.4.4 Graceful Degradation                  257  (1)
      12.4.5 Detection Of Failures In              257  (1)
      Synchronous Systems
    12.5 Tolerating Crash Failures                 258  (1)
      12.5.1 Double And Triple Modular             258  (1)
      Redundancy
    12.6 Tolerating Omission Failures              259  (6)
      12.6.1 Stenning's Protocol                   260  (1)
      12.6.2 Sliding Window Protocol               261  (2)
      12.6.3 Alternating Bit Protocol              263  (1)
      12.6.4 How TCP Works                         264  (1)
    12.7 Concluding Remarks                        265  (1)
    12.8 Bibliographic Notes                       266  (1)
    Exercises                                      267  (4)
  Chapter 13 Distributed Consensus                 271  (26)
    13.1 Introduction                              271  (2)
    13.2 Consensus In Asynchronous Systems         273  (4)
      13.2.1 Bivalent And Univalent States         273  (4)
    13.3 Consensus In Synchronous Systems:         277  (9)
    Byzantine Generals Problem
      13.3.1 Solution With No Traitor              277  (1)
      13.3.2 Solution With Traitors:               277  (1)
      Interactive Consistency Criteria
      13.3.3 Consensus With Oral Messages          278  (6)
        13.3.3.1 Impossibility Result              279  (1)
        13.3.3.2 Om(M) Algorithm                   280  (4)
      13.3.4 Consensus Using Signed Messages       284  (2)
    13.4 Paxos Algorithm                           286  (3)
      13.4.1 Safety Properties                     287  (1)
      13.4.2 Liveness Properties                   288  (1)
    13.5 Failure Detectors                         289  (5)
      13.5.1 Solving Consensus Using Failure       291  (7)
      Detectors
        13.5.1.1 Consensus Using P                 292  (1)
        13.5.1.2 Consensus Using S                 293  (1)
        13.5.1.3 Rationale                         293  (1)
        13.5.1.4 Implementing A Failure Detector   294  (1)
    13.6 Concluding Remarks                        294  (1)
    13.7 Bibliographic Notes                       294  (1)
    Exercises295  (2)
  Chapter 14 Distributed Transactions              297  (20)
    14.1 Introduction                              297  (1)
    14.2 Classification Of Transactions            298  (1)
      14.2.1 Flat Transactions                     298  (1)
      14.2.2 Nested Transactions                   299  (1)
      14.2.3 Distributed Transactions              299  (1)
    14.3 Implementing Transactions                 299  (2)
    14.4 Concurrency Control And Serializability   301  (3)
      14.4.1 Testing For Serializability           302  (1)
      14.4.2 Two-Phase Locking                     302  (2)
      14.4.3 Concurrency Control Via Time Stamp    304  (1)
      Ordering
    14.5 Atomic Commit Protocols                   304  (5)
      14.5.1 One-Phase Commit                      306  (1)
      14.5.2 Two-Phase Commit                      306  (2)
      14.5.3 Three-Phase Commit                    308  (1)
    14.6 Recovery From Failures                    309  (4)
      14.6.1 Stable Storage                        309  (2)
      14.6.2 Checkpointing And Rollback Recovery   311  (1)
      14.6.3 Message Logging                       312  (1)
    14.7 Concluding Remarks                        313  (1)
    14.8 Bibliographic Notes                       314  (1)
    Exercises                                      314  (3)
  Chapter 15 Group Communication                   317  (22)
    15.1 Introduction                              317  (1)
    15.2 Atomic Multicast                          318  (1)
    15.3 IP Multicast                              319  (2)
      15.3.1 Reverse Path Forwarding               320  (1)
    15.4 Application Layer Multicast               321  (1)
    15.5 Ordered Multicasts                        322  (4)
      15.5.1 Implementing Total Order Multicast    323  (2)
        15.5.1.1 Implementation Using A            323  (1)
        Sequencer
        15.5.1.2 Distributed Implementation        324  (1)
      15.5.2 Implementing Causal Order Multicast   325  (1)
    15.6 Reliable Multicast                        326  (3)
      15.6.1 Scalable Reliable Multicast           327  (1)
      15.6.2 Reliable Ordered Multicast            328  (1)
    15.7 Open Groups                               329  (3)
      15.7.1 View-Synchronous Group                331  (1)
      Communication
    15.8 Overview Of Transis                       332  (2)
    15.9 Concluding Remarks                        334  (1)
    15.10 Bibliographic Notes                      334  (1)
    Exercises                                      335  (4)
  Chapter 16 Replicated Data Management            339  (26)
    16.1 Introduction                              339  (1)
      16.1.1 Reliability Versus Availability       339  (1)
    16.2 Architecture Of Replicated Data           340  (4)
    Management
      16.2.1 Passive Versus Active Replication     341  (2)
      16.2.2 Fault-Tolerant State Machines         343  (1)
    16.3 Data-Centric Consistency Models           344  (5)
      16.3.1 Strict Consistency                    345  (1)
      16.3.2 Linearizability                       346  (1)
      16.3.3 Sequential Consistency                346  (1)
      16.3.4 Causal Consistency                    347  (1)
      16.3.5 FIFO Consistency                      348  (1)
    16.4 Client-Centric Consistency Protocols      349  (2)
      16.4.1 Eventual Consistency                  349  (1)
      16.4.2 Consistency Models For Mobile         350  (6)
      Clients
        16.4.2.1 Read-After-Read Consistency       350  (1)
        16.4.2.2 Write-After-Write Consistency     350  (1)
        16.4.2.3 Read-After-Write Consistency      351  (1)
        16.4.2.4 Write-After-Read Consistency      351  (1)
    16.5 Implementation Of Data-Centric            351  (1)
    Consistency Models
    16.6 Quorum-Based Protocols                    352  (2)
    16.7 Replica Placement                         354  (1)
    16.8 Brewer's Cap Theorem                      355  (1)
    16.9 Case Studies                              356  (5)
      16.9.1 Replication Management In Coda        356  (1)
      16.9.2 Replication Management In Bayou       357  (2)
      16.9.3 Amazon Dynamo                         359  (2)
    16.10 Concluding Remarks                       361  (1)
    16.11 Bibliographic Notes                      361  (1)
    Exercises                                      362  (3)
  Chapter 17 Self-Stabilizing Systems              365  (26)
    17.1 Introduction                              365  (2)
    17.2 Theoretical Foundations                   367  (1)
    17.3 Stabilizing Mutual Exclusion              368  (5)
      17.3.1 Mutual Exclusion On A                 368  (2)
      Unidirectional Ring
      17.3.2 Mutual Exclusion On A                 370  (3)
      Bidirectional Array
    17.4 Stabilizing Graph Coloring                373  (2)
    17.5 Stabilizing Spanning Tree Protocol        375  (2)
    17.6 Stabilizing Maximal Matching              377  (2)
    17.7 Distributed Reset                         379  (3)
    17.8 Stabilizing Clock Phase Synchronization   382  (1)
    17.9 Concluding Remarks                        383  (1)
    17.10 Bibliographic Notes                      384  (1)
    Exercises                                      385  (6)
Section V Real-World Issues
  Chapter 18 Distributed Discrete-Event            391  (12)
  Simulation
    18.1 Introduction                              391  (2)
      18.1.1 Event-Driven Simulation               391  (2)
    18.2 Distributed Simulation                    393  (3)
      18.2.1 Challenges                            393  (3)
      18.2.2 Correctness Issues                    396  (1)
    18.3 Conservative Simulation                   396  (1)
    18.4 Optimistic Simulation And Time Warp       397  (2)
      18.4.1 Global Virtual Time                   398  (1)
    18.5 Concluding Remarks                        399  (1)
    18.6 Bibliographic Notes                       399  (1)
    Exercises                                      400  (3)
  Chapter 19 Security In Distributed Systems       403  (32)
    19.1 Introduction                              403  (1)
    19.2 Security Mechanisms                       404  (1)
    19.3 Common Security Attacks                   404  (2)
      19.3.1 Eavesdropping                         404  (1)
      19.3.2 Denial Of Service                     405  (1)
      19.3.3 Data Tampering                        405  (1)
      19.3.4 Masquerading                          405  (1)
      19.3.5 Man In The Middle                     405  (1)
      19.3.6 Malicious Software                    405  (3)
        19.3.6.1 Virus                             406  (1)
        19.3.6.2 Worms                             406  (1)
        19.3.6.3 Spyware                           406  (1)
    19.4 Encryption                                406  (2)
    19.5 Secret Key Cryptosystem                   408  (6)
      19.5.1 Confusion And Diffusion               408  (1)
      19.5.2 DES                                   409  (2)
      19.5.3 3DES                                  411  (1)
      19.5.4 AES                                   411  (1)
      19.5.5 One-Time Pad                          411  (1)
      19.5.6 Stream Ciphers                        412  (1)
      19.5.7 Steganography                         413  (1)
    19.6 Public Key Cryptosystems                  414  (4)
      19.6.1 Rivest祐hamir輸dleman Cryptosystem    414  (3)
      19.6.2 ElGamal Cryptosystem                  417  (1)
    19.7 Digital Signatures                        418  (1)
      19.7.1 Signatures In Secret-Key              418  (1)
      Cryptosystems
      19.7.2 Signatures In Public-Key              418  (1)
      Cryptosystems
    19.8 Hashing Algorithms                        419  (1)
      19.8.1 Birthday Attack                       419  (1)
    19.9 Elliptic Curve Cryptography               420  (1)
    19.10 Authentication Server                    421  (2)
      19.10.1 Authentication Service For           422  (1)
      Secret-Key Cryptosystems
      19.10.2 Authentication Server For            422  (1)
      Public-Key Systems
    19.11 Digital Certificates                     423  (1)
    19.12 Case Studies                             424  (4)
      19.12.1 Kerberos                             424  (1)
      19.12.2 Pretty Good Privacy                  425  (1)
      19.12.3 Secure Socket Layer                  426  (2)
    19.13 Virtual Private Networks And Firewalls   428  (1)
      19.13.1 Virtual Private Network              428  (1)
      19.13.2 Firewall                             429  (1)
    19.14 Sharing A Secret                         429  (1)
    19.15 Concluding Remarks                       430  (1)
    19.16 Bibliographic Notes                      430  (1)
    Exercises                                      431  (4)
  Chapter 20 Sensor Networks                       435  (30)
    20.1 Vision                                    435  (1)
    20.2 Architecture Of Sensor Nodes              436  (6)
      20.2.1 Mica Mote                             436  (1)
      20.2.2 ZigBee-Enabled Sensor Nodes           437  (2)
      20.2.3 TinyOSｮ Operating System              439  (3)
    20.3 Challenges In Wireless Sensor Networks    442  (3)
      20.3.1 Energy Conservation                   442  (1)
      20.3.2 Fault Tolerance                       443  (1)
      20.3.3 Routing                               444  (1)
      20.3.4 Time Synchronization                  444  (1)
      20.3.5 Location Management                   444  (1)
      20.3.6 Middleware Design                     444  (1)
      20.3.7 Security                              445  (1)
    20.4 Routing Algorithms                        445  (3)
      20.4.1 Directed Diffusion                    445  (1)
      20.4.2 Cluster-Based Routing                 446  (2)
        20.4.2.1 LEACH                             446  (1)
        20.4.2.2 PEGASIS                           447  (1)
      20.4.3 Metadata-Based Routing: SPIN          448  (1)
    20.5 Time Synchronization Using Reference      448  (3)
    Broadcast
      20.5.1 Reference Broadcast                   449  (2)
    20.6 Localization Algorithms                   451  (1)
      20.6.1 RSSI-Based Ranging                    451  (1)
      20.6.2 Ranging Using Time Difference Of      451  (1)
      Arrival
      20.6.3 Anchor-Based Ranging                  451  (1)
    20.7 Security In Sensor Networks               452  (3)
      20.7.1 Spin For Data Security                453  (1)
        20.7.1.1 Overview Of SNEP                  453  (1)
        20.7.1.2 Overview Of μTESLA             454  (1)
      20.7.2 Attacks On Routing                    454  (1)
        20.7.2.1 Hello Flood                       455  (1)
    20.8 Applications                              455  (4)
      20.8.1 Health-Care Applications              455  (1)
      20.8.2 Environment Monitoring And Control    456  (1)
      20.8.3 Citizen Sensing                       456  (1)
      20.8.4 Pursuer-Evader Game                   456  (3)
    20.9 Concluding Remarks                        459  (1)
    20.10 Bibliographic Notes                      459  (1)
    Exercises                                      460  (5)
  Chapter 21 Social And Peer-To-Peer Networks      465  (36)
    21.1 Introduction To Social Networks           465  (2)
      21.1.1 Milgram's Experiment                  465  (2)
    21.2 Metrics Of Social Networks                467  (1)
      21.2.1 Clustering Coefficient                467  (1)
      21.2.2 Diameter                              468  (1)
    21.3 Modeling Social Networks                  468  (5)
      21.3.1 Erd?s-R駭yi Model                     468  (1)
      21.3.2 Small-World Model                     469  (1)
      21.3.3 Power-Law Graphs                      470  (3)
    21.4 Centrality Measures In Social Networks    473  (2)
      21.4.1 Degree Centrality                     473  (1)
      21.4.2 Closeness Centrality                  473  (1)
      21.4.3 Betweenness Centrality                474  (1)
    21.5 Community Detection                       475  (1)
      21.5.1 Girvan-Newman Algorithm               475  (1)
    21.6 Introduction To Peer-To-Peer Networks     476  (1)
    21.7 First-Generation P2P Systems              477  (2)
      21.7.1 Napster                               477  (1)
      21.7.2 Gnutella                              478  (1)
    21.8 Second-Generation P2P Systems             479  (8)
      21.8.1 KaZaA                                 481  (1)
      21.8.2 Chord                                 481  (3)
      21.8.3 Content-Addressable Network           484  (1)
      21.8.4 Pastry                                485  (2)
    21.9 Koorde And De Bruijn Graph                487  (1)
    21.10 Skip Graph                               488  (3)
    21.11 Replication Management                   491  (1)
    21.12 Bittorrent And Free Riding               492  (2)
    21.13 Censorship Resistance, Anonymity         494  (1)
    21.14 Concluding Remarks                       494  (1)
    21.15 Bibliographic Notes                      495  (1)
    Exercises                                      496  (5)
References,                                        501  (12)
Index,                                             513