Distributed Systems - Theory and Applications

Preface xxi Acknowledgments xxvii Acronyms xxix 1 Introduction 1 1.1 Advantages of distributed systems : : : : : : : : : : : : : : : : : 2 1.2 De ning Distributed Systems : : : : : : : : : : : : : : : : : : : : 4 1.3 Challenges of a Distributed System : : : : : : : : : : : : : : : : 7 1.4 Goals of distributed system : : : : : : : : : : : : : : : : : : : : : 9 1.4.1 Single System View : : : : : : : : : : : : : : : : : : : 10 1.4.2 Hiding Distributions : : : : : : : : : : : : : : : : : : : 10 1.4.3 Degrees and Distribution of Hiding : : : : : : : : : : 13 1.4.4 Interoperability : : : : : : : : : : : : : : : : : : : : : : 14 1.4.5 Dynamic recon guration : : : : : : : : : : : : : : : : 15 1.5 Architectural Organization : : : : : : : : : : : : : : : : : : : : : : 16 1.6 Organization of the book : : : : : : : : : : : : : : : : : : : : : : 17 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 2 The Internet 21 2.1 Origin and Organization : : : : : : : : : : : : : : : : : : : : : : : 22 2.1.1 ISPs and the Topology of the Internet : : : : : : : : 24 v 2.2 Addressing the Nodes : : : : : : : : : : : : : : : : : : : : : : : : 25 2.3 Network Connection Protocol : : : : : : : : : : : : : : : : : : : : 29 2.3.1 IP Protocol : : : : : : : : : : : : : : : : : : : : : : : : 31 2.3.2 Transmission Control Protocol : : : : : : : : : : : : : 32 2.3.3 User Datagram Protocol : : : : : : : : : : : : : : : : 33 2.4 Dynamic Host Control Protocol : : : : : : : : : : : : : : : : : : : 33 2.5 Domain Name Service : : : : : : : : : : : : : : : : : : : : : : : : 35 2.5.1 Reverse DNS Lookup : : : : : : : : : : : : : : : : : : 39 2.5.2 Client Server Architecture : : : : : : : : : : : : : : : 44 2.6 Content Distribution Network : : : : : : : : : : : : : : : : : : : : 47 2.7 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 50 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 50 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 51 3 Process to Process Communication 53 3.1 Communication Types and Interfaces : : : : : : : : : : : : : : : 54 3.1.1 Sequential type : : : : : : : : : : : : : : : : : : : : : 55 3.1.2 Declarative type : : : : : : : : : : : : : : : : : : : : : 57 3.1.3 Shared states : : : : : : : : : : : : : : : : : : : : : : : 58 3.1.4 Message passing : : : : : : : : : : : : : : : : : : : : : 59 3.1.5 Communication interfaces : : : : : : : : : : : : : : : 59 3.2 Socket programming : : : : : : : : : : : : : : : : : : : : : : : : : 61 3.2.1 Socket data structures : : : : : : : : : : : : : : : : : 62 3.2.2 Socket calls : : : : : : : : : : : : : : : : : : : : : : : : 64 vi 3.3 Remote Procedure Call : : : : : : : : : : : : : : : : : : : : : : : : 70 3.3.1 XML RPC : : : : : : : : : : : : : : : : : : : : : : : : 77 3.4 Remote Method Invocation : : : : : : : : : : : : : : : : : : : : : 80 3.5 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89 4 Microservices, Conterization and MPI 93 4.1 Microservice Architecture : : : : : : : : : : : : : : : : : : : : : : 94 4.2 REST Requests and APIs : : : : : : : : : : : : : : : : : : : : : : 97 4.2.1 Weather Data Using REST API : : : : : : : : : : : : 99 4.3 Cross Platform Applications : : : : : : : : : : : : : : : : : : : : : 101 4.4 Message Passing Interface : : : : : : : : : : : : : : : : : : : : : : 114 4.4.1 Process Communication Models : : : : : : : : : : : : 115 4.4.2 Programming with MPI : : : : : : : : : : : : : : : : : 119 4.5 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 126 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 128 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 129 5 Clock Synchronization and Event Ordering 133 5.1 The Notion of Clock Time : : : : : : : : : : : : : : : : : : : : : : 134 5.2 External Clock Based Mechanisms : : : : : : : : : : : : : : : : : 136 5.2.1 Cristian's Algorithm : : : : : : : : : : : : : : : : : : : 137 5.2.2 Berkeley Clock Protocol : : : : : : : : : : : : : : : : 138 vii 5.2.3 Network Time Protocol : : : : : : : : : : : : : : : : : 139 5.3 Events and Temporal Ordering : : : : : : : : : : : : : : : : : : : 143 5.3.1 Causal Dependency : : : : : : : : : : : : : : : : : : : 145 5.4 De nition of logical clock : : : : : : : : : : : : : : : : : : : : : : 146 5.5 Causal Ordering of Messages : : : : : : : : : : : : : : : : : : : : 155 5.6 Multicast Message Ordering : : : : : : : : : : : : : : : : : : : : : 157 5.6.1 Implementing FIFO multicast : : : : : : : : : : : : : 162 5.6.2 Implementing Causal Ordering : : : : : : : : : : : : : 164 5.6.3 Implementing Total Ordering : : : : : : : : : : : : : 166 5.6.4 Reliable multicast : : : : : : : : : : : : : : : : : : : : 167 5.7 Interval events : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 169 5.7.1 Conceptual neighborhood : : : : : : : : : : : : : : : : 172 5.7.2 Spatial Events : : : : : : : : : : : : : : : : : : : : : : 174 5.8 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 176 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 178 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 181 6 Global States and Termination Detection 185 6.1 Cuts and Global States : : : : : : : : : : : : : : : : : : : : : : : : 186 6.1.1 Global states : : : : : : : : : : : : : : : : : : : : : : : 192 6.1.2 Recording of global states : : : : : : : : : : : : : : : 196 6.1.3 Problem in recording global state : : : : : : : : : : : 201 6.2 Liveness and Safety : : : : : : : : : : : : : : : : : : : : : : : : : : 204 6.3 Termination Detection : : : : : : : : : : : : : : : : : : : : : : : : 209 viii 6.3.1 Snapshot Based Termination Detection : : : : : : : 210 6.3.2 Ring Method : : : : : : : : : : : : : : : : : : : : : : : 213 6.3.3 Tree method : : : : : : : : : : : : : : : : : : : : : : : 217 6.3.4 Weight Throwing Method : : : : : : : : : : : : : : : 221 6.4 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 225 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 225 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 228 7 Leader Election 231 7.1 Impossibility Result : : : : : : : : : : : : : : : : : : : : : : : : : : 232 7.2 Bully Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : 235 7.3 Ring based algorithms : : : : : : : : : : : : : : : : : : : : : : : : 236 7.3.1 Circulate IDs all the way : : : : : : : : : : : : : : : : 237 7.3.2 As far as an ID can go : : : : : : : : : : : : : : : : : 240 7.4 Hirschberg and Sinclair algorithm : : : : : : : : : : : : : : : : : : 241 7.5 Distributed Spanning Tree Algorithm : : : : : : : : : : : : : : : 245 7.5.1 Single Initiator Spanning Tree : : : : : : : : : : : : : 246 7.5.2 Multiple Initiators Spanning Tree : : : : : : : : : : : 251 7.5.3 Minimum Spanning Tree : : : : : : : : : : : : : : : : 259 7.6 Leader election in trees : : : : : : : : : : : : : : : : : : : : : : : 260 7.6.1 Overview of the algorithm : : : : : : : : : : : : : : : 260 7.6.2 Activation Stage : : : : : : : : : : : : : : : : : : : : : 261 7.6.3 Saturation Stage : : : : : : : : : : : : : : : : : : : : : 262 7.6.4 Resolution Stage : : : : : : : : : : : : : : : : : : : : : 264 ix 7.6.5 Resolution Stage : : : : : : : : : : : : : : : : : : : : : 264 7.6.6 Two Nodes Enter SATURATED State : : : : : : : : 266 7.7 Leased Leader Election : : : : : : : : : : : : : : : : : : : : : : : : 269 7.8 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 272 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 273 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 276 8 Mutual Exclusion 281 8.1 System Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 282 8.2 Coordinator-based Solution : : : : : : : : : : : : : : : : : : : : : 285 8.3 Assertion-Based Solutions : : : : : : : : : : : : : : : : : : : : : : 286 8.3.1 Lamport's algorithm : : : : : : : : : : : : : : : : : : : 286 8.3.2 Improvement to Lamport's Algorithm : : : : : : : : : 290 8.3.3 Quorum based algorithms : : : : : : : : : : : : : : : : 291 8.4 Token based solutions : : : : : : : : : : : : : : : : : : : : : : : : 301 8.4.1 Suzuki and Kasami's algorithm : : : : : : : : : : : : 301 8.4.2 Singhal's Heuristically-Aided Algorithm : : : : : : : : 304 8.4.3 Raymond's tree-based algorithm : : : : : : : : : : : : 312 8.5 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 313 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 316 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 317 9 Agreements and Consensus 321 9.1 System Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 322 x 9.1.1 System Model : : : : : : : : : : : : : : : : : : : : : : 322 9.1.2 Failures in Distributed System : : : : : : : : : : : : : 324 9.1.3 Problem De nition : : : : : : : : : : : : : : : : : : : 325 9.1.4 Agreement Problem and its Equivalence : : : : : : : 327 9.2 Byzantine General Problem (BGP) : : : : : : : : : : : : : : : : : 330 9.2.1 BGP Solution Using Oral Messages : : : : : : : : : : 335 9.2.2 Phase-King Algorithm : : : : : : : : : : : : : : : : : : 340 9.3 Commit Protocols : : : : : : : : : : : : : : : : : : : : : : : : : : : 341 9.3.1 Two-Phase Commit Protocol : : : : : : : : : : : : : 343 9.3.2 Three-Phase Commit : : : : : : : : : : : : : : : : : : 349 9.4 Consensus : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 351 9.4.1 Consensus in Synchronous Systems : : : : : : : : : : 351 9.4.2 Consensus in Asynchronous Systems : : : : : : : : : 354 9.4.3 Paxos Algorithm : : : : : : : : : : : : : : : : : : : : : 354 9.4.4 Raft Algorithm : : : : : : : : : : : : : : : : : : : : : : 358 9.4.5 Leader Election : : : : : : : : : : : : : : : : : : : : : 362 9.5 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 364 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 365 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 367 10 Gossip Protocols 373 10.1 Direct Mail : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 374 10.2 Generic Gossip Protocol : : : : : : : : : : : : : : : : : : : : : : : 377 10.3 Anti Entropy : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 379 xi 10.3.1 Push-Based Anti-Entropy : : : : : : : : : : : : : : : : 379 10.3.2 Pull-Based Anti-Entropy : : : : : : : : : : : : : : : : 381 10.3.3 Hybrid Anti-Entropy : : : : : : : : : : : : : : : : : : : 383 10.3.4 Control and Propagation in Anti-Entropy : : : : : : 384 10.4 Rumor Mongering Gossip : : : : : : : : : : : : : : : : : : : : : : 386 10.4.1 Analysis of Rumor Mongering : : : : : : : : : : : : : 389 10.4.2 Fault Tolerance : : : : : : : : : : : : : : : : : : : : : 392 10.5 Implementation Issues : : : : : : : : : : : : : : : : : : : : : : : : 393 10.5.1 Network Related Issues : : : : : : : : : : : : : : : : : 394 10.6 Applications of Gossip : : : : : : : : : : : : : : : : : : : : : : : : 395 10.6.1 Peer Sampling : : : : : : : : : : : : : : : : : : : : : : 395 10.6.2 Failure Detectors : : : : : : : : : : : : : : : : : : : : : 399 10.6.3 Distributed Social Networking : : : : : : : : : : : : : 402 10.7 Gossip in IoT Communication : : : : : : : : : : : : : : : : : : : : 404 10.7.1 Context-aware Gossip : : : : : : : : : : : : : : : : : : 405 10.7.2 Flow-aware Gossip : : : : : : : : : : : : : : : : : : : : 406 10.8 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 413 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 413 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 417 11 Message Di usion Using Publish and Subscribe 421 11.1 Publish and Subscribe Paradigm : : : : : : : : : : : : : : : : : : 422 11.1.1 Broker Network : : : : : : : : : : : : : : : : : : : : : 424 11.2 Filters and Noti cations : : : : : : : : : : : : : : : : : : : : : : : 426 xii 11.2.1 Subscription and Advertisement : : : : : : : : : : : : 428 11.2.2 Covering Relation : : : : : : : : : : : : : : : : : : : : 429 11.2.3 Merging Filters : : : : : : : : : : : : : : : : : : : : : : 432 11.2.4 Algorithms : : : : : : : : : : : : : : : : : : : : : : : : 434 11.3 Noti cation Service : : : : : : : : : : : : : : : : : : : : : : : : : : 438 11.3.1 Siena : : : : : : : : : : : : : : : : : : : : : : : : : : : 439 11.3.2 Rebeca : : : : : : : : : : : : : : : : : : : : : : : : : : 440 11.3.3 Routing of Noti cation : : : : : : : : : : : : : : : : : 441 11.4 MQTT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 443 11.5 Advanced Message Queuing Protocol : : : : : : : : : : : : : : : 445 11.6 E ects of Technology on Performance : : : : : : : : : : : : : : : 448 11.7 Conclusions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 453 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 454 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 455 12 Peer-to-Peer Systems 461 12.1 De nition of P2P : : : : : : : : : : : : : : : : : : : : : : : : : : : 462 12.2 Representative P2P Models : : : : : : : : : : : : : : : : : : : : : 464 12.2.1 The Most Challenging Problem : : : : : : : : : : : : 466 12.3 Chord Overlay : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 468 12.4 Pastry : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 479 12.5 CAN : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 486 12.6 Kademlia : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 489 12.7 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 494 xiii Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 496 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 497 13 Distributed Shared Memory 501 13.1 Multicore and S-DSM : : : : : : : : : : : : : : : : : : : : : : : : 503 13.1.1 Coherency by Delegation to a Central Server : : : : 505 13.2 Manycore Systems and S-DSM : : : : : : : : : : : : : : : : : : : 507 13.3 Programming Abstractions : : : : : : : : : : : : : : : : : : : : : : 507 13.3.1 MapReduce : : : : : : : : : : : : : : : : : : : : : : : : 508 13.3.2 OpenMP : : : : : : : : : : : : : : : : : : : : : : : : : 510 13.3.3 Merging Publish and Subscribe with DSM : : : : : : 512 13.4 Memory Consistency Models : : : : : : : : : : : : : : : : : : : : 516 13.4.1 Sequential consistency : : : : : : : : : : : : : : : : : 519 13.4.2 Linearizability or Atomic consistency : : : : : : : : : 522 13.4.3 Relaxed Consistency Models : : : : : : : : : : : : : : 523 13.4.4 Comparison of Memory Models : : : : : : : : : : : : 531 13.5 DSM Access Algorithms : : : : : : : : : : : : : : : : : : : : : : : 532 13.5.1 Central Sever Algorithm : : : : : : : : : : : : : : : : 532 13.5.2 Migration Algorithm : : : : : : : : : : : : : : : : : : : 535 13.5.3 Read Replication Algorithm : : : : : : : : : : : : : : 537 13.5.4 Full Replication Algorithm : : : : : : : : : : : : : : : 538 13.6 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 540 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 541 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 545 xiv 14 Distributed Data Management 551 14.1 Distributed Storage Systems : : : : : : : : : : : : : : : : : : : : 552 14.1.1 RAID : : : : : : : : : : : : : : : : : : : : : : : : : : : 553 14.1.2 Storage Area Networks : : : : : : : : : : : : : : : : : 553 14.1.3 Cloud Storage : : : : : : : : : : : : : : : : : : : : : : 554 14.2 Distributed File Systems : : : : : : : : : : : : : : : : : : : : : : : 556 14.3 Distributed Index : : : : : : : : : : : : : : : : : : : : : : : : : : : 559 14.4 NoSQL Databases : : : : : : : : : : : : : : : : : : : : : : : : : : 560 14.4.1 Key-Value and Document databases : : : : : : : : : 561 MapReduce algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : 563 14.4.2 Wide Column databases : : : : : : : : : : : : : : : : 565 14.4.3 Graph databases : : : : : : : : : : : : : : : : : : : : : 567 Pregel Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 569 14.5 Distributed Data Analytics : : : : : : : : : : : : : : : : : : : : : : 572 14.5.1 Distributed Clustering Algorithms : : : : : : : : : : : 574 Distributed K-Means Clustering Algorithm : : : : : : : : : : : : : : : : 576 14.5.2 Stream Clustering : : : : : : : : : : : : : : : : : : : : 579 BIRCH Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 580 14.6 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 583 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 583 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 585 15 Distributed Knowledge Management 589 15.1 Distributed Knowledge : : : : : : : : : : : : : : : : : : : : : : : : 590 xv 15.2 Distributed Knowledge Representation : : : : : : : : : : : : : : : 592 15.2.1 Resource Description Framework (RDF) : : : : : : : 593 15.2.2 Web Ontology Language (OWL) : : : : : : : : : : : 600 15.3 Linked Data : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 601 15.3.1 Friend of a Friend : : : : : : : : : : : : : : : : : : : : 602 15.3.2 DBpedia : : : : : : : : : : : : : : : : : : : : : : : : : 603 15.4 Querying Distributed Knowledge : : : : : : : : : : : : : : : : : : 605 15.4.1 SPARQL Query Language : : : : : : : : : : : : : : : 606 15.4.2 SPARQL Query Semantics : : : : : : : : : : : : : : : 607 15.4.3 SPARQL Query Processing : : : : : : : : : : : : : : : 610 15.4.4 Distributed SPARQL Query Processing : : : : : : : : 612 15.4.5 Federated and Peer-to-Peer SPARQL query processing 615 15.5 Data Integration in Distributed Sensor Networks : : : : : : : : : 622 15.5.1 Semantic Data Integration : : : : : : : : : : : : : : : 624 15.5.2 Data Integration in Constrained Systems : : : : : : : 626 15.6 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 631 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 632 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 634 16 Distributed Intelligence 639 16.1 Agents and Multi-Agent Systems : : : : : : : : : : : : : : : : : : 640 16.1.1 Agent Embodiment : : : : : : : : : : : : : : : : : : : 643 16.1.2 Mobile Agents : : : : : : : : : : : : : : : : : : : : : : 644 16.1.3 Multi-agent Systems : : : : : : : : : : : : : : : : : : 645 xvi 16.2 Communication in Agent based Systems : : : : : : : : : : : : : 647 16.2.1 Agent Communication Protocols : : : : : : : : : : : 648 16.2.2 Interaction Protocols : : : : : : : : : : : : : : : : : : 650 Request Interaction Protocol : : : : : : : : : : : : : : : : : : : : : : : 651 16.3 Agent Middleware : : : : : : : : : : : : : : : : : : : : : : : : : : : 652 16.3.1 FIPA Reference model : : : : : : : : : : : : : : : : : 652 16.3.2 FIPA Compliant Middleware : : : : : : : : : : : : : : 654 JADE: Java Agent Development Environment : : : : : : : : : : : : : 654 MobileC : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 655 16.3.3 Agent Migration : : : : : : : : : : : : : : : : : : : : : 655 16.4 Agent Coordination : : : : : : : : : : : : : : : : : : : : : : : : : : 658 16.4.1 Planning : : : : : : : : : : : : : : : : : : : : : : : : : 660 Distributed Planning Paradigms : : : : : : : : : : : : : : : : : : : : : : 661 Distributed Plan Representation and Execution : : : : : : : : : : : : : 663 16.4.2 Task Allocation : : : : : : : : : : : : : : : : : : : : : 665 Contract-Net Protocol : : : : : : : : : : : : : : : : : : : : : : : : : : : 666 Allocation of Multiple Tasks : : : : : : : : : : : : : : : : : : : : : : : : 668 16.4.3 Coordinating through the environment : : : : : : : : 669 16.4.4 Coordination without Communication : : : : : : : : 674 16.5 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 674 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 676 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 679 xvii 17 Distributed Ledger 681 17.1 Cryptographic Techniques : : : : : : : : : : : : : : : : : : : : : : 682 17.2 Distributed Ledger Systems : : : : : : : : : : : : : : : : : : : : : 685 17.2.1 Properties of Distributed Ledger Systems : : : : : : 688 17.2.2 A Framework for Distributed Ledger Systems : : : : 689 17.3 Blockchain : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 691 17.3.1 Distributed Consensus in Blockchain : : : : : : : : : 693 17.3.2 Forking : : : : : : : : : : : : : : : : : : : : : : : : : : 695 17.3.3 Distributed Asset Tracking : : : : : : : : : : : : : : : 697 17.4 Other Techniques for Distributed Consensus : : : : : : : : : : : 698 17.4.1 Byzantine Fault Tolerance and Proof of Work : : : : 699 17.4.2 Alternative Proofs : : : : : : : : : : : : : : : : : : : : 700 17.5 Non-linear Data-structures : : : : : : : : : : : : : : : : : : : : : : 701 17.5.1 Tangle : : : : : : : : : : : : : : : : : : : : : : : : : : : 702 17.5.2 Hashgraph : : : : : : : : : : : : : : : : : : : : : : : : 705 17.6 Scripts and Smart Contracts : : : : : : : : : : : : : : : : : : : : 711 17.7 Distributed Ledgers for Cyber-physical systems : : : : : : : : : : 716 17.7.1 Layered architecture : : : : : : : : : : : : : : : : : : : 717 17.7.2 Smart Contract in Cyber-physical Systems : : : : : : 720 17.8 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 721 Exercises : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 723 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 724 xviii 18 Case Study 729 18.1 Collaborative E-Learning Systems : : : : : : : : : : : : : : : : : : 731 18.2 P2P E-Learning System : : : : : : : : : : : : : : : : : : : : : : : 733 18.2.1 Web Conferencing vs. P2P-IPS : : : : : : : : : : : : 735 18.3 P2P Shared Whiteboard : : : : : : : : : : : : : : : : : : : : : : : 738 18.3.1 Repainting Shared Whiteboard : : : : : : : : : : : : : 739 18.3.2 Consistency of Board View at Peers : : : : : : : : : 739 18.4 P2P Live Streaming : : : : : : : : : : : : : : : : : : : : : : : : : 743 18.4.1 Peer Joining : : : : : : : : : : : : : : : : : : : : : : : 744 18.4.2 Peer Leaving : : : : : : : : : : : : : : : : : : : : : : : 748 18.4.3 Handling "Ask Doubt" : : : : : : : : : : : : : : : : : 749 18.5 P2P-IPS for Stored Contents : : : : : : : : : : : : : : : : : : : : 750 18.5.1 De Bruijn Graphs for DHT Implentation : : : : : : : 750 18.5.2 Node Information Structure : : : : : : : : : : : : : : 755 18.5.3 Leaving of Peers : : : : : : : : : : : : : : : : : : : : : 758 18.6 Searching, Sharing, and Indexing : : : : : : : : : : : : : : : : : : 760 18.6.1 Pre-processing of les : : : : : : : : : : : : : : : : : : 761 18.6.2 File Indexing : : : : : : : : : : : : : : : : : : : : : : : 761 18.6.3 File Searching : : : : : : : : : : : : : : : : : : : : : : 762 18.7 Annotations and Discussion Forum : : : : : : : : : : : : : : : : : 763 18.7.1 Annotation Format : : : : : : : : : : : : : : : : : : : 763 18.7.2 Storing Annotations : : : : : : : : : : : : : : : : : : : 764 18.7.3 Audio and Video Annotation : : : : : : : : : : : : : : 764 xix 18.7.4 PDF Annotation : : : : : : : : : : : : : : : : : : : : : 765 18.7.5 Posts, Comments and Announcements : : : : : : : : 765 18.7.6 Synchronization of Posts and Comments : : : : : : : 766 18.8 Simulation Results : : : : : : : : : : : : : : : : : : : : : : : : : : 768 18.8.1 Live Streaming and Shared Whiteboard : : : : : : : 769 18.8.2 De Bruijn Overlay : : : : : : : : : : : : : : : : : : : : 771 18.9 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 774 Bibliography : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 775 Index 780