Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Conditional Statements & Graph Theory

In course

CS-451: Distributed algorithms

Computing is nowadays distributed over several machines, in a local IP-like network, a cloud or a P2P network. Failures are common and computations need to proceed despite partial failures of machines or communication links. This course will study the fo ...

Description

This lecture covers conditional statements, including the converse, contrapositive, and inverse, as well as exercises related to proof by cases and contradiction. It then delves into graph theory, discussing graphs, paths, connectivity, and k-connectivity. The lecture also explores gossip protocols, robustness to failures, random failures, and Erdös-Renyi graphs, highlighting their connectivity properties and applications in distributed systems.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Rachid Guerraoui

Rachid Guerraoui has been affiliated with Ecole des Mines of Paris, the Commissariat à l'Energie Atomique of Saclay, Hewlett Packard Laboratories and the Massachusetts Institute of Technology. He has worked in a variety of aspects of distributed computing, including distributed algorithms and distributed programming languages. He is most well known for his work on (e-)Transactions, epidemic information dissemination and indulgent algorithms. He co-authored a book on Transactional Systems (Hermes) and a book on reliable distributed programming (Springer). He was appointed program chair of ECOOP 1999, ACM Middleware 2001, IEEE SRDS 2002, DISC 2004 and ACM PODC 2010. His publications are available at http://lpdwww.epfl.ch/rachid/papers/generalPublis.html

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (24)

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

Path (graph theory)

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts.

Related lectures (33)

Polynomial Identity Testing

Covers polynomial identity testing using oracles and random point evaluation, with applications in graph theory and algorithmic aspects.

Networked Control Systems: Opportunities

Explores coordination in networked control systems, graph theory, and consensus algorithms.

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Belief Propagation

Explores Belief Propagation in graphical models, factor graphs, spin glass examples, Boltzmann distributions, and graph coloring properties.

Graph Models and Brain Connectomics

Explores graph theory in brain connectomics, MRI applications, network analysis relevance, and individual fingerprinting.