Building
`Secure and Reliable
`Network Applications
`
`KennethP.Birman
`
`DepartmentofComputerScience
`
`CornellUniversity
`
`Ithaca,NewYork14853
`
`Cover image: line drawing of the golden gate bridge looking towards San Francisco?
`
`@ Copyright 1995, Kenneth P. Birman. All rights reserved. This document may not be copied, electronically or physically, in
`whole or in part, or otherwise disseminated without the author’s prior written permission.
`
`Zynga Ex. 1021, p. 1
`Zynga v. IGT
`IPR2022-00368
`
`

`

`TRADEMARKS CITED IN THE TEXT
`
`PREFACE AND ACKNOWLEDGEMENTS
`
`INTRODUCTION
`
`A USER’S GUIDE TO THIS BOOK
`
`PART I: BASIC DISTRIBUTED COMPUTING TECHNOLOGIES
`
`1. FUNDAMENTALS
`
`1.1 Introduction
`
`1.2 Components of a Reliable Distributed Computing System
`1.2.1 Communications Technology
`1.2.2 Basic transport and network services
`1.2.3 Reliable transport software and communication support
`1.2.4 “Middleware”: Software tools, utilities, and programming languages
`1.2.5 Distributed computing environments
`1.2.6 End-user applications
`
`1.3 Critical Dependencies
`
`1.4 Next Steps
`
`1.5 Additional Reading
`
`2. COMMUNICATION TECHNOLOGIES
`
`2.1 Types of Communication Devices
`
`2.2 Properties
`
`2.3 Ethernet
`
`2.4 FDDI
`
`2.5 B-ISDN and the Intelligent Network
`
`2.6 ATM
`
`2.7 Cluster and Parallel Architectures
`
`2.8 Next steps
`
`2.9 Additional Reading
`
`14
`
`15
`
`16
`
`26
`
`28
`
`29
`
`29
`
`32
`35
`36
`38
`38
`39
`40
`
`41
`
`42
`
`43
`
`44
`
`44
`
`45
`
`46
`
`48
`
`50
`
`53
`
`56
`
`57
`
`58
`
`Zynga Ex. 1021, p. 2
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`3. BASIC COMMUNICATION SERVICES
`
`3.1 Communications Standards
`
`3.2 Addressing
`
`3.3 Internet Protocols
`3.3.1 Internet Protocol: IP layer
`3.3.2 Transport Control Protocol: TCP
`3.3.3 User Datagram Protocol: UDP
`3.3.4 Internet Packet Multicast Protocol: IP Multicast
`
`3.4 Routing
`
`3.5 End-to-end Argument
`
`3.6 O/S Architecture Issues, Buffering, Fragmentation
`
`3.7 Xpress Transfer Protocol
`
`3.8 Next Steps
`
`3.9 Additional Reading
`
`4. RPC AND THE CLIENT-SERVER MODEL
`
`4.1 RPC Protocols and Concepts
`
`4.2 Writing an RPC-based Client or Server Program
`
`4.3 The RPC Binding Problem
`
`4.4 Marshalling and Data Types
`
`4.5 Associated Services
`4.5.1 Naming services
`4.5.2 Time services
`4.5.3 Security services
`4.5.4 Threads packages
`
`4.6 The RPC Protocol
`
`4.7 Using RPC in Reliable Distributed Systems
`
`4.8 Related Readings
`
`5. STREAMS
`
`5.1 Sliding Window Protocols
`5.1.1 Error Correction
`5.1.2 Flow Control
`5.1.3 Dynamic Adjustment of Window Size
`
`3
`
`59
`
`59
`
`59
`
`63
`64
`64
`64
`65
`
`66
`
`67
`
`68
`
`70
`
`71
`
`72
`
`73
`
`75
`
`77
`
`79
`
`81
`
`83
`83
`84
`85
`85
`
`89
`
`92
`
`95
`
`96
`
`96
`97
`98
`98
`
`3
`
`Zynga Ex. 1021, p. 3
`Zynga v. IGT
`IPR2022-00368
`
`

`

`4
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`5.1.4 Burst Transmission Concept
`
`5.2 Negative-Acknowledgement Only
`
`5.3 Reliability, Fault-tolerance, and Consistency in Streams
`
`5.4 RPC over a Stream
`
`5.5 Related Readings
`
`6. CORBA AND OBJECT-ORIENTED ENVIRONMENTS
`
`6.1 The ANSA Project
`
`6.2 Beyond ANSA to CORBA
`
`6.3 OLE-2 and Network OLE
`
`6.4 The CORBA Reference Model
`
`6.5 TINA
`
`6.6 IDL and ODL
`
`6.7 ORB
`
`6.8 Naming Service
`
`6.9 ENS
`
`6.10 Life Cycle Service
`
`6.11 Persistent Object Service
`
`6.12 Transaction Service
`
`6.13 Inter-Object Broker Protocol
`
`6.14 Future CORBA Services
`
`6.15 Properties of CORBA Solutions
`
`6.16 Related Readings
`
`7. CLIENT-SERVER COMPUTING
`
`7.1 Stateless and Stateful Client-Server Interactions
`
`7.2 Major Uses of the Client-Server Paradigm
`
`7.3 Distributed File Systems
`
`4
`
`99
`
`100
`
`100
`
`102
`
`102
`
`104
`
`104
`
`106
`
`107
`
`107
`
`114
`
`114
`
`116
`
`116
`
`117
`
`118
`
`118
`
`118
`
`118
`
`118
`
`119
`
`120
`
`121
`
`121
`
`121
`
`125
`
`Zynga Ex. 1021, p. 4
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`7.4 Stateful File Servers
`
`7.5 Distributed Database Systems
`
`7.6 Applying Transactions to File Servers
`
`7.7 Message Oriented Middleware
`
`7.8 Related Topics
`
`7.9 Related Readings
`
`8. OPERATING SYSTEM SUPPORT FOR HIGH PERFORMANCE
`COMMUNICATION
`
`8.1 Lightweight RPC
`
`8.2 Fbuf’s and the xKernel Project
`
`8.3 Active Messages
`
`8.4 Beyond Active Messages: U-Net
`
`8.5 Protocol Compilation Techniques
`
`8.6 Related Readings
`
`PART II: THE WORLD WIDE WEB
`
`9. THE WORLD WIDE WEB
`
`9.1 Related Readings
`
`10. THE MAJOR WEB TECHNOLOGIES
`
`10.1 Hyper-Text Markup Language (HTML)
`
`10.2 Virtual Reality Markup Language (VRML)
`
`10.3 Universal Resource Locators (URLs)
`
`10.4 Hyper-Text Transport Protocol (HTTP)
`
`10.5 Representations of Image Data
`
`10.6 Authorization and Privacy Issues
`
`10.7 Web Proxy Servers
`
`10.8 Java, HotJava, and Agent Based Browsers
`
`5
`
`129
`
`136
`
`141
`
`143
`
`143
`
`145
`
`146
`
`147
`
`149
`
`151
`
`153
`
`156
`
`157
`
`158
`
`159
`
`164
`
`165
`
`166
`
`166
`
`166
`
`167
`
`170
`
`171
`
`174
`
`175
`
`5
`
`Zynga Ex. 1021, p. 5
`Zynga v. IGT
`IPR2022-00368
`
`

`

`6
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`10.9 GUI Builders and Other Distributed CASE Tools
`
`10.10 Tacoma and the Agent Push Model
`
`10.11 Web Search Engines and Web Crawlers
`
`10.12 Important Web Servers
`
`10.13 Future Challenges
`
`10.14 Related Readings
`
`11. RELATED INTERNET TECHNOLOGIES
`
`11.1 File Transfer Tools
`
`11.2 Electronic Mail
`
`11.3 Network Bulletin Boards (newsgroups)
`
`11.4 Message Oriented MiddleWare Systems (MOMS)
`
`11.5 Message Bus Architectures
`
`11.6 Internet Firewalls and Gateways
`
`11.7 Related Readings
`
`PART III: RELIABLE DISTRIBUTED COMPUTING
`
`12. HOW AND WHY COMPUTER SYSTEMS FAIL
`
`12.1 Hardware Reliability and Trends
`
`12.2 Software Reliability and Trends
`
`12.3 Other Sources of Downtime
`
`12.4 Complexity
`
`12.5 Detecting failures
`
`12.6 Hostile Environments
`
`12.7 Related Readings
`
`13. GUARANTEEING BEHAVIOR IN DISTRIBUTED SYSTEMS
`
`13.1 Consistent Distributed Behavior
`
`13.2 Warning: Rough Road Ahead!
`
`6
`
`179
`
`179
`
`181
`
`182
`
`182
`
`184
`
`185
`
`185
`
`185
`
`186
`
`187
`
`189
`
`191
`
`192
`
`193
`
`194
`
`194
`
`194
`
`196
`
`196
`
`197
`
`198
`
`199
`
`200
`
`200
`
`201
`
`Zynga Ex. 1021, p. 6
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`13.3 Membership in a Distributed System
`
`13.4 Time in Distributed Systems
`
`13.5 Failure Models and Reliability Goals
`
`13.6 Reliable Computing in a Static Membership Model
`13.6.1 The Distributed Commit Problem
`13.6.1.1 Two-Phase Commit
`13.6.1.2 Three-Phase Commit
`13.6.2 Reading and Updating Replicated Data with Crash Failures
`
`13.7 Replicated Data with Non-Benign Failure Modes
`
`13.8 Reliability in Asynchronous Environments
`
`13.9 The Dynamic Group Membership Problem
`
`13.10 The Group Membership Problem
`13.10.1 Protocol used to track GMS Membership
`13.10.2 GMS Protocol to Handle Client Add and Join Events
`13.10.3 GMS Notifications With Bounded Delay
`13.10.4 Extending the GMS to Allow Partition and Merge Events
`
`13.11 Dynamic Process Groups and Group Communication
`13.11.1 Group Communication Primitives
`
`13.12 Delivery Ordering Options
`13.12.1.1 Non-Uniform Failure-Atomic Group Multicast
`13.12.1.2 Dynamically Uniform Failure-Atomic Group Multicast
`13.12.2 Dynamic Process Groups
`13.12.3 View-Synchronous Failure Atomicity
`13.12.4 Summary of GMS Properties
`13.12.5 Ordered Multicast
`13.12.5.1 Fifo Order
`13.12.5.2 Causal Order
`13.12.5.2.1 Causal ordering with logical timestamps
`13.12.5.2.2 Causal ordering with vector timestamps
`13.12.5.2.3 Timestamp compression
`13.12.5.2.4 Causal multicast and consistent cuts
`13.12.5.2.5 Exploiting Topological Knowledge
`13.12.5.3 Total Order
`
`13.13 Communication From Non-Members to a Group
`13.13.1 Scalability
`
`13.14 Communication from a Group to a Non-Member
`
`13.15 Summary
`
`13.16 Related Readings
`
`14. POINT-TO-POINT AND MULTIGROUP CONSIDERATIONS
`
`7
`
`202
`
`203
`
`208
`
`209
`210
`211
`218
`221
`
`223
`
`226
`
`231
`
`235
`239
`241
`242
`244
`
`245
`247
`
`249
`253
`255
`255
`257
`259
`260
`260
`261
`262
`263
`265
`266
`268
`269
`
`271
`273
`
`273
`
`273
`
`275
`
`276
`
`7
`
`Zynga Ex. 1021, p. 7
`Zynga v. IGT
`IPR2022-00368
`
`

`

`8
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`14.1 Causal Communication Outside of a Process Group
`
`14.2 Extending Causal Order to Multigroup Settings
`
`14.3 Extending Total Order to Multigroup Settings
`
`14.4 Causal and Total Ordering Domains
`
`14.5 Multicasts to Multiple Groups
`
`14.6 Multigroup View Management Protocols
`
`14.7 Related Reading
`
`15. THE VIRTUALLY SYNCHRONOUS EXECUTION MODEL
`
`15.1 Virtual Synchrony
`
`15.2 Extended Virtual Synchrony
`
`15.3 Virtually Synchronous Algorithms and Tools
`15.3.1 Replicated Data and Synchronization
`15.3.2 State transfer to a joining process
`15.3.3 Load-Balancing
`15.3.4 Primary-Backup Fault Tolerance
`15.3.5 Coordinator-Cohort Fault-Tolerance
`
`15.4 Related Readings
`
`16. CONSISTENCY IN DISTRIBUTED SYSTEMS
`
`16.1 Consistency in the Static and Dynamic Membership Models
`
`16.2 General remarks Concerning Causal and Total Ordering
`
`16.3 Summary and Conclusion
`
`16.4 Related Reading
`
`17. RETROFITTING RELIABILITY INTO COMPLEX SYSTEMS
`
`17.1 Wrappers and Toolkits
`17.1.1 Wrapper Technologies
`17.1.1.1 Wrapping at Object Interfaces
`17.1.1.2 Wrapping by Library Replacement
`17.1.1.3 Wrapping by Object Code Editing
`17.1.1.4 Wrapping With Interposition Agents and Buddy Processes
`17.1.1.5 Wrapping Communication Infrastructures: Virtual Private Networks
`17.1.1.6 Wrappers: Some Final Thoughts
`17.1.2 Introducing Robustness in Wrapped Applications
`17.1.3 Toolkit Technologies
`
`8
`
`276
`
`279
`
`280
`
`281
`
`282
`
`283
`
`283
`
`284
`
`284
`
`288
`
`292
`292
`296
`298
`299
`301
`
`302
`
`303
`
`303
`
`311
`
`314
`
`315
`
`316
`
`316
`318
`318
`318
`319
`320
`320
`321
`321
`323
`
`Zynga Ex. 1021, p. 8
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`17.1.4 Distributed Programming Languages
`
`17.2 Wrapping a Simple RPC server
`
`17.3 Wrapping a Web Server
`
`17.4 Hardening Other Aspects of the Web
`
`17.5 Unbreakable Stream Connections
`17.5.1 Reliability Options for Stream Communication
`17.5.2 An Unbreakable Stream That Mimics TCP
`17.5.3 Non-Determinism and Its Consequences
`17.5.4 Dealing With Arbitrary Non-Determinism
`17.5.5 Replicating the IP Address
`17.5.6 Maximizing Concurrency by Relaxing Multicast Ordering
`17.5.7 State Transfer Issues
`17.5.8 Discussion
`
`17.6 Building a Replicated TCP Protocol Using a Toolkit
`
`17.7 Reliable Distributed Shared Memory
`17.7.1 The shared memory wrapper abstraction
`17.7.2 Memory coherency options for distributed shared memory
`17.7.3 False sharing
`17.7.4 Demand paging and intelligent prefetching
`17.7.5 Fault-tolerance issues
`17.7.6 Security and protection considerations
`17.7.7 Summary and discussion
`
`17.8 Related Readings
`
`9
`
`325
`
`326
`
`327
`
`328
`
`332
`333
`335
`336
`337
`337
`338
`340
`340
`
`341
`
`342
`342
`344
`346
`346
`347
`347
`348
`
`348
`
`18. RELIABLE DISTRIBUTED COMPUTING SYSTEMS
`
`349
`
`18.1 Architectural Considerations in Reliable Systems
`
`18.2 Horus: A Flexible Group Communications System
`18.2.1 A layered process group architecture
`
`18.3 Protocol stacks
`
`18.4 Using Horus to Build a Robust Groupware Application
`
`18.5 Using Horus to Harden CORBA applications
`
`18.6 Basic Performance of Horus
`
`18.7 Masking the Overhead of Protocol Layering
`18.7.1 Reducing Header Overhead
`18.7.2 Eliminating Layered Protocol Processing Overhead
`18.7.3 Message Packing
`18.7.4 Performance of Horus with the Protocol Accelerator
`
`18.8 Scalability
`
`349
`
`351
`352
`
`355
`
`356
`
`359
`
`360
`
`362
`363
`364
`365
`365
`
`366
`
`9
`
`Zynga Ex. 1021, p. 9
`Zynga v. IGT
`IPR2022-00368
`
`

`

`10
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`18.9 Related Readings
`
`19. SECURITY OPTIONS FOR DISTRIBUTED SETTINGS
`
`19.1 Perimeter Defense Technologies
`
`19.2 Access Control Technologies
`
`19.3 Authentication Schemes and Kerberos
`19.3.1 RSA and DES
`19.3.2 Kerberos
`19.3.3 ONC security and NFS
`19.3.4 Fortezza
`
`19.4 Availability and Security
`
`19.5 Related Readings
`
`368
`
`370
`
`372
`
`374
`
`376
`376
`377
`380
`380
`
`382
`
`383
`
`20. CLOCK SYNCHRONIZATION AND SYNCHRONOUS SYSTEMS
`
`384
`
`20.1 Clock Synchronization
`
`20.2 Timed-asynchronous Protocols
`
`20.3 Adapting Virtual Synchrony for Real-Time Settings
`
`20.4 Related Readings
`
`21. TRANSACTIONAL SYSTEMS
`
`21.1 Implementation of a Transactional Storage System
`21.1.1 Write-ahead logging
`21.1.2 Persistent data seen “through” an updates list
`21.1.3 Non-distributed commit actions
`
`21.2 Distributed Transactions and Multi-Phase Commit
`
`21.3 Transactions on Replicated Data
`
`21.4 Nested Transactions
`21.4.1 Comments on the nested transaction model
`
`21.5 Weak Consistency Models
`21.5.1 Epsilon serializability
`21.5.2 Weak and strong consistency in partitioned database systems
`21.5.3 Transactions on multi-database systems
`21.5.4 Linearizability
`21.5.5 Transactions in Real-Time Systems
`
`21.6 Advanced Replication Techniques
`
`10
`
`384
`
`388
`
`395
`
`398
`
`399
`
`401
`401
`402
`403
`
`404
`
`404
`
`405
`407
`
`410
`410
`411
`412
`412
`413
`
`413
`
`Zynga Ex. 1021, p. 10
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`21.7 Related Readings
`
`22. PROBABILISTIC PROTOCOLS
`
`22.1 Probabilistic Protocols
`
`22.2 Other applications of gossip protocols
`
`22.3 Hayden’s pbcast primitive
`22.3.1 Unordered pbcast protocol
`22.3.2 Adding Total Ordering
`22.3.3 Probabilistic Reliability and the Bimodal Delivery Distribution
`22.3.4 An Extension to Pbcast
`22.3.5 Evaluation and Scalability
`22.3.5.1 Reliability
`22.3.5.2 Message cost and fanout.
`
`22.4 An Unscalable System Model
`
`22.5 Replicated Data using Pbcast
`22.5.1 Representation of replicated data
`22.5.2 Update protocol
`22.5.3 Read protocol
`22.5.4 Locking protocol
`
`22.6 Related Readings
`
`23. DISTRIBUTED SYSTEM MANAGEMENT
`
`23.1 A Relational System Model
`
`23.2 Instrumentation Issues: Sensors, Actuators
`
`23.3 Management Information Bases, SNMP and CMIP
`23.3.1 Sensors and events
`23.3.2 Actuators
`
`23.4 Reactive control in Distributed Settings
`
`23.5 Fault-tolerance by State Machine Replication
`
`23.6 Visualization of Distributed System States
`
`23.7 Correlated Events
`
`23.8 Information Warfare and Defensive Tactics
`
`23.9 Related Readings
`
`24. CLUSTER COMPUTER ARCHITECTURES
`
`11
`
`416
`
`417
`
`417
`
`419
`
`419
`420
`421
`422
`424
`424
`424
`424
`
`425
`
`425
`425
`425
`426
`426
`
`427
`
`428
`
`428
`
`430
`
`430
`431
`434
`
`435
`
`436
`
`436
`
`437
`
`437
`
`441
`
`442
`
`11
`
`Zynga Ex. 1021, p. 11
`Zynga v. IGT
`IPR2022-00368
`
`

`

`12
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`24.1 Inside a High Availability Cluster Product: The Stratus Radio
`
`24.2 Reliability Goals for Cluster Servers
`
`24.3 Comparison with Fault-Tolerant Hardware
`
`24.4 Protocol Optimizations
`
`24.5 Cluster API Goals and Implementation
`
`24.6 Related Readings
`
`25. REASONING ABOUT DISTRIBUTED SYSTEMS
`
`25.1 Dimensions of the Systems Validation Problem
`
`25.2 Process and Message-Oriented Models
`
`25.3 System Definition Languages
`
`25.4 High Level Languages and Logics
`
`26. OTHER DISTRIBUTED AND TRANSACTIONAL SYSTEMS
`
`26.1 Related Work in Distributed Computing
`26.1.1 Ameoba
`26.1.2 Chorus
`26.1.3 Delta-4
`26.1.4 Harp
`26.1.5 The Highly Available System (HAS)
`26.1.6 The Isis Toolkit
`26.1.7 Locus
`26.1.8 Sender-Based Logging and Manetho
`26.1.9 NavTech
`26.1.10 Phoenix
`26.1.11 Psync
`26.1.12 Relacs
`26.1.13 Rampart
`26.1.14 RMP
`26.1.15 StormCast
`26.1.16 Totem
`26.1.17 Transis
`26.1.18 The V System
`
`26.2 Systems That Implement Transactions
`26.2.1 Argus
`26.2.2 Arjuna
`26.2.3 Avalon
`26.2.4 Bayou
`26.2.5 Camelot and Encina
`
`12
`
`443
`
`445
`
`447
`
`448
`
`449
`
`450
`
`451
`
`451
`
`454
`
`457
`
`458
`
`461
`
`461
`461
`461
`462
`462
`463
`463
`464
`464
`465
`465
`465
`465
`466
`466
`466
`467
`468
`468
`
`469
`469
`470
`470
`470
`471
`
`Zynga Ex. 1021, p. 12
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`APPENDIX: PROBLEMS
`
`BIBLIOGRAPHY
`
`INDEX
`
`13
`
`472
`
`482
`
`505
`
`13
`
`Zynga Ex. 1021, p. 13
`Zynga v. IGT
`IPR2022-00368
`
`

`

`14
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`Trademarks Cited in the Text
`
`Unix is a Trademark of Santa Cruz Operations, Inc. CORBA (Common Object Request Broker
`Architecture) and OMG IDL are trademarks of the Object Management Group. ONC (Open Network
`Computing), NFS (Network File System), Solaris, Solaris MC, XDR (External Data Representation), and
`Java are trademarks of Sun Microsystems Inc. DCE is a trademark of the Open Software Foundation.
`XTP (Xpress Transfer Protocol) is a trademark of the XTP Forum. RADIO is a trademark of Stratus
`Computer Corporation.
`Isis Reliable Software Developer’s Kit, Isis Reliable Network File System, Isis
`Reliable Message Bus and Isis for Databases are trademarks of Isis Distributed Computing Systems, Inc.
`Orbix is a trademark of Iona Technologies Ltd. Orbix+Isis is a joint trademark of Iona and Isis
`Distributed Computing Systems, Inc. TIB (Teknekron Information Bus) and Subject Based Addressing
`are trademarks of Teknekron Software Systems (although we use “subject based addressing” in a more
`general sense in this text). Chorus is a trademark of Chorus Systemes Inc. Power Objects is a trademark
`of Oracle Corporation. Netscape is a trademark of Netscape Communications. OLE, Windows, Windows
`New Technology (Windows NT), and Windows 95 are trademarks of Microsoft Corporation. Lotus Notes
`is a trademark of Lotus Computing Corporation. Purify is a trademark of Highland Software, Inc.
`Proliant
`is a trademark of Compaq Computers Inc. VAXClusters, DEC MessageQ, and DECsafe
`Available Server Environment are trademarks of Digital Equipment Corporation. MQSeries and SP2 are
`trademarks of International Business Machines. Power Builder is a trademark of PowerSoft Corporation.
`Visual Basic is a trademark of Microsoft Corporation. Ethernet is a trademark of Xerox Corporation.
`
`Other products and services mentioned in this document are covered by the trademarks, service marks, or
`product names as designated by the companies that market those products. The author respectfully
`acknowledges any such that may not have been included above.
`
`14
`
`Zynga Ex. 1021, p. 14
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`15
`
`Preface and Acknowledgements
`
`This book is dedicated to my family, for their support and tolerance over the two-year period that it was
`written. The author is grateful to so many individuals, for their technical assistance with aspects of the
`development, that to try and list them one by one would certainly be to omit someone whose role was vital.
`Instead, let me just thank my colleagues at Cornell, Isis Distributed Systems, and worldwide for their help
`in this undertaking.
`I am also greatful to Paul Jones of Isis Distributed Systems and to Francois Barrault
`and Yves Eychenne of Stratus France and Isis Distributed Systems, France, for providing me with
`resources needed to work on this book during a sabbatical that I spent in Paris, in fall of 1995 and spring
`of 1996. Cindy Williams and Werner Vogels provided invaluable help in overcoming some of the details
`of working at such a distance from home.
`
`A number of reviewers provided feedback on early copies of this text, leading to (one hopes) considerable
`improvement in the presentation. Thanks are due to: Marjan Bace, David Bakken, Robert Cooper, Yves
`Eychenne, Dalia Malki, Raghu Hudli, David Page, David Plainfosse, Henrijk Paszt, John Warne and
`Werner Vogels. Raj Alur, Ian Service and Mark Wood provided help in clarifying some thorny technical
`questions, and are also gratefully acknowledged. Bruce Donald’s emails on idiosyncracies of the Web
`were extremely useful and had a surprisingly large impact on treatment of that topic in this text.
`
`Much of the work reported here was made possible by grants from the U.S. Department of Defense
`through its Advanced Research Projects Agency, DARPA (administered by the Office of Naval Research,
`Rome Laboratories, and NASA), and by infrastructure grants from the National Science Foundation.
`Grants from a number of corporations have also supported this work, including IBM Corporation, Isis
`Distributed Systems Inc., Siemens Corporate Research (Munich and New Jersey), and GTE Corporation. I
`wish to express my thanks to all of these agencies and corporations for their generosity.
`
`The techniques, approaches, and opinions expressed here are my own, and may not represent positions of
`the organizations and corporations that have supported this research.
`
`15
`
`Zynga Ex. 1021, p. 15
`Zynga v. IGT
`IPR2022-00368
`
`

`

`16
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`Introduction
`
`Despite nearly twenty years of progress towards ubiquitous computer connectivity, distributed computing
`systems have only recently emerged to play a serious role in industry and society. Perhaps this explains
`why so few distributed systems are reliable in the sense of tolerating failures automatically, guaranteeing
`properties such as performance or response time, or offering security against intentional threats. In many
`ways the engineering discipline of reliable distributed computing is still in its infancy.
`
`One might be tempted to reason tautologically, concluding that reliability must not be all that
`important in distributed systems (since otherwise, the pressure to make such systems reliable would long
`since have become overwhelming). Yet, it seems more likely that we have only recently begun to see the
`sorts of distributed computing systems in which reliability is critical. To the extent that existing mission-
`and even life-critical applications rely upon distributed software, the importance of reliability has perhaps
`been viewed as a narrow, domain-specific issue. On the other hand, as distributed software is placed into
`more and more critical applications, where safety or financial stability of large organizations depends
`upon the reliable operation of complex distributed applications, the inevitable result will be growing
`demand for technology developers to demonstrate the reliability of their distributed architectures and
`solutions. It is time to tackle distributed systems reliability in a serious way. To fail to do so today is to
`invite catastrophic computer-systems failures tomorrow.
`
`At the time of this writing, the sudden emergence of the “World Wide Web” (variously called the
`“Web”, the Information Superhighway, the Global Information Infrastructure, the Internet, or just the
`Net) is bringing this issue to the forefront. In many respects, the story of reliability in distributed systems
`is today tied to the future of the Web and the technology base that has been used to develop it.
`It is
`unlikely that any reader of this text is unfamiliar with the Web technology base, which has penetrated the
`computing industry in record time. A basic premise of our study is that the Web will be a driver for
`distributed computing, by creating a mass market around distributed computing. However, the term
`“Web” is often used loosely: much of the public sees the Web as a single entity that encompasses all the
`Internet technologies that exist today and that may be introduced in the future. Thus when we talk about
`the Web, we are inevitably faced with a much broader family of communications technologies.
`
`It is clear that some form of critical mass has recently been reached: distributed computing is
`emerging from its specialized and very limited niche to become a mass-market commodity, something
`that literally everyone depends upon, like a telephone or an automobile. The Web paradigm brings
`together the key attributes of this new market in a single package: easily understandable graphical
`displays, substantial content, unlimited information to draw upon, virtual worlds in which to wander and
`work. But the Web is also stimulating growth in other types of distributed applications.
`In some
`intangible way, the experience of the Web has caused modern society to suddenly notice the potential of
`distributed computing.
`
`Consider the implications of a societal transition whereby distributed computing has suddenly
`become a mass market commodity.
`In the past, a mass-market item was something everyone “owned”.
`With the Web, one suddenly sees a type of commodity that everyone “does”. For the most part, the
`computers and networks were already in place. What has changed is the way that people see them and use
`them. The paradigm of the Web is to connect useful things (and many useless things) to the network.
`Communication and connectivity suddenly seem to be mandatory: no company can possibily risk arriving
`
`16
`
`Zynga Ex. 1021, p. 16
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`17
`
`Increasingly, it makes sense to believe that if an application can be
`late for the Information Revolution.
`put on the network, someone is thinking about doing so, and soon.
`
`to the
`Whereas reliability and indeed distributed computing were slow to emerge prior
`introduction of the Web, reliable distributed computing will be necessary if networked solutions are to be
`used safely for many of the applications that are envisioned. In the past, researchers in the field wondered
`why the uptake of distributed computing had been so slow. Overnight, the question has become one of
`understanding how the types of computing systems that run on the Internet and the Web, or that will be
`accessed through it, can be made reliable enough for emerging critical uses.
`
`If Web-like interfaces present medical status information and records to a doctor in a hospital, or
`are used to control a power plant from a remote console, or to guide the decision making of major
`corporations, reliability of those interfaces and applications will be absolutely critical to the users. Some
`may have life-or-death implications: if that physician bases a split-second decision on invalid data, the
`patient might die. Others may be critical to the efficient function of the organization that uses them: if a
`bank mismanages risk because of an inaccurate picture of how its investments are allocated, the bank
`could incur huge losses or even fail. In still other settings, reliability may emerge as a key determinant in
`the marketplace: the more reliable product, at a comparable price, may simply displace the less reliable
`one. Reliable distributed computing suddenly has broad relevance.
`
`•
`
`Throughout what follows, the term “distributed computing” is used to describe a type of computer
`system that differs from what could be called a “network computing” system. The distinction illuminates
`the basic issues with which we will be concerned.
`
`As we use the term here, a computer network is a communication technology supporting the
`exchange of messages among computer programs executing on computational nodes. Computer networks
`are data movers, providing capabilities for sending data from one location to another, dealing with
`mobility and with changing topology, and automating the division of available bandwidth among
`contending users. Computer networks have evolved over a twenty year period, and during the mid 1990’s
`network connectivity between computer systems became pervasive. Network bandwidth has also increased
`enormously, rising from hundreds of bytes per second in the early 1980’s to millions per second in the
`mid 1990’s, with gigabit rates anticipated in the late 1990’s and beyond.
`
`Network functionality evolved steadily during this period. Early use of networks was entirely for
`file transfer, remote login and electronic mail or news. Over time, however, the expectations of users and
`the tools available have changed. The network user in 1996 is likely to be familiar with interactive
`network browsing tools such as Netscape’s browsing tool, which permits the user to wander within a huge
`and interconnected network of multimedia information and documents. Tools such as these permit the
`user to conceive of a computer workstation as a window into an immense world of information, accessible
`using a great variety of search tools, easy to display and print, and linked to other relevant material that
`may be physically stored halfway around the world and yet accessible at the click of a mouse.
`
`Meanwhile, new types of networking hardware have emerged. The first generation of networks
`was built using point-to-point connections; to present the illusion of full connectivity to users, the network
`included a software layer for routing and connection management. Over time, these initial technologies
`were largely replaced by high speed long distance lines that route through various hubs, coupled to local
`area networks implemented using multiple access technologies such as Ethernet and FDDI: hardware in
`which a single “wire” has a large number of computers attached to it, supporting the abstraction of a
`
`17
`
`Zynga Ex. 1021, p. 17
`Zynga v. IGT
`IPR2022-00368
`
`

`

`18
`
`Kenneth P. Birman - Building Secure and Reliable Network Applications
`
`shared message bus. At the time of this writing, a third generation of technologies is reaching the market,
`such as ATM hardware capable of supporting gigabit communication rates over virtual circuits, mobile
`connection technologies for the office that will allow computers to be moved without rewiring, and more
`ambitious mobile computing devices
`that exploit
`the nationwide cellular
`telephone grid for
`communications support.
`
`As recently as the early 1990’s, computer bandwidth over wide-area links was limited for most
`users. The average workstation had high speed access to a local network, and perhaps the local email
`system was connected to the Internet, but individual users (especially those working from PC’s) rarely had
`better than 1600 baud connections available for personal use of the Internet. This picture is changing
`rapidly today: more and more users have relatively high speed modem connections to an Internet service
`provider that offers megabyte-per-second connectivity to remote servers. With the emergence of ISDN
`services to the home,
`the last link of the chain will suddenly catch up with the rest.
`Individual
`connectivity has thus jumped from 1600 baud to perhaps 28,800 baud at the time of this writing, and may
`jump to 1 Mbaud or more in the not distant future. Moreover, this bandwidth has finally reached the PC
`community, which enormously outnumbers the workstation community.
`
`It has been suggested that technology revolutions are often spurred by discontinuous, as opposed
`to evolutionary, improvement in a key aspect of a technology. The bandwidth improvements we are now
`experiencing are so disproportionate with respect to other performance changes (memory sizes, processor
`speeds) as to fall squarely into the discontinuous end of the spectrum. The sudden connectivity available
`to PC users is similarly disproportionate to anything in prior experience. The Web is perhaps just the first
`of a new generation of communications-oriented technologies enabled by these sudden developments.
`
`In particular, the key enablers for the Web were precisely the availability of adequate long-
`distance communications bandwidth to sustain its programming model, coupled to the evolution of
`computing systems supporting high performance graphical displays and sophisticated local applications
`dedicated to the user. It is only recently that these pieces fell into place. Indeed,
`the Web emerged more
`or less as early as it could possibly have done so, considering the state of the art in the various
`technologies on which it depends. Thus while the Web is clearly a breakthrough (cid:190)
`the “killer
`application” of the Internet (cid:190)
`it is also the most visible manifestation of a variety of underlying
`developments that are also enabling other kinds of distributed applications. It makes sense to see the Web
`as the tip of an iceberg: a paradigm for something much broader that is sweeping the entire computing
`community.
`
`•
`
`As the trend towards better communication performance and lower latencies continues, it is
`certain to fuel continued growth in distributed computing.
`In contrast to a computer network, a
`distributed computing system refers to computing systems and applications that cooperate to coordinate
`actions at multiple locations in a network. Rather than adopting a perspective in which conventional (non-
`distributed) application programs access data remotely over a network, a distributed system includes
`multiple application programs that communicate over the network, but take actions at the multiple places
`where the application runs. Despite the widespread availability of networking since early 1980, distributed
`computing has only become common in the 1990’s. This lag reflects a fundamental issue: distributed
`computing turns out
`to be much harder than non-distributed or network computing applications,
`especially if reliability is a critical requirement.
`
`Our treatment explores the technology of distributed computing with a particular bias: to
`understand why the emerging generation of critical Internet and Web technologies is likely to require very
`
`18
`
`Zynga Ex. 1021, p. 18
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Chapter 1: Fundamentals
`
`19
`
`high levels of reliability, and to explore the implications of this for distributed computing technologies. A
`key issue is to gain some insight into the factors that make it so hard to develop distributed computing
`systems that can be relied upon in critical settings, and and to understand can be done to simplify the task.
`In other disciplines like civil engineering or electrical engineeri