![stream rate art](https://habrastorage.org/webt/ko/ay/op/koayopm8caby70zokumllg3xzyk.jpeg)
Измерение интенсивности потоков в представлении художника.
В одной из наших предыдущих публикаций мы рассказывали о способе измерения интенсивности потока событий при помощи счетчика на основе экспоненциального распада. Оказывается, идея такого счетчика имеет интересное обобщение, о котором в этой публикации расскажут сотрудники компании Qrator Labs Артем Шворин и Дмитрий Камальдинов.
План погружения у нас следующий. Для начала рассмотрим и проанализируем несколько примеров того, как вообще считают события и оценивают интенсивность потока. Дальнейший шаг — увидеть обобщение, а именно — некоторый класс счетчиков, который мы называем u-моделью. После мы исследуем, какими полезными свойствами обладают u-модели, и предлагаем методику построения адекватной оценки интенсивности.
1 Какие бывают счетчики
Без ограничения общности можно считать, что счетчик событий описывается своим состоянием
Состояние не обязательно выражается числом, но из соображений практической реализуемости можно считать, что оно представляется конечным набором битов.
В некоторых случаях события являются взвешенными, и при обновлении состояния требуется учитывать вес события
Но для начала будем рассматривать простые невзвешенные события, а учет веса добавим потом, когда понадобится. Это будет совсем не сложно.
В этой статье мы ограничимся рассмотрением только детерминированных счетчиков, то есть таких, для которых правило обновления задается функцией
Также должна быть возможность, зная состояние счетчика, оценить интенсивность потока. Вообще говоря, понятие интенсивности потока нетривиально, и позже мы его обсудим подробнее. Пока же будем просто считать, что к модели счетчика прилагается некоторая номинальная оценка в виде функции
1.1 Линейные счетчики: подсчет всех событий
Самое простое, что можно придумать, — простой подсчет количества событий, произошедших с момента запуска. То есть по приходе события делаем вот так:
Будем называть такие счетчики линейными.
Оценка представляет собой среднюю интенсивность за всю историю:
Некоторую проблему может составлять то, что счетчик может переполниться. Также есть вопросы к тому, как задать оценку — очень старые события оказывают такое же влияние на оценку, как и недавние.
1.1.1 Подсчет событий в скользящем окне
Для устранения вышеописанных недостатков линейных счетчиков можно подсчитывать количество событий не с сотворения мира, а только тех, что произошли не более чем
Наивная реализация предполагает запоминать все события в окне, что требует
К сожалению, и эта разновидность линейных счетчиков для наших целей не подходит: снижение точности еще можно потерпеть, а
1.2 EDecay: экспоненциальный распад
Идея распадных счетчиков навеяна известной концепцией радиоактивного распада [4]. Ее суть состоит в том, что с течением времени количество нераспавшегося вещества уменьшается со временем по экспоненциальному закону:
где
Удобней переписать это выражение в таком виде:
заменив параметр. Более подробно о параметризации моделей счетчиков см. раздел A приложения.
На основе этого механизма можно построить счетчик событий, как было описано в нашей статье [1].
Будем по определению считать, что каждому типу события соответствует величина, имеющая физический смысл «количества вещества» и зависящая от времени, которая при наступлении события скачком увеличивается на единицу, а в остальное время уменьшается по приведенному выше экспоненциальному закону.
То есть, чтобы учесть новое событие, пришедшее в момент времени
где
Чтобы этим можно было пользоваться, нужно придумать, как хранить счетчик в памяти. Самый простой способ представления состояния счетчика — пара чисел
В статье [1] мы детально разбираем такие счетчики. Важной идеей, которую здесь уместно упомянуть, является более экономичное предстваление состояние счетчика в виде одного числа
Величинане хранится явно в памяти, но может быть вычислена в любой момент. Хранится же значение
, такое что в момент времени
величина
выражается следующим образом:
Не вдаваясь в подробности, скажем лишь, что при таком подходе правило обновления и оценка принимают вид:
1.3 QDecay: более быстрый распад
При рассмотрении модели экспоненциального распада можно заметить, что функция распада (в данном случае экспонента) удовлетворяет дифференциальному уравнению:
На самом деле, с физической точки зрения, скорее, наоборот — именно это уравнение описывает радиоактивный распад, а экспонента — его решение.
Действительно, смысл уравнения состоит в том, что скорость распада пропорциональна количеству имеющегося вещества. В какой-то момент нам захотелось, чтобы распад в модели происходил побыстрее, для этого мы попробовали взять не линейную, а квадратичную зависимость (quadratic decay, QDecay):
Решение — новая функция распада:
и она действительно стала покруче.
На самом деле…
Вряд ли корректно говорить, что гипербола круче экспоненты. Но распад больших значений теперь и правда происходит быстрее (а малых — медленнее).
Аналогично рассмотренной ранее модели (с экспоненциальным распадом), здесь можно представить состояние счетчика в виде одного числа
Здесь замечательно то, что вычисление функции обновления обходится дешево — оно требует только элементарных арифметических операций, причем деление только одно. То есть изначально мы хотели всего лишь более быструю лошадь (распад), а получили новое полезное качество (меньше вычислений).
Можно пойти дальше, взяв бо́льшую степень в уравнении на функцию распада:
1.4 SW: усреднение межпакетных интервалов
Рассмотрим еще один подход к построению счетчиков, а именно — усреднение. В данном случае будем усреднять интервал времени между соседними событиями. Мы называем эту величину межпакетным интервалом, поскольку имеем дело с сетевым трафиком, где в качестве события выступает приход сетевого пакета, а слово «межсобытийный» как-то не прижилось.
Вообще говоря, смысл этого подхода заключается в том, что у нас есть последовательность значений некоторой величины (в данном случае межпакетных интевалов), которая слишком быстро меняется, чтобы ее можно было использовать непосредственно, и хочется эту последовательность каким-то образом сгладить или усреднить.
Определение усреднения
Пусть есть некоторая последовательность
, тогда ее среднее на
-м шаге определяется так:
То есть здесь получается среднее арифметическое последних
членов последовательности.
Это определение можно обобщить. Взвешенным средним последовательности
называется сумма
где
— некоторые весовые коэффициенты, такие что
.
То есть здесь получается среднее арифметическое последних
Это определение можно обобщить. Взвешенным средним последовательности
где
Напомним, что чем новее события, тем интереснее нам их вклад в оценку интенсивности. Поэтому вместо обычного усреднения естественно использовать взвешенное, давая больший вес недавним событиям. Выбирать веса можно по-разному, сейчас попробуем взять веса в виде членов геометрической прогрессии. Такой способ суммирования называется экспоненциальным скользящим средним (EMA).
Определение EMA-усреднения
Экспоненциальное скользящее среднее последовательности
определяется следующим образом:
где
— параметр,
.
Поскольку событий очень много, то есть
велико, можно считать, что в далеком прошлом были какие-то фиктивные события
,
, вклад которых берется с пренебрежимо малыми весами
. Тогда удобней переписать определение так:
поскольку в этом случае
.
Одним из важных преимуществ EMA по сравнению с другими способами усреднения является возможность свернуть громоздкую сумму в рекурсивное выражение:
Таким образом, при вычислениях не требуется хранить множество старых значений
. Кстати, именно эту формулу часто берут в качестве опредения EMA [2].
где
Поскольку событий очень много, то есть
поскольку в этом случае
Одним из важных преимуществ EMA по сравнению с другими способами усреднения является возможность свернуть громоздкую сумму в рекурсивное выражение:
Таким образом, при вычислениях не требуется хранить множество старых значений
Применяя формулу экспоненциального усреднения к межпакетным интервалам, получим:
где
Эта модель еще раз упоминается в разделе 4.3, где, в частности, показано, как выразить состояние счетчика одним числом и упростить вычисления. Пока же просто выпишем результат.
Обновление счетчика по приходе события в момент времени
В качестве оценки интенсивности берется обратная величина усредненного значения межпакетного интервала:
Замечание
При помощи EMA-усреднения можно получить модель, в точности совпадающую с распадной моделью из раздела 1.2. Для этого надо усреднять не межпакетные интервалы, а величину
, которую можно было бы назвать мгновенной интенсивностью:
1.5 Вероятностные счетчики
Идея вероятностных счетчиков — менять состояние счетчика по приходе события не всегда, а с некоторой вероятностью. Эту вероятность можно задавать по-разному, например
- держать ее постоянной (биномиальные счетчики);
- уменьшать в 2 раза после каждого успешного обновления (счетчики Морриса);
- менять после каждых
успешных обновлений.
Вероятностные счетчики позволяют очень эффективно использовать память. Например, оригинальные 8-битные счетчики Морриса можно использовать для учета до
2 U-модель: идея
Если посмотреть на счетчики, основанные на идее распада, то можно заметить такую особенность: состояние описывается парой чисел
Временно забудем тот факт, что на практике значение счетчика должно быть дискретно и описываться сравнительно небольшим количеством бит, и, оставаясь в рамках вакуумной сфероиппологии, положим, что и значение счетчика, и время прихода событий являются вещественными числами, а также преобразования над ними будут, соответственно, вещественнозначными. Потом (см. раздел 3.3) научимся дискретизировать модели, делая их пригодными на практике.
2.1 Инвариант распада
Рассмотрим участок кривой распада (см. рис. 1a). Пусть в момент времени
![decay curves](https://habrastorage.org/webt/g5/1l/go/g51lgoqqpwxztjv7aeg18mqe5ro.png)
Вообще говоря, у нас не одна распадная кривая, а целое семейство
Посмотрим теперь, как должно происходит обновление такого счетчика. Пусть
тогда именно это значение
Замечание
Если нужно учитывать взвешенные события, то изменение происходит не на единицу, а на вес события:
.
Пока не очень понятно, как находить индекс нужной кривой, но совсем скоро это прояснится.
2.2 Трансляционная симметрия
На рис. 1b распадные кривые
Математически это можно свойство записать так:
то есть кривая
Вообще кривые можно занумеровать как попало, нужно лишь уметь находить индекс новой кривой при операции обновления. Но удобнее всё же нумеровать по порядку, так чтобы индекс
Замечание
Здесь введено обозначение
, которое удобно тем, что функция
монотонно возрастает. Это потом пригодится в разделе 2.4 при определении интенсивности.
Теперь правило обновления по приходе события в момент времени
Таким образом, правило обновления представляется в виде
где
Это правило выглядит настолько просто и универсально, что его можно взять в качестве определения. Именно так мы будем определять u-модель.
Замечание
Если распадная функция задается дифференциальным уравнением вида
то для нее всегда легко находится инвариант, который обладает свойством (6).
Действительно, решение дифференциального уравнения можно записать в виде
Тогда в качестве инварианта можно взять
, а соответствующая кривая выражается как
.
то для нее всегда легко находится инвариант, который обладает свойством (6).
Действительно, решение дифференциального уравнения можно записать в виде
Тогда в качестве инварианта можно взять
В разделе 3.1 перечислены формальные свойства, которым должна удовлетворять функция
2.3 Абсолютное и относительное
Можно сказать, что
Тот факт, что функция обновления работает с относительным значением счетчика, отражает принцип распада: если события не происходят, то абсолютное значение
2.4 Оценка интенсивности
Для распадной модели значение
Сохраняя не букву (из формулы (6)), но дух идеи распда, будем строить оценку интенсивности как функцию от одного аргумента, а именно — от относительного значения счетчика:
Получается, что подход u-модели состоит в реализации следующего плана (да, выглядит несколько по-панковски).
- Берем какие-нибудь модели, построенные из «физических соображений», и для каждой из них выражаем правило обновления через u-функцию.
- Затем абстрагируемся от физического смысла, оставляя только голую u-функцию. Теперь можно, не заботясь о смысле, смело менять u-функцию, например, выбирая более вычислительно дешевую.
- Наконец, придумываем, как заново внести смысл — построить адекватную оценку интенсивности.
- PROFIT!
Для того, чтобы этот план стал возможным — загвоздка, очевидно, только в пункте 3, — потребуется наложить какие-то ограничения на u-функцию, и сейчас попробуем выяснить, какие именно. Эти мотивационные рассуждения, однако, можно пропустить и сразу перейти к определению ограничений (9) на u-функцию.
2.4.1 Равномерный поток
Наша компания занимаемся изучением трафика в сети, и мы можем считать приход сетевых пакетов штуками — это будет поток, интенсивность которого измеряется в пакетах в секунду (pps, packets per second). А можем учитывать размер пакетов, тогда размер выступает в качестве веса события, соответственно, интенсивность такого взвешенного потока будет измеряться в битах в секунду (bps, bits per second). Бывает также важным различать пакеты по их содержимому (IP-адреса источника и/или получателя, номера портов, протокол и т.п.), тогда мы группируем события по типам и для каждого типа заводим отдельные счетчики.
Поскольку мы здесь занимаемся оценкой интенсивности потока событий, нужно вначале формализовать понятия события и потока событий.
Определение (событие). Событием назовем тройку, где
— время прихода события,
— вес события,
— тип события, некоторый идентификатор потока.
Определение (поток событий). Поток событий определяется как последовательность событий,
. Причем события в потоке должны быть упорядочены по времени:
при
.
В большинстве реализаций систем учета событий время считается дискретной величиной:
Если нас интересуют только события как таковые, например, мы измеряем количество пакетов штуками в секунду, то вес
Определение (равномерный поток). Детерминированный равномерный потокопределяется следующим образом:
где— параметр потока — период между событиями. Тогда интенсивность такого потока, по определению, выражается как
.
Теперь можно выразить способ измерения интенсивности потока для любой модели. Пусть на счетчик набегает поток некоторой известной интенсивности
Хочется, чтобы интенсивность потока
2.4.2 Аттрактор
Изучая на конкретных примерах поведение u-модели под воздействием детерминированного потока, мы обнаружили, что (по крайней мере для этих примеров) существует понятие аттрактора, который не вполне формально описывается следующими свойствами.
- Для каждого значения интенсивности входящего потока
существует аттрактор — такое подмножество относительных значений счетчика, что если какое-то значение
оказалось в этом аттракторе, то все последующие значения
для
туда тоже попадут. Аттрактор представляет собой отрезок
(возможно, вырожденный, когда оба его конца слиплись).
- Имеет место сходимость — даже если относительное значение счетчика было вне аттрактора, по прошествии нескольких обновлений оно туда попадет или хотя бы подойдет сколь угодно близко к аттрактору.
- Имеет место монотонность — положение аттрактора монотонно зависит от интенсивности набегающего потока. То есть оба конца отрезка
и
являются монотонно возрастающими функциями.
Поскольку нам нужно по значению счетчика судить об интенсивности потока, требуется решить обратную задачу. Это возможно в силу монотонности и непрерывности — существуют функции
Разумеется, для того чтобы эти свойства были практически полезными, нужно, чтобы, во-первых, отрезок-аттрактор был коротким, иначе точность будет низкой, во-вторых, чтобы сходимость была быстрой, иначе придется долго ждать, прежде чем счетчик начнет показывать адекватное значение. В любом случае для конкретной u-модели можно записать решение в явном виде и оценить точность и скорость сходимости.
Теперь попробуем перейти от частного к общему. Зададимся вопросом: какие условия нужно наложить на u-функцию, чтобы у соответствующей u-модели появился аттрактор с указанными выше свойствами? Исчерпывающий ответ изложен в следующем разделе.
3 U-модель: реализация
3.1 Определение u-модели
Пусть функция
где
Определение (u-модель). Рассмотрим способ обновления счетчика, построенный на основе функции, обладающей свойствами (9), при котором обновление счетчика
по приходе события в момент времени
выражается правилом (8):
Такой способ обновления счетчика назовем u-моделью обновления.
Функция
3.2 Измерение интенсивности
Свойств (9) оказывается достаточно, чтобы обеспечить существование аттрактора и построить верхнюю
3.2.1 Строгая u-модель
Можно заметить, что условия (9) не запрещают случай, когда приращение функции обновления обращается в ноль в некоторой точке, то есть когда
Несложно доказать, что если взять
Определение (строгая u-модель). Если в дополнение к свойствам (9) функциии
являются строго монотонными на
, то соответствующую u-модель обновления назовем строгой.
Теорема (теорема о неподвижной точке). Для строгой u-модели при воздействии детерминированного равномерного потока интенсивностипоследовательность значений
является константной, если выполнено дополнительное условие: функция
является сжимающим отображением, то есть
, такое что
.
Идея доказательства заключается в применении теоремы Банаха [5], которая гарантирует существование и единственность неподвижной точки у сжимающего отображения. Тогда все члены последовательности
Получается, что у строгой u-модели аттрактор состоит из одной точки.
На самом деле не для всех u-моделей, которые мы используем, функция обновления является сжимающим отображением, например, у модели EDecay функция обновления «почти» сжимающа — для нее константа
Например, имеет место следующее утверждение. Если в некоторый момент времени счетчик находился в таком состоянии, что его относительное значение было равно
3.2.2 Общий случай — нестрогая модель
Что касается дискретизованных моделей (см. раздел 3.3), то они теряют строгую монотонность, поэтому вместо теоремы о неподвижной точке помогает набор утверждений (не приводим их здесь), которые требуют более слабых условий и дают более слабые, хотя всё еще полезные для оценки интенсивности, результаты. Для нестрогой модели вместо взаимно однозначного соответствия между интенсивностью потока и относительным значением счетчика имеет место интервальная оценка. То есть аттрактор представляет собой невырожденный отрезок.
Пользуясь предложенной методикой, для заданной u-модели остается лишь построить верхнюю
3.3 Дискретизация
Для того, чтобы u-моделью можно было пользоваться на практике, ее необходимо дискретизировать. То есть сделать так, чтобы множество состояний счетчика стало конечным, причем, желательно, небольшим по размеру. Почему небольшим? Нам нужно держать в памяти миллиарды счетчиков, чем их больше, тем выше будет качество предоставляемого сервиса. В самом деле, зачем тратить 64 бита на счетчик, когда можно обойтись 16-ю?
Замечание
Можно пойти на хитрость, усложнив представление состояния, представив его в виде пары
, где
относится к конкретному счетчику, а
— общая часть состояния целой группы счетчиков. Мы дейстительно пользуемся этим приемом, в частности, для борьбы с переполнением счетчиков, но в данной работе его не рассматриваем.
Один из очевидных способов дискретизации — из континуума относительных значений счетчика выбрать конечное подмножество идущих подряд целых чисел и немного модифицировать u-функцию, так чтобы она стала целочисленной.
Для начала построим функцию
- она имеет целые значения в целых точках:
для
,
- в некотором смысле близка к
:
для
,
- удовлетворяет условиям (9).
По-видимому, эту задачу можно решить разными способами. Ниже приведен один конкретный способ построения
Основная идея этого построения состоит в том, чтобы задать значения
Удобней сначала строить
где
Остается лишь определить саму функцию
Утверждение. Построенная таким образом функцияудовлетворяет условиям (9) и, таким образом, определяет u-модель.
Замечание. Вообще говоря, u-модель при такой операции (переход от
Возникает закономерный вопрос: зачем доопределять
Замечание
Кажется, здесь должна быть какая-то метатеорема, утверждающая, что, независимо от способа построения
в промежуточных точках, методика построения оценок дает одинаковый результат.
Теперь у нас есть функция
Как выбирать границы интервала
В качестве
следует взять такое число, чтобы
,
. (В силу условия (9d) такое число существует.) Тогда результат обновления никогда не вылезет за правую границу: для
имеем
. Что касается левой границы, то ее можно выбирать произвольно (годится любое
). Действительно, в силу неотрицательности
для
будет выполнено
, то есть результат обновления не вылезет за левую границу. Таким образом,
можно выбирать из соображений размера счетчика — чем больше разрядность счетчика, тем левее можно подвинуть левую границу, и тем точнее будет оценка малоинтенсивных потоков.
Именно эту функцию
В разделе B приложения в качестве примера показана дискретизация модели EDecay.
4 Примеры u-моделей
Счетчики, введенные в разделе 1 (кроме линейных), представляются в виде u-модели, поскольку для них правило обновления выражается в виде
Здесь мы рассмотрим их еще раз, теперь уже в соответствии с новой методикой: вначале задается u-функция, потом строятся оценочные функции.
Рисунки 2,3,4 иллюстируют свойства моделей: оттенками желтого показаны графики функций
4.1 EDecay
![EDecay](https://habrastorage.org/webt/lj/cg/q5/ljcgq59o5nanh0mjzzeddgh-1nk.png)
Правило обновления (1) выглядит так:
где
У этой модели есть интересная особенность — для нее существует оценочная функция
где
4.2 QDecay
Соответствующая правилу (2) функция обновления выглядит так:
![QDecay](https://habrastorage.org/webt/-8/gx/jr/-8gxjrqykulebloejuwgofmx8oy.png)
4.3 SW
Правило обновления (4) эквивалентно выражается в рамках u-модели через функцию обновления
Полезным свойством этой модели является вычислительная простота функции обновления, можно прямо эту формулу записать в код безо всяких табличных приближений.
![SW](https://habrastorage.org/webt/c-/mo/5c/c-mo5cg4ru7mr5sodigxwl3gu1s.png)
4.4 Сводная таблица
В таблице 1 указаны характеристики перечисленных моделей.
![summary table](https://habrastorage.org/webt/ux/8k/vv/ux8kvvgaxg9vkxmmz-ctub6mbbe.png)
Можно заметить, что у некоторых моделей формула нижней оценки
Помимо строгих оценок интенсивности
Заключение
На нескольких примерах были показаны общие принципы построения счетчиков событий. В качестве довольно универсального обобщения предложена схема u-модели. Предложена методика построения оценок интенсивности для любых u-моделей.
Кроме того, за кадром осталось много интересного.
- Вероятностные счетчики. Что будет, если в правиле обновления u-модели заменить функцию
на случайную величину, зависящую от относительного значения счетчика?
- Представление и обслуживание больших массивов одинаковых счетчиков. Функции обновления и оценки зависят от относительного значения счетчика
, где
и
могут находиться в сравнительно узком диапазоне значений, в то время как
пробегает широкий (потенциально бесконечный) диапазон. Как сделать, чтобы счетчики не переполнялись?
- Алгоритмы выделения тяжелых потоков. Отдельные счетчики позволяют измерять интенсивность потоков, но как их организовать, чтобы выявлять наиболее интенсивные потоки?
Приложение
A Параметризация
Все модели счетчиков, рассматриваемые в данной статье, являются однопараметрическими. Но мы в разных местах используем в качестве параметра разные величины, чтобы формулы выглядели удобней. Ниже следует перечень величин, каждая из которых может быть равноценно использована в качестве параметра модели, с указанием их физического смысла и взаимосвязей между ними.
— так называемая постоянная распада из закона радиоактивного распада [4]
,
— величина, характеризующая среднее время жизни в той же модели. Также верно, что за время
количество распадающегося вещества уменьшается в
раз, а период полураспада выражается через
следующим образом:
.
,
.
— параметр сглаживания в EMA [2]
Модель экспоненциального распада может быть выражена двояко: через радиоактивный распад и через EMA-сглаживание. При этом имеет место связь между параметрами:.
B Пример дискретизации EDecay
Модель EDecay определяется следующей функций обновления:
Рассмотрим на рис. 5, как меняется функция обновления при дискретизации.
![interpolated EDecay](https://habrastorage.org/webt/s-/tp/t7/s-tpt7pw0memx371oizdvfiswzo.png)
- Есть идеальная вещественнозначная функция обновления, которая в точности
задает модель экспоненциального распада (гладкая зеленая линия на графике). - Для практического применения ее приходится дискретизировать. Можно использовать представление с плавающей точкой (это, очевидно, тоже дискретизация, только не равномерная), а можно взять целочисленное. В данном случае применяется округление вниз, хотя это не принципиально (синяя линия).
- Наконец, можно еще сильнее загрубить функцию обновления. В [1] для ускорения вычислений предлагалось вместо вычисления вещественнозначной функции с логарифмами и экспонентами использовать табличный подход. При этом предполагалось, что размер таблицы будет невелик, если используется малоразрядный счетчик. Однако ничто не мешает проредить таблицу, сократив ее размер еще в несколько раз, и реализовать линейную интерполяцию. Полученная функция обновления будет немного отличаться (красная пунктирная линия на графике).
Разумеется, в результате дискретизации функция обновления искажается, что само по себе не является проблемой, но приходится это учитывать при построении оценки интенсивности. Кроме того, неизбежно теряется строгая монотонность модели, вследствие чего снижается точность оценки. Степень искажения зависит от параметра
Ссылки
[1] Наша статья про распадную модель: https://habr.com/ru/company/qrator/blog/334354
[2] Экспоненциально взвешенное скользящее среднее: https://ru.wikipedia.org/wiki/Скользящая_средняя#Экспоненциально_взвешенное_скользящее_среднее
[3] Взвешенные скользящие средние: https://ru.wikipedia.org/wiki/Скользящая_средняя#Взвешенные_скользящие_средние
[4] Закон радиоактивного распада: https://ru.wikipedia.org/wiki/Закон_радиоактивного_распада
[5] Теорема Банаха о неподвижной точке: https://ru.wikipedia.org/wiki/Теорема_Банаха_о_неподвижной_точке
[6] Ayur Datar et al. — Maintaining Stream Statistics Over Sliding Windows — Society for Industrial and Applied Mathematics, Vol. 31, No. 6: http://www-cs-students.stanford.edu/~datar/papers/sicomp_streams.pdf
[7] Наша статья про счетчики Морриса: https://habr.com/ru/company/qrator/blog/559818/
[8] Трансляционная симметрия: https://ru.wikipedia.org/wiki/Трансляционная_симметрия