Distributed Network Systems

• Weekly hours
• Competences
• Objectives
• Contents
• Activities
• Teaching methodology
• Evaluation methodology
• Bibliography
• Previous capacities

Teachers

Person in charge

• Jordi Guitart Fernandez ( )

Weekly hours

Competences

Technical Competences

Common technical competencies

• CT5 - To analyse, design, build and maintain applications in a robust, secure and efficient way, choosing the most adequate paradigm and programming languages.
  • CT5.6 - To demonstrate knowledge and capacity to apply the fundamental principles and basic techniques of parallel, concurrent, distributed and real-time programming.
• CT6 - To demonstrate knowledge and comprehension about the internal operation of a computer and about the operation of communications between computers.
  • CT6.4 - To demonstrate knowledge and capacity to apply the characteristics, functionalities and structure of the Distributed Systems and Computer and Internet Networks guaranteeing its use and management, as well as the design and implementation of application based on them.

Technical Competences of each Specialization

Information technology specialization

• CTI1 - To define, plan and manage the installation of the ICT infrastructure of the organization.
  • CTI1.3 - To select, deploy, integrate and manage information system which satisfy the organization needs with the identified cost and quality criteria.
• CTI3 - To design solutions which integrate hardware, software and communication technologies (and capacity to develop specific solutions of systems software) for distributed systems and ubiquitous computation devices.
  • CTI3.1 - To conceive systems, applications and services based on network technologies, taking into account Internet, web, electronic commerce, multimedia, interactive services and ubiquitous computation.
  • CTI3.2 - To implement and manage ubiquitous systems (mobile computing systems).
  • CTI3.4 - To design communications software.

Transversal Competences

Third language

• G3 [Avaluable] - To know the English language in a correct oral and written level, and accordingly to the needs of the graduates in Informatics Engineering. Capacity to work in a multidisciplinary group and in a multi-language environment and to communicate, orally and in a written way, knowledge, procedures, results and ideas related to the technical informatics engineer profession.
  • G3.1 - To understand and use effectively handbooks, products specifications and other technical information written in English.

Objectives

1. Understand the definition of distributed system and its possible applications, as well as challenges to be faced to design and implement it.
   Related competences: CTI3.1, CTI3.4, CT6.4, CTI1.3,
   Subcompetences:
   • Know the possible applications of a distributed system
   • Put examples of distributed systems
   • Understand the challenges to design and implement a distributed system: heterogeneity, lack of global view, security, coordination, asynchrony, openness, transparency, fault tolerance, scalability
   • Understand the definition of distributed system
2. Understand the basic system architectures in distributed systems.
   Related competences: CTI3.1, CTI3.4, CT6.4, CT5.6,
   Subcompetences:
   • Know the basic system architectures in distributed systems: centralized (client-server), decentralized (peer-to-peer), hybrid
3. Understand the basic mechanisms of communication in a distributed system: invocation of remote operations, message-based communication, event-based communication and channel-based communication (streams), and write distributed applications that communicate by sending messages.
   Related competences: CTI3.1, CTI3.4, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Know the basic communication paradigms in distributed systems: remote procedure call, message passing, message queuing, group communication, publish/subscribe, shared data spaces, shared-memory, mobile code, stream-oriented
   • Write distributed applications that communicate by sending messages
   • Know the communication mechanism based on streams: transmission modes, quality of service
   • Know the event-based communication mechanism: publish/subscribe systems
   • Know the different types of communication in a distributed system: direct vs. indirect (space and time uncoupling), persistent vs. transient, synchronous vs. asynchronous, discrete vs. continuous
   • Know the communication mechanism based on messages: transient (Sockets) vs. persistent (MOM)
   • Know the communication mechanism by invoking remote procedures (RPC): basic operation, parameter passing, extensions of the basic model, failure handling, remote method invocation (RMI)
4. Understand the problem of time and events ordering in a distributed system and explain and implement the mechanisms of logic clocks to attack this problem and algorithms to synchronize physical clocks in a distributed system.
   Related competences: CTI3.1, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Understand the problem of time and events ordering in a distributed system
   • Explain and implement algorithms to synchronize physical clocks in a distributed system: Cristian (NTP), Berkeley
   • Explain and implement logical clocks mechanisms to attack this problem: happened-before relation, Lamport logical clocks (scalar, vector)
5. Describe, compare and implement algorithms for the coordination of processes in a distributed system, including the coordination necessary to ensure mutual exclusion, leader election, multicast group communication and consensus.
   Related competences: CTI3.1, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Describe, compare, and implement algorithms for the coordination of processes in a distributed system to ensure mutual exclusion: permission-based algorithms (centralized, Lin's, Maekawa's, Ricart & Agrawala's), token-based algorithms (token ring)
   • Describe, compare, and implement algorithms for the coordination of processes in a distributed system for multicast group communication: basic reliable multicast, scalable reliable multicast, ordered multicast (FIFO, causal, total), atomic multicast
   • Describe, compare, and implement algorithms for the coordination of processes in a distributed system for the election of leader: Bully, Ring
6. Understand the application of replication in a distributed system, as well as the consistency problems introduced, and describe the corresponding consistency models and their implementation.
   Related competences: CTI3.1, CT6.4, CTI1.3, CTI3.2, CT5.6,
   Subcompetences:
   • Describe specific implementations of consistency models: primary-based protocols (remote-write, local-write) and replicated-write protocols (active replication, quorum-based protocols)
   • Understand the application of replication in a distributed system, in addition to the consistency problems introduced
   • Describe the data-centric relaxed consistency models: usage of synchronization variables
   • Describe the client-centric consistency models: eventual, monotonic-read, monotonic-write, read-your-writes, writes follow-reads
   • Know the implementation details of consistency models in relation to the replica placement (permanent, initiated by the server, initiated by the client) and the propagation of updates (push-pull protocols)
   • Describe the data-centric strong consistency models: strict, sequential, causal, FIFO
7. Understand and compare basic features of name resolution services for flat, structured and attribute-based names, and implement and evaluate one of these systems.
   Related competences: CTI3.1, CT6.4, CTI1.3, CTI3.2,
   Subcompetences:
   • Implement and evaluate a simple DNS service
   • Know and compare the basic features of name resolution services for flat names: broadcasting, forwarding pointers, home-based solutions, DHTs
   • Know and compare the basic characteristics of name resolution services for structured names: name spaces, iterative resolution, recursive resolution, DNS
   • Know and compare the basic features of name resolution services for attribute-based names: directory services (LDAP)
8. Understand and compare the basic characteristics of distributed filesystems (e.g. NFS).
   Related competences: CTI3.1, CT6.4, CTI1.3, CTI3.2,
   Subcompetences:
   • Understand the semantics of file sharing: UNIX semantics, session semantics, immutable files, transactional semantics
   • Understand and compare the basic features of the NFS distributed file system
   • Understand and compare the basic characteristics of the distributed filesystem Coda
   • Know the architectures of distributed file systems: remote access model, upload / download model, the basic idea of ​​clustered architectures (stripping + replication)
9. Understand and compare the basic characteristics of Web-based distributed systems: web servers, application servers, Web Services, Content Distribution Networks (CDN), and implement and evaluate one of these systems.
   Related competences: CTI3.1, CTI3.4, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Implement and evaluate a simple web server
   • Know the synchronization mechanisms in distributed Web-based systems
   • Know the communication protocols in distributed Web-based systems: HTTP, SOAP, WSDL
   • Know the mechanisms of replication and caching in distributed Web-based systems: Proxies, Content Distribution Networks (CDN): Akamai, redirection schemes (URL Rewriting, DNS redirection)
   • Know the architectures of distributed Web-based systems: client/server, servlets, server clusters, Web Services
   • Know the name services in distributed Web-based systems: URL, DNS, UDDI
10. Understand the Peer-to-Peer (P2P) computing model, compare the characteristics of non-structured P2P systems and structured systems based on DHTs, and implement and evaluate one of these systems.
    Related competences: CTI3.1, CT6.4, CTI1.3, CT5.6,
    Subcompetences:
    • Understand the Peer-to-Peer (P2P) computing model, its advantages, and its applications
    • Compare the characteristics of non-structured centralized P2P systems: BitTorrent
    • Compare the characteristics of structured P2P systems based on DHTs: Chord: organization of the ring, inserting items, searching items with finger tables, inserting nodes
    • Implement and evaluate a structured P2P system
    • Compare the characteristics of non-structured hierarchical P2P systems: FastTrack
    • Compare the characteristics of non-structured decentralized P2P systems with flooding-based search: Gnutella
11. Know the most important distributed computing paradigms (volunteer computing, Grid and Cloud) and their characteristics.
    Related competences: CTI3.1, CT6.4, CTI1.3,
    Subcompetences:
    • Know the Cloud paradigm for distributed computing, its characteristics, and its applications: Utility Computing, type of Clouds (public, private, community, hybrid), differences with Grid computing, Cloud Services (IaaS, PAAS, SaaS), base technologies for implementation, Cloud infrastructure (datacenters), obstacles to the consolidation of the Cloud
    • Know the Grid paradigm for distributed computing, its characteristics and its applications: Virtual Organizations (VO), OGSA architecture, difference from the cluster and distributed computing
    • Know the volunteeer distributed computing paradigm: BOINC
12. Know the paradigms of Mobile and Ubiquitous Computing and their problems.
    Related competences: CTI3.1, CT6.4, CTI3.2,
    Subcompetences:
    • Know the paradigms of Mobile and Ubiquitous Computing and their problems: volatility, association, interoperability, sensors and context-awareness, adaptation
13. Understand articles, assignments, and any source of technical information written in English
    Related competences: G3.1,

Contents

1. Concepts underlying distributed systems
   Definition of a distributed system. Potential applications of a distributed system. Examples of distributed systems. Challenges to design and implement a distributed system: heterogeneity, lack of global view, security, coordination, asynchrony, openness transparency, fault tolerance, scalability. Basic system architectures in distributed systems: centralized (client-server), decentralized (peer-to-peer), hybrid
2. Interprocess communication
   Types of communication in a distributed system: direct vs. indirect (space and time uncoupling), persistent vs. transient, synchronous vs. asynchronous, discrete vs. continuous. Basic communication paradigms in distributed systems: remote procedure call, message passing, message queuing, group communication, publish/subscribe, shared data spaces, shared-memory, mobile code, stream-oriented. Invocation of remote procedures (RPC): basic operation, parameter passing, extensions of the basic model, failure handling, remote method invocation (RMI). Message-oriented communication based on : transient (Sockets) vs. persistent (MOM). Event-based communication: publish/subscribe systems. Stream-based communication: transmission modes, quality of service
3. Time and order
   Time and events ordering in a distributed system. Logical clocks: happened-before relation, Lamport logical clocks (scalar, vector). Algorithms to synchronize physical clocks in a distributed system: Cristian (NTP), Berkeley.
4. Coordination and agreement
   Coordination of processes in a distributed system to ensure mutual exclusion: permission-based algorithms (centralized, Lin's, Maekawa's, Ricart & Agrawala's), token-based algorithms (token ring). Coordination of processes in a distributed system for the election of leader: Bully, Ring. Coordination of processes in a distributed system for multicast group communication: basic reliable multicast, scalable reliable multicast, ordered multicast (FIFO, causal, total), atomic multicast.
5. Consistency and replication
   Replication and consistency in a distributed system. Data-centered strong consistency models: strict, sequential, causal, FIFO. Data-centric relaxed consistency models: usage of synchronization variables. Client-centric consistency models: eventual, monotonic-read, monotonic-write, read-your-writes, writes follow-reads. Replica placement (permanent, initiated by the server, initiated by the client) and propagation of updates (push-pull protocols). Implementations of consistency models: primary-based protocols (remote-write, local-write) and replicated-write protocols (active replication, quorum-based protocols)
6. Naming systems
   Name resolution services for flat names: broadcasting, forwarding pointers, home-based solutions, DHTs. Name resolution services for structured names: name spaces, iterative resolution, recursive resolution, DNS. Name resolution services for attribute-based names: directory services (LDAP)
7. Distributed file systems
   Architectures of distributed file systems: remote access model, upload / download model, the basic idea of ​​clustered architectures (stripping + replication). Semantics of file sharing: UNIX semantics, session semantics, immutable files, transactional semantics. Basic features of the NFS distributed file system. Basic features of the Coda distributed file system
8. Distributed Web-based systems
   Architectures of distributed Web-based systems: client/server, servlets, server clusters, Web Services. Communication protocols in distributed Web-based systems: HTTP, SOAP, WSDL. Name services in distributed Web-based systems: URL, DNS, UDDI. Synchronization mechanisms in distributed Web-based systems. Replication and caching in distributed Web-based systems: Proxies, Content Distribution Networks (CDN): Akamai, redirection schemes (URL Rewriting, DNS redirection)
9. Peer-to-Peer (P2P) systems
   Peer-to-Peer (P2P) computing model, its advantages, and its applications. Non-structured centralized P2P systems: BitTorrent. Non-structured decentralized P2P systems with flooding-based search: Gnutella. Non-structured hierarchical P2P systems: FastTrack. Structured P2P systems based on DHTs: Chord: organization of the ring, inserting items, searching items with finger tables, inserting nodes; Kademlia: organization of the tree and node state, node lookup and join, finding and storing items.
10. Distributed computing systems
    Volunteeer distributed computing paradigm: BOINC. Grid paradigm for distributed computing, its characteristics and its applications: Virtual Organizations (VO), OGSA architecture, difference from the cluster and distributed computing. Cloud paradigm for distributed computing, its characteristics, and its applications: Utility Computing, type of Clouds (public, private, community, hybrid), differences with Grid computing, Cloud Services (IaaS, PAAS, SaaS), base technologies for implementation, Cloud infrastructure (datacenters), obstacles to the consolidation of the Cloud
11. Mobile and ubiquitous systems
    Mobile and ubiquitous systems: volatility, association, interoperability, sensors and context-awareness, adaptation

Activities

Activity Evaluation act

Teaching methodology

Evaluation methodology

Bibliography

Basic:

• Distributed systems - Steen, M. van ; Tanenbaum, A.S, Pearson Educación, 2017. ISBN: 9781543057386
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004112739706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Distributed systems: concepts and design - Coulouris, G.; [et al.], Addison-Wesley/Pearson Education, 2012. ISBN: 9780273760597
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000675069706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Distributed systems: an algorithmic approach - Ghosh, S, Chapman and Hall/CRC, 2014. ISBN: 9781466552982
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001569699706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementary:

• Programming Erlang: software for a concurrent world - Armstrong, J, Pragmatic Bookshelf , 2013. ISBN: 9781937785536
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004002229706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Erlang programming - Cesarini, F.; Thompson, S, O'Reilly , 2009. ISBN: 9780596518189
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003712929706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Slides for SDX Lectures - Guitart, J., , .
  https://mwiki.fib.upc.edu/grau-sdx/
• Seminar Assignments for SDX - Guitart, J., , .
  https://mwiki.fib.upc.edu/grau-sdx/

Previous capacities