Distributed Systems E-Book

Ratan K. Ghosh

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 844

Veröffentlichungsjahr: 2023

Beschreibung

Distributed Systems Comprehensive textbook resource on distributed systems--integrates foundational topics with advanced topics of contemporary importance within the field Distributed Systems: Theory and Applications is organized around three layers of abstractions: networks, middleware tools, and application framework. It presents data consistency models suited for requirements of innovative distributed shared memory applications. The book also focuses on distributed processing of big data, representation of distributed knowledge and management of distributed intelligence via distributed agents. To aid in understanding how these concepts apply to real-world situations, the work presents a case study on building a P2P Integrated E-Learning system. Downloadable lecture slides are included to help professors and instructors convey key concepts to their students. Additional topics discussed in Distributed Systems: Theory and Applications include: * Network issues and high-level communication tools * Software tools for implementations of distributed middleware. * Data sharing across distributed components through publish and subscribe-based message diffusion, gossip protocol, P2P architecture and distributed shared memory. * Consensus, distributed coordination, and advanced middleware for building large distributed applications * Distributed data and knowledge management * Autonomy in distributed systems, multi-agent architecture * Trust in distributed systems, distributed ledger, Blockchain and related technologies. Researchers, industry professionals, and students in the fields of science, technology, and medicine will be able to use Distributed Systems: Theory and Applications as a comprehensive textbook resource for understanding distributed systems, the specifics behind the modern elements which relate to them, and their practical applications.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

About the Authors

Preface

Acknowledgments

Acronyms

1 Introduction

1.1 Advantages of Distributed Systems

1.2 Defining Distributed Systems

1.3 Challenges of a Distributed System

1.4 Goals of Distributed System

1.5 Architectural Organization

1.6 Organization of the Book

Bibliography

2 The Internet

2.1 Origin and Organization

2.2 Addressing the Nodes

2.3 Network Connection Protocol

2.4 Dynamic Host Control Protocol

2.5 Domain Name Service

2.6 Content Distribution Network

2.7 Conclusion

Exercises

Bibliography

3 Process to Process Communication

3.1 Communication Types and Interfaces

3.2 Socket Programming

3.3 Remote Procedure Call

3.4 Remote Method Invocation

3.5 Conclusion

Exercises

Additional Web Resources

Bibliography

4 Microservices, Containerization, and MPI

4.1 Microservice Architecture

4.2 REST Requests and APIs

4.3 Cross Platform Applications

4.4 Message Passing Interface

4.5 Conclusion

Exercises

Additional Internet Resources

Bibliography

5 Clock Synchronization and Event Ordering

5.1 The Notion of Clock Time

5.2 External Clock Based Mechanisms

5.3 Events and Temporal Ordering

5.4 Logical Clock

5.5 Causal Ordering of Messages

5.6 Multicast Message Ordering

5.7 Interval Events

5.8 Conclusion

Exercises

Bibliography

6 Global States and Termination Detection

6.1 Cuts and Global States

6.2 Liveness and Safety

6.3 Termination Detection

6.4 Conclusion

Exercises

Bibliography

7 Leader Election

7.1 Impossibility Result

7.2 Bully Algorithm

7.3 Ring‐Based Algorithms

7.4 Hirschberg and Sinclair Algorithm

7.5 Distributed Spanning Tree Algorithm

7.6 Leader Election in Trees

7.7 Leased Leader Election

7.8 Conclusion

Exercises

Bibliography

Note

8 Mutual Exclusion

8.1 System Model

8.2 Coordinator‐Based Solution

8.3 Assertion‐Based Solutions

8.4 Token‐Based Solutions

8.5 Conclusion

Exercises

Bibliography

9 Agreements and Consensus

9.1 System Model

9.2 Byzantine General Problem (BGP)

9.3 Commit Protocols

9.4 Consensus

9.5 Conclusion

Exercises

Bibliography

10 Gossip Protocols

10.1 Direct Mail

10.2 Generic Gossip Protocol

10.3 Anti‐entropy

10.4 Rumor‐mongering Gossip

10.5 Implementation Issues

10.6 Applications of Gossip

10.7 Gossip in IoT Communication

10.8 Conclusion

Exercises

Bibliography

11 Message Diffusion Using Publish and Subscribe

11.1 Publish and Subscribe Paradigm

11.2 Filters and Notifications

11.3 Notification Service

11.4 MQTT

11.5 Advanced Message Queuing Protocol

11.6 Effects of Technology on Performance

11.7 Conclusions

Exercises

Bibliography

12 Peer‐to‐Peer Systems

12.1 The Origin and the Definition of P2P

12.2 P2P Models

12.3 Chord Overlay

12.4 Pastry

12.5 CAN

12.6 Kademlia

12.7 Conclusion

Exercises

Bibliography

13 Distributed Shared Memory

13.1 Multicore and S‐DSM

13.2 Manycore Systems and S‐DSM

13.3 Programming Abstractions

13.4 Memory Consistency Models

13.5 DSM Access Algorithms

13.6 Conclusion

Exercises

Bibliography

14 Distributed Data Management

14.1 Distributed Storage Systems

14.2 Distributed File Systems

14.3 Distributed Index

14.4 NoSQL Databases

14.5 Distributed Data Analytics

14.6 Conclusion

Exercises

Bibliography

15 Distributed Knowledge Management

15.1 Distributed Knowledge

15.2 Distributed Knowledge Representation

15.3 Linked Data

15.4 Querying Distributed Knowledge

15.5 Data Integration in Distributed Sensor Networks

15.6 Conclusion

Exercises

Bibliography

16 Distributed Intelligence

16.1 Agents and Multi‐Agent Systems

16.2 Communication in Agent‐Based Systems

16.3 Agent Middleware

16.4 Agent Coordination

16.5 Conclusion

Exercises

Bibliography

17 Distributed Ledger

17.1 Cryptographic Techniques

17.2 Distributed Ledger Systems

17.3 Blockchain

17.4 Other Techniques for Distributed Consensus

17.5 Scripts and Smart Contracts

17.6 Distributed Ledgers for Cyber‐Physical Systems

17.7 Conclusion

Exercises

Bibliography

18 Case Study

18.1 Collaborative E‐Learning Systems

18.2 P2P E‐Learning System

18.3 P2P Shared Whiteboard

18.4 P2P Live Streaming

18.5 P2P‐IPS for Stored Contents

18.6 Searching, Sharing, and Indexing

18.7 Annotations and Discussion Forum

18.8 Simulation Results

18.9 Conclusion

Bibliography

Index

End User License Agreement

List of Tables

Chapter 5

Table 5.1 Summary of state recordings.

Table 5.2 Ordering of time vector

Chapter 6

Table 6.1 Inconsistent states related to bank transaction.

Table 6.2 Consistent global states related to bank transaction.

Chapter 7

Table 7.1 Summary of leader election algorithms

Chapter 8

Table 8.1 Initial values of state vectors for five sites.

Table 8.2 State vectors updates for processing 's request.

Table 8.3 State vectors update to process 's request.

Table 8.4 Summary of mutual exclusion algorithm.

Chapter 9

Table 9.1 Summary of problem variations.

Table 9.2 Commit versus Byzantine problem.

Chapter 10

Table 10.1 Comparison of gossip protocols for messaging in IoT networks.

Chapter 11

Table 11.1 Rules for filter merging.

Table 11.2 Comparison of protocols.

Chapter 12

Table 12.1 Some of the P2P application.

Table 12.2 Finger table.

Table 12.3 Comparison of structured peer‐to‐peer networks.

Chapter 14

Table 14.1 Monthly distribution of satellite launches.

Chapter 18

Table 18.1 Asymptotic degree‐diameter properties.

Table 18.2 Graph diameter for nodes.

Table 18.3 Average distance between pair of nodes for .

Table 18.4 Structure maintained at each node.

Table 18.5 Minimum throughput value.

Table 18.6 Lookup latency and success rate.

List of Illustrations

Preface

Figure 1 Topics and flow diagram of book's content.

Chapter 1

Figure 1.1 Illustrating distributed computing.

Figure 1.2 Dimension of scalability.

Chapter 2

Figure 2.1 Topological organization of the Internet.

Figure 2.2 Half duplex communication.

Figure 2.3 Communication via a mediator.

Figure 2.4 Setting up of the communication pipe between two routers.

Figure 2.5 Messaging sequence for DHCP.

Figure 2.6 Domain name hierarchy.

Figure 2.7 The hierarchy of a DNS tree segment.

Figure 2.8 Two‐tier distribution of programming responsibilities.

Chapter 3

Figure 3.1 Communication models in concurrent programming.

Figure 3.2 Pipeline computation using co‐routines.

Figure 3.3 Data flow graph for assignment statements.

Figure 3.4 Connecting two ends of a network application.

Figure 3.5 Important information in socket table.

Figure 3.6 Operation of TCP socket calls between a server and a client.

Figure 3.7 Run stack for handling function calls. (a) Run stack before call ...

Figure 3.8 Communication between client and server stubs in RPC.

Figure 3.9 RPC program compilation process flow.

Figure 3.10 Creating an object and its reference in Java.

Figure 3.11 RMI flow involving stub, skeleton, and registry.

Chapter 4

Figure 4.1 Monolithic architecture for cloud applications.

Figure 4.2 Microservice architecture for cloud applications.

Figure 4.3 Hypervisor.

Figure 4.4 Containerization.

Figure 4.5 Directory structure containerization of BibTeX app.

Figure 4.6 Classification of types of communication.

Figure 4.7 Persistent types of communication. (a) Asynchronous and (b) synch...

Figure 4.8 Transient asynchronous communication.

Figure 4.9 Types of synchronous transient communication. (a) Receipt‐based, ...

Figure 4.10 User's view of MPI.

Figure 4.11 MPI groups and processes.

Figure 4.12 Principle of message passing.

Figure 4.13 Non‐buffered blocking. (a) Sender arrives first, (b) both arrive...

Figure 4.14 Non‐blocking buffered communication. (a) Message is copied into ...

Chapter 5

Figure 5.1 Querying time server.

Figure 5.2 Time‐stamps of message pairs in NTP.

Figure 5.3 Each process gets partial views.

Figure 5.4 Concurrent events.

Figure 5.5 Illustrating Lamport's logical clock. (a) Clock not adjusted and ...

Figure 5.6 Total ordering using Lamport's clock.

Figure 5.7 Problem due to false total ordering.

Figure 5.8 Vector clock example.

Figure 5.9 Causal order violation.

Figure 5.10 Illustrating causal ordering.

Figure 5.11 FIFO ordering of multicast messages.

Figure 5.12 Causal ordering of multicast message.

Figure 5.13 Total ordering of multicast message.

Figure 5.14 Implementing FIFO ordering of multicast.

Figure 5.15 Implementing causal ordering of multicast messages.

Figure 5.16 Illustrating total ordering of messages.

Figure 5.17 Allen's temporal relations.

Figure 5.18 Semantics of Allen's relations.

Figure 5.19 Ambiguity in Allen's relations when extended to multi‐dimensiona...

Figure 5.20 Containment relations.

Chapter 6

Figure 6.1 Types of global states of a distributed system.

Figure 6.2 Rubber band transformation.

Figure 6.3 Global states with transitions.

Figure 6.4 Marker algorithm produces a consistent cut.

Figure 6.5 Concurrent execution of multiple instances of marker algorithm.

Figure 6.6 Permute events from actual execution sequence.

Figure 6.7 Token is circulated clock‐wise to detect termination. (a) Initiat...

Figure 6.8 Race condition between message and token circulation. (a) The bla...

Chapter 7

Figure 7.1 Execution of bully algorithm. (a) Process 4 initiates election bu...

Figure 7.2 Ring‐based leader election algorithm all the way up.

Figure 7.3 The number of messages. (a) Message circulation and (b) message c...

Figure 7.4 Phases of HS algorithm. (a) Phase 0 and (b) phase 1.

Figure 7.5 Illustrating worst‐case example for Hirschberg–Sinclair algorithm...

Figure 7.6 Counting message exchanges in single initiator algorithm.

Figure 7.7 Difficulty with multiple initiators in SPT algorithm. (a) and

Figure 7.8 Worst case scenario for the tree construction.

Figure 7.9 Saturated nodes.

Figure 7.10 Describes how client and master communicate in Chubby.

Chapter 8

Figure 8.1 Synchronization delay and performance. (a) Synchronization delay ...

Figure 8.2 Two examples illustrating execution of Lamport's algorithm.

Figure 8.3 Illustration of Ricart and Agrawala's mutex algorithm.

Figure 8.4 The finite projective plane of order 2.

Figure 8.5 Construction of suboptimal request set. (a) Grid method and (b) t...

Figure 8.6 Deadlock situation in Maekawa's algorithm.

Figure 8.7 Illustrating Suzuki and Kasami's algorithm. (a) is using

TOKEN

....

Figure 8.8 Initial state information.

Figure 8.9 Directed tree topology formed by

HOLDER

variables.

Chapter 9

Figure 9.1 Equivalence of agreement problems.

Figure 9.2 Derived execution sequences with loss of messages.

Figure 9.3 Three‐process impossibility result.

Figure 9.4 Four‐process BGP in the presence of a single fault.

Figure 9.5 Execution of OM(1) on four processes: (a) is nonfaulty and (b)

Figure 9.6 Case2 for OM(): source is faulty.

Figure 9.7 Difference in two ATM types. (a) Byzantine ATMs and (b) Commit AT...

Figure 9.8 Two‐phase commit protocol.

Figure 9.9 Time–space diagram of two‐phase commit protocol.

Figure 9.10 Transition states of two‐phase commit protocol. (a) States of pa...

Figure 9.11 States in execution of three‐phase commit. (a) States of partici...

Figure 9.12 Synchronous systems operate in rounds of time.

Figure 9.13 Raft server states and transitions.

Figure 9.14 Time is divided into terms of arbitrary lengths.

Chapter 10

Figure 10.1 DirectMail is equivalent to multiple unicasts.

Figure 10.2 Fully interconnected network for gossip.

Figure 10.3 Responsibility of spreading update gets halved in each round.

Figure 10.4 A two‐layer organization of the users.

Figure 10.5 A grid topology.

Chapter 11

Figure 11.1 Pub–sub messaging system event decoupling dimensions: (a) Space ...

Figure 11.2 Publish–subscribe model of message distribution.

Figure 11.3 Imposing multiple filters on the same attribute: (a) example‐1 a...

Figure 11.4 Illustrating the concept of filter covering.

Figure 11.5 Siena architecture.

Figure 11.6 Routing of notification in content‐broker system.

Figure 11.7 MQTT message brokering model.

Figure 11.8 AMQP message distribution via broker.

Figure 11.9 IoT messaging protocols in different messaging scenarios.

Chapter 12

Figure 12.1 The Napster model.

Figure 12.2 The Gnutella model.

Figure 12.3 The KaZaA model.

Figure 12.4 Mapping keys to circular address space.

Figure 12.5 Illustrating chord.

Figure 12.6 Example. (a) Finger table and (b) search using FT.

Figure 12.7 A new node joining an existing Chord.

Figure 12.8 Adjustment of finger tables.

Figure 12.9 Illustrating Chord stabilization process.

Figure 12.10 Leaf set, first four rows of Pastry routing table and neighborh...

Figure 12.11 Lookup for a target node, corrects one digit at a time.

Figure 12.12 2‐torus generated by a circle rotating along a coplanar axis.

Figure 12.13 Splitting of coordinate space in CAN.

Figure 12.14 Binary tree abstraction for splitting CAN.

Figure 12.15 Routing in CAN.

Figure 12.16 Proximity metric decides which machines handles which files.

Figure 12.17 The ‐lists of a Kademlia node.

Figure 12.18 Lookup queries and replies.

Chapter 13

Figure 13.1 Cache coherence in multicore architecture.

Figure 13.2 Layout of a manycore system depicting memory hierarchy.

Figure 13.3 Steps of MapReduce operation.

Figure 13.4 Difference between traditional and reduction‐based MapReduce.

Figure 13.5 Fork‐join execution semantics.

Figure 13.6 Picture of data source with critical tiles.

Figure 13.7 Conceptual representation of sequential consistency.

Figure 13.8 Sequential consistency: (a) “correct” order and (b) violation of...

Figure 13.9 Sequentially consistent and linearizability. (a) Not linearizabl...

Figure 13.10 Program order not necessary for correctness.

Figure 13.11 Accessing order which affects correctness.

Figure 13.12 Weak consistency. (a) Valid:

S

is performed after

R(x)

. (b) inv...

Figure 13.13 Illustrating acquire and release.

Figure 13.14 Operation categories for release consistency memory model.

Figure 13.15 Comparing power and execution of memory consistency models.

Figure 13.16 Types of S‐DSM algorithms.

Figure 13.17 Central server algorithm.

Figure 13.18 Migration algorithm.

Figure 13.19 Full replication algorithm.

Chapter 14

Figure 14.1 RAID architecture.

Figure 14.2 SAN architecture.

Figure 14.3 Key‐value database.

Figure 14.4 document database.

Figure 14.5 Wide‐column database.

Figure 14.6 Graph database.

Figure 14.7 Example graph to illustrate Pregel algorithm.

Figure 14.8 Graph partitions for Giraph algorithm.

Figure 14.9 Lambda architecture.

Figure 14.10 Data clustering.

Chapter 15

Figure 15.1 A graphical representation for the RDF statements in Listing 15....

Figure 15.2 Graphical representation of distributed knowledge described in L...

Figure 15.3 Frame‐based knowledge representation.

Figure 15.4 DBpedia architecture. Source: sharafmaksumov/Adobe Stock (Globe ...

Figure 15.5 SPARQL query example.

Figure 15.6 Cluster‐TDB architecture.

Figure 15.7 Federated architecture for SPARQL query processing.

Figure 15.8 BGP for SPARQL query‐2 (Listing 15.7).

Figure 15.9 Source‐index hierarchy for a sample schema path.

Figure 15.10 A representative distributed sensor network architecture.

Figure 15.11 Stimulus–sensor–observation pattern: model for SSN ontology.

Figure 15.12 Bayesian data fusion in distributed system.

Chapter 16

Figure 16.1 Abstract architecture of an agent.

Figure 16.2 Mobile agent.

Figure 16.3 Multi‐agent systems.

Figure 16.4 Classes of performatives.

Figure 16.5 FIPA agent communication model.

Figure 16.6 Possible message flows in FIPA

request interaction

protocol. (a)...

Figure 16.7 FIPA agent management reference model.

Figure 16.8 JADE interaction protocol for agent migration.

Figure 16.9 Local plan conflict.

Figure 16.10 Dependencies of actions in multi‐agent systems.

Figure 16.11 Contract‐net interaction protocol.

Figure 16.12 Allocation of multiple tasks.

Figure 16.13 Foraging behavior of ants.

Figure 16.14 Ant colony optimization algorithm with traveling salesman probl...

Figure 16.15 Example road network and base‐station configuration of a taxi s...

Figure 16.16 Example city connectivity for ant colony optimization problem....

Chapter 17

Figure 17.1 A framework for a distributed ledger system.

Figure 17.2 Structure of a blockchain ledger.

Figure 17.3 Forking in blockchain.

Figure 17.4 Asset tracking in blockchain.

Figure 17.5 The structure of a tangle.

Figure 17.6 (a) Structure of a hashgraph, and (b) structure of an event in a...

Figure 17.7 An extended hashgraph.

Figure 17.8 Distributed ledge as a state transition machine.

Figure 17.9 Overlay in a typical smart‐home network.

Chapter 18

Figure 18.1 Collaborative E‐learning systems.

Figure 18.2 BigBlueButton web‐conferencing system.

Figure 18.3 The organization of the E‐learning platform.

Figure 18.4 Whiteboard packet format. (a) Packet Id. (b) Packet format.

Figure 18.5 Mesh structure and initial request of a joining peer. (a) Partia...

Figure 18.6 Mesh pull strategy. (a) Initial pull request. (b) Next pull requ...

Figure 18.7 An example of de Bruijn graph .

Figure 18.8 Prefix match and substring routing.

Figure 18.9 Physical nodes forming a de Bruijn DHT.

Figure 18.10 Joining of two peers. (a) First node. (b) Next node.

Figure 18.11 Joining of two peers. (a) Link removed. (b) Links & are a...

Figure 18.12 The stabilization of the maximum path length and churning. (a) ...

Figure 18.13 Streaming latency experience at the end‐devices.

Figure 18.14 Experimental results on node out‐degrees. (a) Maximum out‐degre...

Figure 18.15 Average number of hops and load distribution of queries in de B...

Guide

Cover Page

IEEE Press

Title Page

Copyright

About the Authors

Preface

Acknowledgments

Acronyms

Table of Contents

Begin Reading

Index

Wiley End User License Agreement

Pages

ii

iii

iv

xv

xvi

xvii

xviii

xix

xx

xxi

xxii

xxiii

xxiv

xxv

xxvi

xxvii

1

2

3

4

5

6

7

8

9

10

11

12

13

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

525

526

527

528

529

530

531

532

533

IEEE Press445 Hoes LanePiscataway, NJ 08854

IEEE Press Editorial BoardSarah Spurgeon, Editor in Chief

Jón Atli Benediktsson

Anjan Bose

Adam Drobot

Peter (Yong) Lian

Andreas Molisch

Saeid Nahavandi

Jeffrey Reed

Thomas Robertazzi

Diomidis Spinellis

Ahmet Murat Tekalp

About IEEE Computer Society

IEEE Computer Society is the world's leading computing membership organization and the trusted information and career‐development source for a global workforce of technology leaders including: professors, researchers, software engineers, IT professionals, employers, and students. The unmatched source for technology information, inspiration, and collaboration, the IEEE Computer Society is the source that computing professionals trust to provide high‐quality, state‐of‐the‐art information on an on‐demand basis. The Computer Society provides a wide range of forums for top minds to come together, including technical conferences, publications, and a comprehensive digital library, unique training webinars, professional training, and the Tech Leader Training Partner Program to help organizations increase their staff's technical knowledge and expertise, as well as the personalized information tool my Computer. To find out more about the community for technology leaders, visit http://www.computer.org.

IEEE/Wiley Partnership

The IEEE Computer Society and Wiley partnership allows the CS Press authored book program to produce a number of exciting new titles in areas of computer science, computing, and networking with a special focus on software engineering. IEEE Computer Society members receive a 35% discount on Wiley titles by using their member discount code. Please contact IEEE Press for details. To submit questions about the program or send proposals, please contact Mary Hatcher, Editor, Wiley‐IEEE Press: Email: [email protected], John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030‐5774.

Distributed Systems

Theory and Applications

Ratan K. GhoshFormer ProfessorIIT Kanpur

Hiranmay GhoshFormer AdviserTCS ResearchAdjunct ProfessorIIT Jodhpur

Copyright © 2023 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey. Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per‐copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750‐8400, fax (978) 750‐4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748‐6011, fax (201) 748‐6008, or online at http://www.wiley.com/go/permission.

Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates in the United States and other countries and may not be used without written permission. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762‐2974, outside the United States at (317) 572‐3993 or fax (317) 572‐4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging‐in‐Publication Data

Names: Ghosh, Ratan K., author. | Ghosh, Hiranmay, author.

Title: Distributed systems : theory and applications / Ratan K. Ghosh, Hiranmay Ghosh.

Description: Hoboken, New Jersey : Wiley, [2023] | Includes index.

Identifiers: LCCN 2022055650 (print) | LCCN 2022055651 (ebook) | ISBN 9781119825937 (cloth) | ISBN 9781119825944 (adobe pdf) | ISBN 9781119825951 (epub)

Subjects: LCSH: Electronic data processing–Distributed processing. | Computer networks.

Classification: LCC QA76.9.D5 G486 2023 (print) | LCC QA76.9.D5 (ebook) | DDC 004/.36–dc23/eng/20221207

LC record available at https://lccn.loc.gov/2022055650

LC ebook record available at https://lccn.loc.gov/2022055651

Cover Design: Wiley

Cover Image: © ProStockStudio/Shutterstock

About the Authors

Ratan Ghosh is an education professional skilled in Distributed Systems, Wireless Networking, Mobile Computing, and Wireless Sensor Networks. He has been a Professor in Computer Science and Engineering at IIT Kanpur until July 2019. He also held a Professor's position in the Department of Computer Science and Engineering at IIT Guwahati on lien from IIT Kanpur during 2001‐2002. After superannuation from IIT Kanpur he was a Visiting Professor in the EECS Department at IIT Bhilai during 2019‐2020. Concurrently he was affiliated to BITS-Mesra as an Adjunct Professor until November, 2022. At present he is a Distinguished Visiting Professor, Mentor and Advisor to The Assam Kaziranga University‐Jorhat.

Dr. Ghosh completed his PhD at IIT Kharagpur and his undergraduate studies at Ravenshaw University, Cuttack. He has collaborated actively with researchers from several countries, particularly in parallel computing, wireless sensor networks, mobile computing, and distributed systems, on problems in algorithms, network protocols, transient social networking, peer‐to‐peer systems, and IoT applications.

Dr. Ghosh authored the books Wireless Networking and Mobile Data Management in 2017 and Foundations of Parallel Processing in 1993. He is a life member of ACM.

Hiranmay Ghosh is a researcher in Computer Vision, Artificial Intelligence, Cognitive Computing, and Distributed Systems. He had received his PhD degree from IIT‐Delhi and his BTech degree in Radiophysics and Electronics from the Calcutta University. He is an Adjunct Professor with IIT‐Jodhpur.

Hiranmay had been associated with industrial research for more than 40 years and had been instrumental in academy–industry collaborations. He had been a research adviser with TCS and has been invited by IIT‐Delhi, IIT‐Jodhpur and NIT‐Karnataka to teach in the capacity of Adjunct Faculty. He has several publications to his credit, including the books Multimedia Ontology: Representation and Applications and Computational Models for Cognitive Vision.

Hiranmay is a Senior Member of IEEE, Life Member of IUPRAI, and a Member of ACM.

Preface

The concept of the book germinated about two and half years back when we were informally exchanging our experiences and thoughts on what could typically constitute a course on distributed systems for senior undergraduates and graduate students in engineering institutes. The existing textbooks on the subject, authored by eminent scientists, present an excellent discourse on the rich and interesting theoretical foundations that academicians across the board appreciate and adopt in computer science and engineering curricula. At the same time, distributed systems have recently evolved and grown beyond their conventional boundaries. There is plenty of published material on various new topics in the interfacing area of computing, communication, and Internet technologies. These developments have brought in new challenges for distributed computing technology, and we think they need to find a place in a modern curriculum on the subject. In particular, we focus on distributed applications involving large volumes of distributed data, cyber‐physical systems, and distributed intelligence. Though excellent research articles and books are available on these topics, they tend to focus on aspects of the technology other than distributed computing. It is challenging to garner a holistic view of the subject by joining the knowledge dots from various books and research articles. We try to address this challenge in our work.

We debated if there is a space for a new textbook encompassing protocols, theory, and applications that also included distributed data analytics and smart environments. If so, the challenge is to organize the material and package it in a form that might have a broader academic acceptance while serving as a reference text for the developers. We drew our experiences in the roles of an instructor and a practitioner. We interacted with the students and the developers to identify the knowledge gaps that hamper their career growth in an evolving discipline. We have observed over time that the merging of communication technologies, computing, and the Internet motivated smart developers to build large applications over geographically dispersed distributed computing resources, mobile hand‐held systems, and sensor‐controlled smart devices. Many toolchains were developed to aid the building of these applications. Applications often needed to interface with human and program‐controlled actors using petabytes of data stored over large data centers that communicate through the Internet. Earlier, data from different distributed sources were fed to a central computer over a telecommunication network for processing. While this approach worked satisfactorily for small and mid‐sized applications, it could not scale well due to the capacity limitation of the central processing node and the excessive network traffic. Besides capacity, the reliability of the data and system availability became severe handicaps for the centralized approach. The exponential growth in data traffic due to sensory data, videos, and requirements for distributed data analytics compounded the problems for the communication networks. It was soon realized that distributed computing, where data for an application is processed on multiple independent and interconnected computers, is the key to achieving scalability and reliability in large‐scale distributed application systems.

The paradigm of distributed computing has been around for several decades now with the pioneering works of Turing awardees like Leslie Lamport, Edgar W. Dijkstra, Barbara Liskov, among others. At the same time, industry requirements fueled research and development. As a result, the subject of distributed systems witnessed spectacular growth over the years. Starting with client–server applications, where some data preprocessing and rendering of the results were delegated to the client computers, distributed computing has matured to peer‐to‐peer systems where the participating application components could make independent decisions. We find heterogeneous devices in such peer‐to‐peer systems, with large servers with tremendous processing power and storage capacity at one end of the spectrum and severely constrained IoT devices at the other. We see large and “open” distributed applications, where computer systems owned by different individuals or groups, even with unknown ownership, can participate for specific periods. Addressing security concerns in such open systems created newer and non‐predictable challenges to the design of distributed systems today.

In this book, we have attempted to bridge the gap between the foundational material and contemporary advances in distributed computing. To give a complete and coherent view of the subject, we start with the fundamental issues and theories of distributed computing and progressively move to advanced and contemporary topics. We present the subject in three layers of abstraction, namely,

Network

, dealing with basic connectivity of the computers and processes running on them.

Middleware tools

, which provide a layer of abstraction over the possibly heterogeneous network layer, and facilitates system development efforts.

Application frameworks

enable the development of various distributed applications.

In summary, we expect a reader of the book will be able to

Get a holistic coverage of the subject by addressing different layers of abstraction in a distributed system, namely network, middleware tools, and application framework.

Relate the theoretical foundations with the contemporary advances in distributed systems.

Familiarity with distributed computing principles deployed in the applications frameworks that are crucial for developing smart environments and distributed automation requirements for industry 4.0.

The book's content has been organized in the form of three main threads as in Figure 1. The middle thread marked “A,” consisting of nine chapters, could be sufficient for the first‐level course on distributed systems. An advanced level course on operating systems could consist of the first seven chapters and a few additional topics labeled by the left thread marked “B.” Understanding case study requires knowledge of peer‐to‐peer system apart from the basics of distributed system covered in thread “A.” It is also possible to use the text for an advanced graduate‐level course on distributed systems oriented toward intelligent data management and applications. It is represented by the thread marked “C” to the right in the content flow diagram.

Figure 1 Topics and flow diagram of book's content.

Kolkata, Mysore (India)

Ratan K. GhoshHiranmay Ghosh

Acknowledgments

The subject of Distributed Computing has seen fascinating growth over the last couple of decades. It has resulted in many practical and useful systems that pervade our daily lives. At the outset, we acknowledge the efforts of numerous researchers and practitioners, without which the content of this book would not have materialized.

This book grew from several courses on Distributed Systems, and related topics offered to senior undergraduate and graduate students at many institutes, namely IIT‐Kanpur, IIT‐Bhilai, IIT‐Delhi, and IIT‐Jodhpur. The interaction with the students and the experiments conducted with their help were an incredible learning process. We acknowledge the contributions of these students to shaping the book's contents. We also acknowledge the encouragement of our colleagues at these institutes, who contributed valuable inputs to defining the curricula for the subjects.

It was a great experience to work together with the Wiley‐IEEE Press editorial team. The book would not have seen the light of the day but for their support. In particular, we acknowledge the support received from Mary Hatcher, Senior Acquisition Editor and her assistant Victoria Bradshaw while working with the proposal. We thankfully acknowledge the efforts of Teresa Netzler, Managing Editor who handled the long review process with persistence. We acknowledge with thanks Sundaramoorthy Balasubramani, Content Refinement Specialist for his outstanding assistances in copyediting and proof corrections. We also thank the anonymous reviewers of the book proposal, whose comments led to substantial improvements in the organization and the contents of the book.

Ratan would like to thank Rajat Moona of IIT Gandhinagar for providing critical infrastructural support during a transitional phase that significantly eased the preparation of the major part of the manuscript. Rajat, as usual, has been enthusiastically supportive. Ratan further expresses his gratitude to Prof G. P. Bhattacharjee, former professor of IIT Kharagpur. As a true mentor, GPB is always a source of inspiration for all academic pursuits. Ratan also acknowledges the support and encouragement from Prof R.K. Shyamasundar of IIT Bombay. He thankfully acknowledges the input from his daughter Ritwika of Bodo.ai, during the initial planning of the book. It helped shape the contents of Chapters 3 and 4. Last but not least, he feels obliged to his spouse Sarbani. Being engaged in two back‐to‐back book projects has been like a sabbatical from family responsibilities. Sarbani willingly handled the extra burden so that Ratan could focus on completing these projects. Half the credit goes to Sarbani for her support and understanding.

Hiranmay would like to thank Prof. Santanu Chaudhury of IIT‐Jodhpur, Prof. Pankaj Jalote of IIIT‐Delhi, and Prof. V.S. Subrahmanian of Dartmouth College for their constant support and encouragement in his academic and professional pursuits. He feels indebted to his spouse Sharmila, for absolving him of his household obligations and bearing up with his isolation in the study. Her occasional queries about the status of the book, particularly when the progress was slow, have been an encouragement to Hiranmay and have helped him focus on the manuscript and complete his assignment within the stipulated time. And last but not least, he thanks the first author for inviting him to participate in the project of writing this book.

Ratan K. GhoshHiranmay Ghosh

Acronyms

2PC

two phase commit

3PC

three phase commit

6LowPAN

IPv6 over low‐power wireless personal area networks

ACL

agent communication language

ACO

ant colony optimization

AMQP

advanced message queuing protocol

AMS

agent management services

API

application programming interface

AS

autonomous system

ASIC

application specific integrated circuit

BBB

BigBlueButton

BFT

Byzantine fault‐tolerance

BGP

Byzantine general problem

BGP

basic graph pattern

BIRCH

balanced iterative reducing and clustering using hierarchies

BM

block manager

BSS

Birman Stephenson and Schiper

BTC

bitcoin

C

consensus

CAN

content addressable P2P network

CDN

content distribution network

CDPS

cooperative distributed problem solving

CFP

call for proposal

CGI

common gateway interface

CNAME

canonical name

CNP

contract net protocol

CoAP

constrained application protocol

CoTS

components of the shelf

CPU

central processing unit

CRUD

create, read, update(/write), delete

CS

critical section

CSMA/CA

carrier sensing multiple access with collision avoidance

CSMA/CD

carrier sensing multiple access with collision detection

CSV

comma‐separated values

CTP

collection tree protocol

DAG

directed acyclic graph

DARPA

defense advanced research projects agency

DCMI

Dublin core metadata initiative

DDBMS

distributed data base management

DFS

distributed file systems

DHCP

dynamic host control protocol

DHT

distributed hash table

DLT

distributed ledger technology

DNS

domain name service

DnS

descriptions and situations

DOI

digital object identifier

DOLCE

descriptive ontology for linguistic and cognitive engineering

DSN

distributed sensor network

DUL

DOLCE+DnS ultralite

ECDSA

elliptic curve digital signature algorithm

ETX

expected transmission count

FCFS

fist come first serve

FELGossip

fair efficient location‐based gossip

FIFO

first in first out

FiGo

firefly gossip

FIPA

Foundation of Physical Agents

FoaF

friend of a friend

FPGA

field programmable gate array

FQDN

fully qualified domain name

FT

finger table

FTP

file transfer protocol

GALS

globally asynchronous and locally synchronous

GB

giga bytes ( bytes)

Gbps

giga‐bits per second ( bits per second)

GHS

Gallagher Humblet and Spira

GID

group ID

GMT

Greenwich mean time

GPS

global positioning system

HDFS

hadoop distributed file system

HMR

home mediation router

HPC

high performance computing

HTML

hypertext markup language

HTTP

hypertext transfer protocol

IC

interactive consistent

ICANN

international committee for assigned names and numbers

IDL

interface definition language

IEC

International Electrotechnical Commission

IEEE

Institution of Electrical and Electronics Engineers

IoT

internet of things

IP

Internet Protocol

IPv4

Internet Protocol version 4

IPv6

Internet Protocol version 6

IRI

international resource identifier

ISIS

intermediate system to intermediate system

ISO

International Standard Organization

ISP

internet service provider

IST

Indian Standard Time

JADE

Java agent development environment

JPEG

joint photographic experts group

JSON

JavaScript Object Notation

JVM

Java virtual machine

KQML

Knowledge Query and Manipulation Language

LAN

local area network

LCA

lowest common ancestor

LCP

lowest common prefix

LGossip

location‐based gossip

LLN

low power lossy network

LM

local manager

M2M

machine to machine

MAC

media access control

MAS

multi‐agent system

MFENCE

memory fence

MMU

memory management unit

MOC

message oriented communication

MPI

message passing interface

MQTT

message queue telemetry transport

MR

mediation router

MRMW

multiple readers, multiple writers

MRSW

multiple reader, single writer

MSB

most significant bit

MTU

maximum transmission unit

NAT

network address translation

NIST

National Institution of Standard and Technology

NoC

network on chip

NoSQL

not (only) SQL

NS

name server

NTP

network time protocol

NUMA

non uniform memory access

OASIS

Organization for the Advancement of Structured Information Standards

OM

oral message

OS

operating systems

OWL

web ontology language

P2P

peer to peer

P2P‐IPS

peer to peer interactive presentation system

PDF

portable document format

PGM

property graph model

PHP

hypertext preprocessor

PID

process ID

PoET

proof of elapsed time

PoS

proof of stake

POSIX

portable operating system interface

PoW

proof of work

PSO

partial store order

PTR

pointer record

QoS

quality of service

RAID

redundant array of inexpensive disks

RDF

resource description framework

RDFS

RDF schema

REST

REpresentational State Transfer

RFC

request for comments

RMI

remote method invocation

RNS

root name server

RPC

remote procedure call

RPS

random peer sampling

RTT

round trip time

S‐DSM

software distributed shared memory

SAN

storage area network

SASL

simple authentication and security layer

SC

sequential consistency

SDSS

Sloan digital sky survey

SES

Schiper Eggli and Sandoz

SHA

secure hash algorithm

SI

susceptible and infected

SIP

session initiation protocol

SIR

susceptible, infected and removed

SKOS

simple knowledge organization system

SMP

symmetric multi‐processor

SMR

shingled magnetic recording

SNS

social network systems

SOA

service oriented architecture

SOAP

simple object access protocol

SPARQL

SPARQL protocol and RDF query language

SQL

structured query language

SRSW

single reader single writer

SSH

secured shell

SSN

semantic sensor network

TB

terra bytes ( bytes)

TCP

transport control protocol

TDB

triplet data base

TF‐IDF

term frequency‐inverse document frequency

TSO

total store order

TTL

time to live

UDP

user datagram protocol

UMA

uniform memory access

URI

universal resource identifier

URL

uniform resource locator

UT

universal time

UTC

coordinated universal time

VM

virtual machine

W3C

world wide web consortium

WAN

wide area network

WSDL

web services description language

WSGI

web server gateway interface

WSN

wireless sensor network

XML

extensible markup language

XQuery

XML query language

1Introduction

A distributed system consists of many independent units, each performing a different function. The units work in coordination with each other to realize the system's goals. We find many examples of distributed systems in nature. For instance, a human body consists of several autonomous components such as eyes and ears, hands and legs, and other internal organs. Yet, coordinated by the brain, it behaves as a single coherent entity. Some distributed systems may have hierarchic organizations. For example, the coordinated interaction among human beings performing various roles realizes the goals of human society. We find such well‐orchestrated activities in lower forms of animals too. For example, in a beehive an ensemble of bees exhibit coordinated and consistent social behaviors fulfilling their goals of foraging.

Inspired by nature, researchers have developed a distributed systems paradigm for solving complex multi‐dimensional computation problems. This book aims to provide a narrative for the various aspects of distributed systems and the computational models for interactions at multiple levels of abstractions. We also describe the application of such models in realizing practical distributed systems. In our journey through the book, we begin with the low‐level interaction of the system components to achieve performance through parallelism and concurrency. We progressively ascend to higher levels of abstractions to address the issues of knowledge, autonomy, and trust, which are essential for large distributed systems spanning multiple administrative domains.

1.1 Advantages of Distributed Systems

A distributed system offers many advantages. Let us illustrate them with a simple example. Figure 1.1 depicts a distributed system for evaluation of simple arithmetic expressions. The expression‐evaluator in the system divides the problem into smaller tasks of multiplications and additions and engages other modules, namely, a set of adders and multipliers, to solve them. Hosting the modules on different computers connected over a network is possible. It schedules the activities of those modules and communicates the final result to the user. We can notice several advantages of a distributed computing even through this trivial example:

Figure 1.1 Illustrating distributed computing.

Performance enhancement

: The system may engage multiple components to perform subtasks, e.g., multiplications, in parallel, resulting in performance improvement. However, the distribution of the components over multiple hardware elements causes increased communication overheads. So, an analysis of trade‐off is necessary between parallel computation and communication.

Specialization and autonomy

: Each module may be designed independently for performing a specific task, e.g., addition or multiplication. A component can implement any specific algorithm irrespective of the type of algorithms deployed in the other modules. So, localization of task‐dependent knowledge and the local optimization of the modules for performance enhancements are possible. It simplifies the design of the system. The modules can even be implemented on disparate hardware and in different programming environments by various developers. A change in one module does not affect others, so long as the interfaces remain unchanged.

Geographic distribution and transparency

: It is possible to locate the components on machines at various geographical locations and administrative domains. The geographical distribution of the components is generally transparent to the applications, introducing flexibility of dynamic redistribution. For example, the a piece of computation can be scheduled on a computing node that has the least load at a given point of time, and can be shifted to another node in case of a failure. It results in reuse and optimal utilization of the resources. As another example, the replicas of a storage system can be distributed across multiple geographical locations to guard against accidental data loss.

Dynamic binding and optimization

: A distributed system can have a pool of similar computational resources, such as adders and multipliers. These resources may be dynamically associated with different computing problems at different points in time. Further, even similar resources, like the multipliers, may have different performance metrics, like speed and accuracy. The system can choose an optimal set of modules in a specific problem context. Such optimum and dynamic binding of the resources leads to improvement of overall system performance.

Fault tolerance

: The availability of a pool of similar resources aids in fault tolerance in the system. If one of the system components fails, then the task can migrate to another component. The system can experience a graceful performance degradation in such cases, rather than a system failure.

Openness, scalability, and dynamic reconfigurability

: A distributed system can be designed as an open system, where individual components can interact with a set of standard protocols. It facilitates the independent design of the components. Loose coupling between the system components helps in scalability. Further, we can replace deprecated components by new components without shutting down a system.

1.2 Defining Distributed Systems

Leslie Lamport's seminal work [Lamport 2019] laid down the theoretical foundations of time, clock, and event ordering in a distributed system. Lamport realized that the concept of sequential time and system state does not work in distributed systems. A failure in a distributed system is one of the toughest problems to understand. The failure is meaningful only in the context of time. Whether a computing system or a link has failed is indistinguishable from an unusually late response. Lamport recognized the importance of failure detection and recovery in a distributed system through the following famous quip [Malkh 2013]:

“A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable.”

Understandably, fault tolerance [Neiger and Toueg 1988, Xiong et al. 2009], which includes detection of failures and recovery from faults, is a dominant area of research in distributed systems.

There are many technical‐sounding definitions, but all seem to converge on the importance of fault tolerance in distributed systems. We plan to discuss fault tolerance in this book sometime later. However, to get a flavor of different ways of defining a distributed system, let us examine a few of those found in the literature [Kshemkalyani and Singhal 2011].

Definition 1.1(Collection and coordination): A distributed system is a collection of computers not sharing a common memory or a common physical clock that communicates by messages over a communication network and where each computer has its memory and runs on its OS. Typically computers are semi‐automatic, loosely coupled when they cooperate to address a problem collectively.

Definition 1.2(Single system view): A collection of independent computers that appear to the users of the system as a single coherent computer.

Definition 1.3(Collection): A term used to describe a wide range of computer systems from a weakly coupled system such as a wide area network to strongly coupled systems such local area network, to very strongly coupled multiprocessor systems.

The running idea behind all three definitions stated earlier is to capture certain basic characteristics of a distributed system; namely,

There is no common clock in a distributed system.

It consists of several networked autonomous computers, each having its clock, memory, and OS.

It does not have a shared memory.

The computers of a distributed can communicate and coordinate through message passing over network links.

However, we feel that the definitions are still inadequate in missing out on two key aspects of Lamport's observation of a distributed system. We propose the following new definition.

Definition 1.4 (Proposed definition): A distributed system consists of several independent, geographically dispersed, and networked computing elements such as computers, smartphones, sensors, actuators, and embedded electronic devices. These devices communicate among themselves through message passing to coordinate and cooperate in satisfying common computing goals, notwithstanding the occasional failures of a few links or devices.

The proposed definition covers the basic characteristics of a collection of networked computing devices. It indicates that a collections of independent components integrated as a unified system is a distributed system that

Subsumes

Definitions 1.3

and

1.2

,

Covers coordination aspect as in

Definition 1.1

,

Includes fault tolerance and message passing aspects of Lamport's observation.

1.3 Challenges of a Distributed System

Some of the well‐understood bottlenecks for implementing a distributed system are the following:

Centralized algorithms

: A single computer is responsible for program control decisions. These algorithms are suitable for client‐server model of computation where a server may be overwhelmed by many simultaneous client requests.

Centralized data

: Consider the situation where a single database is used for all telephone numbers worldwide. Searching such a database, even with indexing, could be extremely time‐consuming.

Centralized server

: Only one single server is available for all service requests. All user requests are queued for the service at the server, and each service request experiences large queuing delays.

So, distributed algorithms are key to the development of a distributed system. A few of the top‐level characteristics of distributed algorithms are the following:

There is no implicit assumption about the existence of a global clock.

No machine has complete data (data is distributed).

Every machine makes decisions on local information.

Failure of any single machine must not ruin the algorithm.

However, the basis for designing distributed algorithms is often much stronger than those stated above. It includes the assumptions such as guaranteed (reliable), ordered delivery of messages with low latency. So, most of the distributed algorithms work well in LAN environment, which provides:

Reliable synchronous network, and

Can use both broadcast and multicast.

The two major problems that seriously impede the scalability of distributed algorithms to WANs are:

Trust and security

: Communication has to cross through multiple administrative domains. Administrators of different domains enforce varying security and trust policies.

Centralized component

: Affects performance severely.

The scalability of a distributed system appears to be a performance problem limited by the server capability and the network bandwidth. We need to follow a few simple guidelines for designing scalable distributed algorithms. They are as follows:

Reduce dependence on remote servers.

Hide network latency by applying the following tricks:

Split problems into independent parts.

Use asynchronous communication.

Rely on local computation as much as possible.

Breakdown large messages and check syntactical correctness of requests and basic data validations at the client end.

Use caching and replication extensively in the applications.

However, the problem of scaling is not simple to solve. We have to solve many other orthogonal issues before using the suggested design guidelines effectively. Some of the issues that affect scalability are:

Maintaining consistency of replicas

. It needs global synchronization. Relaxing consistency can avoid strict synchronization requirements. But doing so would mean we can implement only a certain class of applications in distributed systems. Algorithm designers need to spend more time addressing many low‐level system‐related issues.

Too many assumptions on reliability, stability, and security of network

. These assumptions are as follows:

The underlying network consists of homogeneous nodes with a fixed topology.

The network latency is zero, and the bandwidth is infinite.

Message transport cost is nil, and

All the computation nodes are under a single administrative domain.

It is not possible for a distributed system over a wide area computer network to guarantee reliable, secure, and ordered delivery of messages with low latency. Therefore, only a few assumptions made in the design of distributed algorithms may hold even for a distributed system over a LAN segment.

1.4 Goals of Distributed System

The most apparent goals for using distributed systems are economics and fast processing. With distributed systems, sharing and connectivity become less expensive. Therefore, it leads to better cohesive collaborations and an overall increase in the productivity of system developers.

The sharing of resources is the most important goal in a distributed system. However, resource sharing goes much beyond exploiting concurrency in computation. The users may access any remote resources and, at the same time, share their respective local resources with others using a standard interface. For example, the users may remotely access a multiprocessor system to relocate the compute‐intensive task or access any specialized database hosted remotely. With increased sharing and connectivity, the system vulnerabilities and risks related to privacy and security increase enormously.

1.4.1 Single System View

A coherent single system view of a distributed system is possible through use of many layers of abstractions between the user/application and the OS/ communication layers underneath. Therefore, the requirement for a single system view characterize most of the goals of a distributed system.

The main concern is concealing (hiding) the physical separation of the distributed system components from the application programmers and the users. The hiding of separation transcends different levels of transparency requirements in a distributed system.

1.4.2 Hiding Distributions

A user should not bother about the underlying platform. The system should provide uniform access to both remote and local objects. For example, accessing a remote file or printer should be as simple as accessing a local printer or a file. Therefore, the calling interface for an object class's local or remote method must be identical. The SQL queries for accessing database tables should be identical irrespective of the nature of the back‐end database. It requires preserving both syntactic and semantic similarity between distributed and sequential access.

The migration of objects (processes or data) from one location to another should be transparent to a user. Migration may be needed for various reasons, including performance enhancement, load balancing, reliability, and hiding failures.

The physical locations or the details of the topological organization of resources in a distributed system should not matter to the users. For example, a user may be able to access local or remote web documents uniformly. There should be a uniform and uniquely defined naming scheme for the resources, i.e., each resource has a uniform resource identifier (URI).

Relocation of resources may be necessary for better organization and management of resources, including a performance enhancement. Relocation should not be confused with migration. Migration refers to relocating a resource while it is in use; whereas relocation is moving a resource to a different location for better management.

With replication, a system becomes highly available. It also reduces access latency. Replicas of files, DDBMS, code repositories, and mirrors for web pages make a system highly available. However, replica maintenance is a complex problem. For example, how do the replicas get synchronized? Whether a write in a replica should propagate to other replicas at once (write‐through) or at the time of the next read (lazy propagation). Therefore, maintaining replica transparency is one of the important goals of a distributed system.

For economic reasons, some resources like printer, DDBMS tables should be sharable by many concurrently executing processes. Concurrency control is the principal objective of a distributed system. The issues encountered in concurrency control are problematic but interesting in developing distributed applications.

The major issues in achieving concurrency transparency are as follows:

Event ordering

: It ensures that all accesses to any shared resource provides a consistent view to all the users of the system.

Consensus and coordination

: Certain system activities such as initiation of a computation, a collective decision on partial computations, sequencing a set of tasks requires consensus and coordination.

Mutual exclusion

: Any resource that cannot be shared simultaneously must be used in exclusive mode by the competing processes. In other words, all the accesses to non‐shareable resources must be serializable.

No starvation

: Processes cannot indefinitely prevent any particular process from accessing a resource.

No deadlock

: It ensures that a situation will never arise wherein a collection of processes are prevented from progress even though no single process requests more than the resources available in the system.

Hiding at least partial failures from the users should be possible. After recovery from transient failures, the application should run to completion.