Module COMP4227: Distributed Network Computing and Algorithms

Department: Computer Science

COMP4227: Distributed Network Computing and Algorithms

Prerequisites

• COMP2181 Theory Of Computation

Corequisites

• None

Excluded Combination of Modules

• None

Aims

• To introduce students to network based distributed computing paradigms and algorithm design concepts.
• To equip students with the ability to design and analyse efficient distributed algorithms and data structures.

Content

• Network abstracted as a graph.
• Distributed computing models and analysis: LOCAL, CONGEST . . .
• Fundamental and classic distributed algorithms: Flooding, Leader Election, etc.
• Centralised to distributed via classic graph problems: Maximal Independent Set (MIS), Colouring, Matching, Minimum Spanning Tree (MST), etc.
• (Advanced) Topics from the following:
• (Secure) Computation despite faults: Fault-tolerant distributed com¬putation despite attacks and/or edge/node insertions/deletions.
• Byzantine fault-tolerance: Foundations of Blockchain/Cryptocurrency.
• Autonomous systems: Self-stabilization, Self-healing, Mobile robots.
• Algorithm complexity and general design techniques: Network Decomposition and Graph Shattering.

Learning Outcomes

• On completion of the module, students will be able to demonstrate:
• An understanding of computing, abstraction, and algorithms for networks and decentralised systems;
• An understanding of formal concepts for designing and analysing distributed algorithms;
• An understanding of fundamental distributed algorithms and distributed variants of classic graph problems;
• An understanding of advanced distributed concepts such as fault-tolerant algorithms.

• On completion of the module, students will be able to demonstrate:
• An ability to abstract real-world problems and network architectures to provide solutions by specific distributed algorithms;
• Appreciating real world constraints and an ability to reason about decentralised and distributed systems;
• An ability to design distributed solutions (algorithms) and analyse accordingly.

• On completion of the module, students will be able to demonstrate:
• An ability to abstract problems to devise computational solutions;
• An ability to reason about multi-agent, decentralised and distributed systems and networks;
• A scientific approach to algorithm and system design.

Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module

• Lectures enable the students to learn new material relevant to distributed systems, distributed computing and distributed algorithms in various scenarios.
• Summative assessments assess the understanding of distributed systems, distributed computing, distributed algorithms, and the ability to design and analyse such algorithms.

Teaching Methods and Learning Hours

Summative Assessment

Formative Assessment:

Example exercises are given during the course. Simulating a distributed algorithm in class/lab.

■ Attendance at all activities marked with this symbol will be monitored. Students who fail to attend these activities, or to complete the summative or formative assessment specified above, will be subject to the procedures defined in the University's General Regulation V, and may be required to leave the University