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

Lecture

Chord: Search & Routing

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 Chord algorithm for search and routing in distributed hash tables (DHTs). The instructor explains the concepts of unstructured and structured search, the use of functional APIs, and the implementation of Chord using SHA256 hashes for node IDs and keys.

Instructors (2)

Bryan Alexander Ford

Pierluca Borsò

Official source

Ontological neighbourhood

Computer engineering

Computer security: Public-key cryptography

Related concepts (32)

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Distributed hash table

A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. Keys are unique identifiers which map to particular values, which in turn can be anything from addresses, to documents, to arbitrary data.

SHA-2

SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher. SHA-2 includes significant changes from its predecessor, SHA-1. The SHA-2 family consists of six hash functions with digests (hash values) that are 224, 256, 384 or 512 bits: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256.

HMAC

In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. HMAC can provide authentication using a shared secret instead of using digital signatures with asymmetric cryptography.

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.

Related lectures (40)

Search and Routing Protocols

Explores unstructured and structured search and routing protocols, emphasizing the importance of network structure assumptions and introducing the 'Bubble Storm' algorithm.

Decentralized Systems Engineering: Chord DHT

Covers the Chord DHT in decentralized systems engineering, focusing on reliability, redundancy, and structure maintenance.

Cryptographic Hash Functions

Explores cryptographic hash functions, message authentication codes, and MAC constructions, highlighting SHA1, SHA2, SHA3, HMAC, CBC-MAC, WC-MAC, and P-MAC.

Gossip Efficiency: Decentralized Systems

Explores gossip efficiency in decentralized systems, covering protocols, interaction needs, and bandwidth optimization, along with search algorithms and optimizations.

Cryptographic Hash Functions and Block Chains