Lecture

Search and Routing Protocols

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-438: Decentralized systems engineering

A decentralized system is one that works when no single party is in charge or fully trusted. This course teaches decentralized systems principles while guiding students through the engineering of their own decentralized system featuring messaging, file sha ...

Description

This lecture covers the concepts of unstructured and structured search and routing protocols, emphasizing the importance of not assuming anything about network structure. The instructor, Bryan Ford, explains how structured protocols can build and maintain a 'map' of information, contrasting with unstructured ones. The lecture delves into the base case algorithm, 'Bubble Storm', which aims to improve search flexibility and efficiency by sending metadata to random nodes. It also discusses the challenges and benefits of different search strategies, such as source routing and random walks, in achieving almost uniform random sampling.

Instructors (2)

Pierluca Borsò

Expertise Teaching & PhD Courses Decentralized systems engineering CS-438 A decentralized system is one that works when no single party is in charge or fully trusted. This course teaches decentralized systems principles while guiding students through the engineering of their own decentralized system featuring messaging, file sharing, encryption, and blockchain concepts.

Bryan Alexander Ford

Links DEDIS lab home pagePersonal home page Curriculum vitae https://bford.info/cv.pdf Teaching & PhD PhD Students Shailesh Mishra Past EPFL PhD Students Eleftherios Kokoris Kogias, Kirill Nikitin, Cristina Basescu, Enis Ceyhun Alp, Simone Colombo, Pasindu Nivanthaka Tennage, Louis-Henri Manuel Jakob Merino Past EPFL PhD Students as codirector David Froelicher, Ludovic Barman, Georgia Fragkouli Courses Decentralized systems engineering CS-438 A decentralized system is one that works when n

Official source

Related concepts (32)

Data (computer science)

In computer science, data (treated as singular, plural, or as a mass noun) is any sequence of one or more symbols; datum is a single symbol of data. Data requires interpretation to become information. Digital data is data that is represented using the binary number system of ones (1) and zeros (0), instead of analog representation. In modern (post-1960) computer systems, all data is digital. Data exists in three states: data at rest, data in transit and data in use. Data within a computer, in most cases, moves as parallel data.

Meta-learning (computer science)

Meta learning is a subfield of machine learning where automatic learning algorithms are applied to metadata about machine learning experiments. As of 2017, the term had not found a standard interpretation, however the main goal is to use such metadata to understand how automatic learning can become flexible in solving learning problems, hence to improve the performance of existing learning algorithms or to learn (induce) the learning algorithm itself, hence the alternative term learning to learn.

Binary search algorithm

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.

Routing

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet. In packet switching networks, routing is the higher-level decision making that directs network packets from their source toward their destination through intermediate network nodes by specific packet forwarding mechanisms.

Routing table

In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with those routes. The routing table contains information about the topology of the network immediately around it. The construction of routing tables is the primary goal of routing protocols. Static routes are entries that are fixed, rather than resulting from routing protocols and network topology discovery procedures.

Related lectures (64)

Chord: Search & Routing

Covers the Chord algorithm for search and routing in distributed hash tables.

Graph Algorithms II: Traversal and Paths

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

SCION: Next-Generation Internet Security

Presents SCION, a highly secure and efficient next-generation internet architecture with a focus on security and efficiency.

IP Addressing and Routing: Basics and Examples

Explains IP addressing, routing, and TCP packet meta-data, along with practical routing table considerations.

Quantum and Nanocomputing

Covers quantum wire analysis, transmission function, and tunneling in dots.