Lecture

Decentralized Systems Engineering: Chord DHT

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 courses (2)

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 ...

CS-234: Technologies for democratic society

This course will offer students a broad but hands-on introduction to technologies of human self-organization. ...

Description

This lecture covers the fundamentals of decentralized systems engineering, focusing on the Chord Distributed Hash Table (DHT). It discusses the structure of Chord DHT, the hashing process, API operations, object storage, and the challenges related to reliability, redundancy, and maintaining structure in decentralized systems.

Instructors (3)

Verónica del Carmen Estrada Galiñanes

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)

Universal hashing

In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient.

Consistent hashing

In computer science, consistent hashing is a special kind of hashing technique such that when a hash table is resized, only keys need to be remapped on average where is the number of keys and is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is defined by a modular operation. The term "consistent hashing" was introduced by David Karger et al.

Random-access memory

Random-access memory (RAM; ræm) is a form of computer memory that can be read and changed in any order, typically used to store working data and machine code. A random-access memory device allows data items to be read or written in almost the same amount of time irrespective of the physical location of data inside the memory, in contrast with other direct-access data storage media (such as hard disks, CD-RWs, DVD-RWs and the older magnetic tapes and drum memory), where the time required to read and write data items varies significantly depending on their physical locations on the recording medium, due to mechanical limitations such as media rotation speeds and arm movement.

Hash collision

In computer science, a hash collision or hash clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Although hash algorithms have been created with the intent of being collision resistant, they can still sometimes map different data to the same hash (by virtue of the pigeonhole principle). Malicious users can take advantage of this to mimic, access, or alter data.

Cuckoo hashing

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as brood parasitism; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.

Related lectures (64)

Ad-Hoc Networks: Routing and DHTs

Explores peer-to-peer networks, ad-hoc routing, and distributed hash tables.

Hashing and Sorting Techniques in Database Systems

Provides an overview of hashing and sorting techniques in database management systems, focusing on their implementation and performance optimization.

Hashing and Sorting

Covers hashing, sorting, extendible hashing, linear hashing, and external sorting.

Hash Tables Analysis

Covers the analysis of hash tables, including search operations and expected collisions.

Pairwise Independence: Hashing and Load Balancing

Explores pairwise independence in hashing to avoid collisions and achieve load balancing.