BorisBurkov.net

Overview of consensus algorithms in distributed systems - Paxos, Zab, Raft, PBFT
 October 03, 2021 21 min read

cover

The field of consensus in distributed systems emerged in late 1970s - early 1980s. Understanding of consensus algorithms is required for working with fault-tolerant systems, such as blockchain, various cloud and container environments, distributed file systems and message queues. To me it feels like consensus algorithms is a rather pseudo-scientific and needlessly overcomplicated area of computer science research. There is definitely more fuzz about consensus algorithms than there should be, and many explanations are really lacking the motivation part. In this post I will consider some of the most popular consensus algorithms in the 2020s.

Популярная статья о распределенных вычислительных системах, блокчейне и криптографии в контексте выборов
 September 25, 2021 26 min read

cover

В контексте прошедших выборов многие люди, не являющиеся техническими специалистами, заинтересовались тематикой блокчейна, криптографии и т.п. Меня попросили подготовить популярную статью на эту тему.

Divergence, Gauss-Ostrogradsky theorem and Laplacian
 September 20, 2021 6 min read

cover

Laplacian is an interesting object that initially was invented in multivariate calculus and field theory, but its generalizations arise in multiple areas of applied mathematics, from computer vision to spectral graph theory and from differential geometry to homologies. In this post I am going to explain the intuition behind Laplacian, which requires the introduction of the notion of divergence first. I'll also touch the famous Gauss-Ostrogradsky theorem.

How to configure a private OpenVPN server (+ client)
 September 18, 2021 8 min read

cover

Late September is the time of parliament elections in Russia. 2 weeks prior to the elections Russian government has banned several major VPN providers in order to prevent users from accessing banned opposition websites, through which dissidents coordinate counter-measures against divide-and-conquer tactics, employed by the regime. In this post I'll explain, how to set up a basic OpenVPN server and configure a client to overcome this obstacle.

Johnson-Lindenstrauss lemma
 September 10, 2021 16 min read

cover

Johnson-Lindenstrauss lemma is a super-important result on the intersection of fields of functional analysis and mathematical statistics. When you project a dataset from multidimensional space to a lower-dimensional one, it allows you to estimate, by how much you distort the distances upon projection. In this post I work out its proof and discuss applications.

Intro to spectral graph theory
 September 02, 2021 5 min read

cover

Spectral graph theory is an amazing connection between linear algebra and graph theory, which takes inspiration from multivariate calculus and Riemannian geometry. In particular, it finds applications in machine learning for data clustering and in bioinformatics for finding connected components in graphs, e.g. protein domains.

Singular Value Decomposition
 August 26, 2021 10 min read

cover

Singular value decomposition is a way of understanding a rectangular (i.e. not necessarily square) matrix from the operator norm standpoint. It is complementary perspective to eigenvalue decomposition that finds numerous application in statistics, machine learning, bioinformatics, quantum computers etc. This post explains its nature and connections to operator norm, least squares fitting, PCA, condition numbers, regularization problems etc.

Condition numbers
 August 23, 2021 8 min read

cover

The notion of condition numbers arises when you are studying the problem of numeric stability of solutions of ordinary linear equations systems (OLES). This concept is really important in such practical applications as least-squares fitting in regression problems or search of inverse matrix (which can be an inverse of covariance matrix in such machine learning applications as Gaussian processes). Another example of their use is the time complexity of quantum algorithms for solving OLES - complexity of those algorithms is usually a polynomial or (poly-) logarithmic function of condition numbers. This post gives a brief review of condition numbers.

Normal matrices - unitary/orthogonal vs hermitian/symmetric
 August 13, 2021 9 min read

cover

Both orthogonal and symmetric matrices have orthogonal eigenvectors matrices. If we look at orthogonal matrices from the standpoint of outer products, as they often do in quantum mechanics, it is not immediately obvious, why they are not symmetric. The demon is in complex numbers - for symmetric matrices eigenvalues are real, for orthogonal they are complex.

Kernel methods and Reproducing Kernel Hilbert Space (RKHS)
 August 03, 2021 43 min read

cover

Kernel methods are yet another approach to automatic feature selection/engineering in the machine learning engineer's toolbox. It is based on theoretical results from the field of functional analysis, dating to 1900s and 1950s, called Reproducing Kernel Hilbert Space. Kernel methods, such as kernel SVMs, kernel ridge regressions, gaussian processes, kernel PCA or kernel spectral clustering are very popular in machine learning. In this post I'll try to summarize my readings about this topic, linearizing the pre-requisites into a coherent story.

Roadmap to understanding the quantum mechanics
 July 16, 2021 3 min read

cover

In my university days I used to attend a course of quantum chemistry/mechanics, which was given in a typical post-soviet education style. All formalism, no essentials. As quantum computers are getting closer and closer to the reality by the day, I had a practical reason to finally improve my understanding of the theory. Here is my roadmap to understanding the quantum mechanics.

Wishart, matrix Gamma, Hotelling T-squared, Wilks' Lambda distributions
 July 13, 2021 5 min read

cover

In this post I'll briefly cover the multivariate analogues of gamma-distribution-related univariate statistical distributions.

Principal components analysis
 July 12, 2021 7 min read

cover

Principal components analysis is a ubiquitous method of dimensionality reduction, used in various fields from finance to genomics. In this post I'm going to consider PCA from different standpoints, resulting in various perspectives on it.

Beta distribution and Dirichlet distribution
 July 10, 2021 7 min read

cover

Beta distribution and Dirichlet distribution are Bayesian conjugate priors to Bernoulli/binomial and categorical/multinomial distributions respectively. They are closely related to gamma-function and Gamma-distribution, so I decided to cover them next to other gamma-related distributions.

Multivariate normal distribution
 July 01, 2021 20 min read

cover

Multivariate normal distribution arises in many aspects of mathematical statistics and machine learning. For instance, Cochran's theorem in statistics, PCA and Gaussian processes in ML heavily rely on its properties. Thus, I'll discuss it here in detail.

Cochran's theorem
 June 30, 2021 18 min read

cover

Here I discuss the Cochran's theorem that is used to prove independence of quadratic forms of random variables, such as sample variance and sample mean.

Student's t-distribution, t-test
 June 20, 2021 15 min read

cover

Here I discuss, how to derive Student's t-distribution, an important statistical distribution, used as a basis for t-test.

Snedecor's F distribution and F-test
 June 19, 2021 13 min read

cover

Here I discuss, how to derive F distribution as a random variable, which is a ratio of two independent chi-square disributions. I'll also briefly discuss F-test and ANOVA here.

Pearson's Chi-square tests - intuition and derivation
 June 17, 2021 16 min read

cover

Here I discuss, how an average mathematically inclined person like myself could stumble upon Karl Pearson's chi-squared test (it doesn't seem intuitive at all from the first glance). I demonstrate the intuition behind it and then prove its applicability to multinomial distribution.

Survival analysis - survival function, hazard rate, cumulative hazard rate, hazard ratio, Cox model
 June 11, 2021 8 min read

cover

Here I discuss the statistics apparatus, used in survival analysis and durability modelling.

Data structures for efficient NGS read mapping - suffix tree, suffix array, BWT, FM-index
 June 10, 2021 4 min read

cover

In Next-Generation Sequencing bioinformatics there is a problem of mapping so-called reads - short sequences of ~100 nucleotides - onto a full string that contains them - the reference genome. There is a number of clever optimizations to this process, which I consider in this post.

Gamma, Erlang, Chi-square distributions... all the same beast
 June 09, 2021 21 min read

cover

Probably the most important distribution in the whole field of mathematical statistics is Gamma distribution. Its special cases arise in various branches of mathematics under different names - e.g. Erlang or Chi-square (and Weibull distribution is also strongly related) - but essentially are the same family of distribution, and this post is supposed to provide some intuition about them.

Why Huffman trees require a bottom-up walk to be optimal?
 June 08, 2021 1 min read

cover

Why greedy algorithm wouldn't work for Huffman trees?

A case study of 20PiB Ceph cluster with 100GB/s throughput
 March 15, 2021 14 min read

cover

Recently we deployed a Ceph cluster that might be one of the more powerful in Russia in terms of both throughput and storage capacity. I'd like to discuss nuts and bolts of that system in this post.

Blog version 4
 July 13, 2019 1 min read

cover

I just released a new version of my personal blog http://borisburkov.net, this time powered by Gatsby.js.

Asyncio ecosystem
 March 29, 2019 4 min read

cover

I have a very bad developer experience with Asyncio. It is such a messy and overcomplicated system that I studied it over at least 3 times now. I figured, it's time to cut my losses and write a post about it!

Екатерина Шульман - лекция о российском социуме
 March 15, 2019 3 min read

cover

В сентябре мы с Андреем Попеску, Артемом Ломакиным и Женей Галимовым ели пиццу, лениво разглядывали задачки на Кеггле и трепались о разном. Спустя пару недель я сбросил в наш чатик лекцию Екатерины Шульман о влиянии АИ на социум.

Манчестер - хлопок и паровозы
 February 27, 2019 3 min read

cover

Подобно тому, как между современными инженерами из IBM, Google и Ригетти сейчас развернулась гонка за то, чтобы первыми достичь квантового превосходства, первые инженеры начала 19-ого соревновались в том, кому удастся произвести первый паровоз массового производства, который должен был курсировть между Манчестером и Ливерпулем.

DeepMind - Презентация AlphaFold в EBI
 February 07, 2019 5 min read

cover

Два месяца назад весь мир облетела новость, что DeepMind выиграл известное соревнование по предсказанию 3D-структур белков CASP, порвав всех биоинформатиков с впечатляющим отрывом. Многие люди из мира биотеха теперь пытаются осознать, 'что это было'? Революция или эволюция, наука или инженерия, талант или финансирование? Волею судеб я когда-то оказался совсем недалеко от этой области науки, поэтому потратил несколько дней чтобы разобраться в деталях - а между тем в EBI приехал наводить мосты ведущий инженер проекта Эндрю Сеньор из DeepMind.

Amazon Alexa
 February 07, 2019 4 min read

cover

Послушал двух парней из кембриджского офиса Амазона, работающих над Алексой. Составил общее впечатление о том, каково оно - работать в Амазон.

Prowler.io
 January 22, 2019 1 min read

cover

Побывал на презентации Prowler.io - самого модного кембриджского стартапа.

Focal loss and Average Precision
 November 12, 2018 2 min read

cover

A simple loss function for multiclass classification with multiple classes that beautifully deals with class imbalance

Встреча с Обри де Греем
 November 10, 2018 1 min read

cover

Поглядел наконец живьем на главного геронтологического оптимиста.

Карьера в империи данных - Лекция дата-инженера из Facebook
 October 23, 2018 1 min read

cover

Этой весной на ML/AI-конференции в Microsoft Research я коротко обсудил вопрос построения карьера дата-сайнтиста в IT-компаниях с Зубином Гарамани, профессором сильнейшего инженерного факультета Кембриджа и директором лабораторий искусственного интеллекта в Убер. Зубин тогда объяснил, что от ваших научных регалий обычно зависит та позиция, на которую вы устраиваетесь на работу, и роль в компании. И вот в это воскресенье я получил подтверждение его слов от Марека Романовича, дата инженера в Фейсбуке в Нью-Йорке.

20 примеров - как и на что живут РНК-биоинформатики?
 October 19, 2018 6 min read

cover

Только что прошел мой второй RNAcentral consortium meeting, и это было настолько интересное мероприятие с точки зрения понимания того, как устроен мир, что я не могу не поделиться этой информацией.

Postgres roles
 October 09, 2018 4 min read

cover

Postgres authentication and permission system sometimes feels like a total mess to me. This is a recap of how it works.

Docker users and user namespaces
 October 09, 2018 2 min read

cover

After taking a break from DevOps for a few months and switching to other fields, I would always forget the details of how users within a docker container map to users on the host machine. This is a condensed recap of user mappings that should save me time, upon switching the contexts.

Почему образование в США с 1985 по 2013 подорожало в 6 раз?
 February 02, 2018 8 min read

cover

Это краткий пересказ замечательной главы из книги Кэти О'Нил "Weapons of Math Destruction", посящённой тому, как большие данные углубляют социальное неравенство, концентрируют власть в руках капиталистов и делают обычного человека всё более беспомощным.

Мир МедТеха
 January 23, 2018 6 min read

cover

В конце прошлой недели я был на хакатоне по медицинской технике и получил массу знаний и впечатлений. Это совершенно другой мир, который живёт под девизом "Health & Wealth" и держится на патентах и контактах.

OpenStack, Kubernetes and OpenShift crash course for impatient - Kubernetes
 January 20, 2018 3 min read

cover

Kubernetes is a system for orchestration of containerized applications that can be used to deploy your microservice-based websites to the cloud. Kubernetes is created by Google, based on their internal orchestration system Borg (although, codebase is re-written completely from scratch). Kubernetes is written mostly in Go programming languages and is open-source.

OpenStack, Kubernetes and OpenShift crash course for impatient - OpenStack
 January 19, 2018 2 min read

cover

OpenStack is a pretty old standard for describing cloud resources and interacting with them. Most of its APIs were suggested around 2012. It is "Open" because multiple vendors that provide cloud services (including Rackspace and Red Hat) agreed to use the same API for interaction with them and called it OpenStack.

OpenStack, Kubernetes and OpenShift crash course for impatient - introduction
 January 18, 2018 2 min read

cover

Much like a junkie from a russian anecdote, who started shouting "Jiggers, cops!" when they brought him to the police station, EBI in 2018 suddenly discovered the existence of cloud technologies.

Traction
 December 17, 2017 60 min read

cover

MOST STARTUPS DON'T FAIL BECAUSE THEY CAN'T BUILD THE PRODUCT. MOST STARTUPS FAIL BECAUSE THEY CAN'T GET TRACTION.

BurkovBA.github.io is online!
 December 14, 2017 6 min read

cover

I've been procrastinating over my blog for almost a year. Initially I wrote it in Angular in early 2017 and re-wrote everything in React in the last couple of weeks. At last, following Github's "ship early - ship often" motto, I shipped it today. Probably the most challenging aspect of the whole work was to make Github pages play nice with React SPA - I'll tell you how in this post.

Энигма, часть 5 - "Бисмарк" и "дебютантка"
 November 30, 2017 2 min read

cover

В ходе "Битвы за Атлантику" в 41-ом году немецкий флот пытался отрезать Великобританию от морского сообщения с континентом и Штатами. У немцев было превосходство в военно-морском флоте, и на какое-то время им даже удалось установить вокруг островов морскую блокаду.

Back in Black - Памяти Малькольма Янга
 November 21, 2017 4 min read

cover

В течение последнего месяца умерли двое австралийских музыкантов - братья Джордж и Малькольм Янги. Если смерть Джорджа была мало кем замечена, то про Малькольма Янга сообщали во всех СМИ, ведь он - основатель легендарной австралийской рок-группы AC/DC."

Энигма, часть 1 - Что такое "Энигма"?
 November 01, 2017 2 min read

cover

Что вообще такое эта знаменитая "Энигма", которую все так стремились взломать, и зачем она была нужна?

Энигма, часть 0 - Британия во Второй мировой
 October 25, 2017 1 min read

cover

Прежде чем перейти собственно к теме повествования, криптографии и Блетчли-парк, я хотел сказать пару слов об участии Британии в войне - чтобы дать контекст.

Энигма. Анонс
 October 21, 2017 1 min read

cover

Все смотрели "Игру в Имитацию"? Камбербетч, конечно, прекрасен, а в жизни, конечно, всё было не так. Этот пост про математиков и инженеров из GC&CS (Government Code and Cypher School) во главе с Аланом Тьюрингом, нашедших уязвимости в немецких шифровальных машинах "Энигма" и "Лоренцå" во Вторую мировую войну, и спасших тем самым десятки или даже сотни тысяч соотечественников.

Facebook license
 September 25, 2017 2 min read

cover

Несколько дней назад Facebook изменил лицензии ряда самых популярных своих open-source библиотек React, Flow, Jest и Immutable.js на стандартную MIT.

Congenica
 September 21, 2017 5 min read

cover

Вчера был на семинаре основателей Congenica - компании, занимающейся медицинской генетикой врождённых болезней. Выступали двое из пяти или шести её основателей Ник Ленч и Энди Ричардс, и самое мощное впечатление произвёл Ричардс, с которым я после этого побеседовал.

Babraham Institute
 July 05, 2017 1 min read

cover

Как устроена жизнь простого российского мол. биолога я примерно представляю. Денег нет - денег нет - денег нет - денег нет - да ну нафиг, пойду в Мерк... \n Посмотрел, как она устроена у английского. В каком-то смысле совсем по-другому, в каком-то - точно так же...

Об овцах и стартапщиках
 January 05, 2017 3 min read

cover

Гербом Англии должны быть не три льва, а дюжина овец. Этим кротким созданиям она во-многом обязана своей индустриальной мощью, позволившей ей так вырваться вперед в общественном и экономическом развитии.