Проект "Свободные голосования"
http://gplvote.andyhost.ru/forum/

Алгоритм подсчета голосов и структура записей в БД нод
http://gplvote.andyhost.ru/forum/viewtopic.php?f=23&t=364
Страница 1 из 3

Автор:  IgorK [ 22 янв 2012, 11:01 ]
Заголовок сообщения:  Алгоритм подсчета голосов и структура записей в БД нод

Предлагаю для обсуждения алгоритм подсчета результатов голосований. Из него следует также состав записей в БД, содержащих исходные данные и результаты голосований, а также количество таких записей. Отмечу сразу, что точки "выверки" - сравнении результатов, полученных разными нодами, я опустил. Несколько слов об этом в конце поста.
Как вы правильно подметили, первоначально, на самом нижнем уровне иерархии, все ноды СГ требуется однозначно и фиксировано разделить на группы. Например, по фиксированному ID каждой ноды. И, например, по 1024 ноды в каждой группе.
В каждой ноде группы должны храниться исходные данные голосований на всех других нодах данной группы. Это нужно, в первую очередь (по-моему, и в последнюю), для надежного хранения исходных данных по голосованию во всей системе. В результате количество записей в виде исходных данных в каждой ноде зависит от количества проголосовавших в этой группе нод. Очевидно, что реально это будет от единиц до числа, незначительно превышающего 1024 (размер группы нод).
Дальнейшее разбиение на группы для подсчета результатов голосований в этих группах производится по разным атрибутам голосующих или по ID самих нод (хотя реальную заинтересованность кого-либо в подсчете результатов голосований именно по группам нод системы трудно представить в реальности).
Атрибутом голосующего, однозначно и фиксировано определяющего его принадлежность к той или иной группе, может быть "приписка" его к определенной УИК (книга избирателей), расположенному на территории соответствующей ТИК, далее ОИК. В реальных голосованиях такое разбиение на группы будет чаще всего. В некоторых случаях, в соответствии с запросом заказчика и при наличии у голосующих соответствующих атрибутов, может производиться подсчет голосов по группам, образованным по другим (любым) критериям - пол, возраст, социальное или семейное положение, и т.д.
Далее для сокращения текста будем говорить о голосовании с принципом разбиения голосующих по УИК, ТИК, ОИК и ЦИК в вершине иерархии групп. Алгоритм подсчета при разбиении по группам нод, очевидно, отличается лишь в деталях

Итак, голосование идет или уже завершилось. В группе из 1024 нод, могут быть голоса, принадлежащие различным УИК. Понятно, что ВСЕ голоса в СГ, поданные людьми, приписанными к этой УИК, надо где-то агрегировать для подведения итога по этой УИК. Это надо делать в БД тех нод, где голоса этой УИК появились. Каждая такая нода готовит записи, суммирующие исходные голоса по этим УИК. Каждая из записей гласит: на этой ноде проголосовало такое-то количество людей из такой-то УИК. Количество таких записей не должно превышать количества людей, проголосовавших на этой ноде, и, в пределе, не превышает кол-ва людей, приписанных ко всем УИК, "отметившихся" в данной ноде. В реальности, конечно же, это будут единицы-десятки записей, не больше.
В итоге на ноде мы получили суммирующие записи по каждой УИК, проявившейся в исходных голосах ноды. Но люди, приписанные к этим УИК, могли проголосовать и на других нодах (те, которые проголосовали в этой группе нод, уже учтены – их голоса уже реплицировались в БД ноды). Для того, чтобы каждая нода могла самостоятельно подвести итоги по этим УИК (и просто для подведения итогов), все записи, относящиеся к указанным УИК, должны собираться со всей СГ на нодах, где эти УИК проявились в результате голосования. Причем, что важно, собираться с других нод и храниться в БД этой ноды в исходном виде - в том, в котором приняты. Каждый раз, когда такая новая запись приходит и записывается в БД ноды, на ней производится новый подсчет голосов по соответствующему УИК. Суммирующая запись заменяет предыдущую в БД и представляет из себя частичные данные группы следующего уровня подведения итогов - ТИК.
На уровне ТИК алгоритм полностью повторяется. Суммирующая запись заменяет предыдущую в БД и представляет из себя частичные данные уровня ОИК.
Наконец, суммирующая запись, полученная на уровне ОИК, сохраняется в БД ноды и является текущим результатом голосования по всей системе в целом.
Если подсчет результатов производится во время голосования, то сверка результатов и выявление фальсификаций - дело непростое. Алгоритм сверки необходимо тщательно продумать - из-за динамичности процесса голосования итоги все время меняются. Подведение итогов и сверка результатов после окончания голосования может быть осложнена недоступностью необходимых данных (нод, на которых они считаются). Процесс сверки результатов при закрытых голосованиях тоже заставляет задуматься.
В предложенном алгоритме каждая нода не считает данные по всем группам (УИК). Ведь все исходные данные хранить на всех нодах невозможно. Промежуточные (и окончательные тоже) итоги по всем группам тоже хранить на всех нодах не имеет смысла - ведь это уже результат обработки данных, а не сами исходные данные. Кроме того, очевидно, что предложенный алгоритм кардинально сокращает трафик и размеры БД по сравнению этими (полными) вариантами.

p.s. получился длинный текст. С графическим пояснением было бы значительно нагляднее. Как на форуме разместить рисунок?

Автор:  yurial [ 22 янв 2012, 15:54 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

Как у вас все сложно... (с)

Автор:  Dim [ 22 янв 2012, 18:23 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

На самом деле есть вариант иерархических субъектов голосований. Вселенная - галактика - звезда - планета - континент(океан) - страна - округ - город - район - улица - дом.
В этом случае голосование может касаться любого уровня иерархии и будет складываться из подсчётов более мелких субъектов.

Автор:  yurial [ 23 янв 2012, 00:00 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

Dim писал(а):
На самом деле есть вариант иерархических субъектов голосований. Вселенная - галактика - звезда - планета - континент(океан) - страна - округ - город - район - улица - дом.
В этом случае голосование может касаться любого уровня иерархии и будет складываться из подсчётов более мелких субъектов.

То же самое, что я предлагаю в своем варианте, только не привязываясь к конкретным объектам (субъектам).

Автор:  IgorK [ 23 янв 2012, 09:36 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

Лучше, конечно же обсудить все мысли всех совместно и прийти к единому мнению. Но пока пишем каждый по своему(у вас уже начинает даже немножко получаться писать по-человечески). Но так как я пока все равно не можете :-)
В следующих 1-2 постах я распишу алгоритм с примером записей в БД нод – так нагляднее и понятнее. А пока общие выводы о том, как должен производиться подсчет голосов) в СГ (обратите внимание - мы постепенно сближаемся во мнениях).

1. Принцип разбиения на группы подсчета – по атрибутам нод или голосующих, не важен – алгоритм подсчета и выверки результатов голосований в целом остается неизменным. Подведение итогов в каждой ноде ВСЕГДА производится по группам нод (базовый подсчет). Одновременно возможны другие варианты подсчета – см. п.4.

2. Сбор на каждой ноде ИСХОДНЫХ результатов голосования группы нод фактически есть ТОЛЬКО backup исходных голосов. В алгоритме подсчета итогов голосований на ноде ИСХОДНЫЕ (в исходном виде) данные других нод НЕ УЧАСТВУЮТ. Размер группы нод для backup-репликации, т.е. количество дополнительных записей в БД выбирается только и исключительно исходя из требуемой надежности backup голосов и величины генерируемого при этом (внутригруппового ли?) трафика. Как вариант, backup данные лучше бы вообще хранить в каком-то виде отдельно от БД для подсчета.

3. Каждая нода СГ производит подсчеты каждого уровня агрегации самостоятельно, заверяет и выдает в сеть СГ, при этом сама пользуется заверенными результатами других нод (вопрос выверки данных сейчас не рассматриваем). Результаты подсчета голосов любого уровня иерархии – это агрегация (суммирование) данных предыдущего уровня.

4. В стандартном варианте нода собирает полные данные только самого последнего уровня иерархии групп – для подведения итогов голосования всего субъекта, при этом БД получается весьма компактной. Как сказано в п.1, подведение итогов в каждой ноде всегда производится по группам нод (базовый подсчет). Заказчик при инициации голосования указывает дополнительные (нужные ему) принципы подведения итогов («приписка» голосующего к УИК/ТИК/ОИК/ЦИК или другие - при наличии требуемых атрибутов). В этом случае подсчет голосов на нодах ведется в базовом и других вариантах одновременно (в разных логических БД). Процесс и результаты базового и нужных заказчику подсчетов отображаются в приложении (в WEB) ноды.

5. Результаты голосований на ЛЮБОЙ ноде можно детализировать до любого уровня иерархии. Для этого необходимо обеспечить условия сбора данных – достаточно мощный канал для входящего трафика и необходимый размер дискового пространства для размещения БД голосований. Алгоритм подсчета голосов при этом не изменяется. Собирать более детальные (вплоть до данных голосования на каждой ноде, но не в исходном виде, если требуется) данные будут, возможно, заказчик голосования, штабы кандидатов, избирательные комиссии разного уровня.

6. Интенсивность трафика в СГ в процессе голосования можно (и нужно) регулировать. Подробности сформулирую позже.

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

Автор:  yurial [ 23 янв 2012, 11:00 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

IgorK писал(а):
2. Сбор на каждой ноде ИСХОДНЫХ результатов голосования группы нод фактически есть ТОЛЬКО backup исходных голосов... Размер группы нод для backup-репликации, т.е. количество дополнительных записей в БД выбирается только и исключительно исходя из требуемой надежности backup голосов и величины генерируемого при этом (внутригруппового ли?) трафика.

Не только количество реплик, но и "размазанность" тайного голоса. В группе из 32 человек гораздо проще определить кто как голосовал, нежели в группе из 1024.
IgorK писал(а):
3. Каждая нода СГ производит подсчеты каждого уровня агрегации самостоятельно, заверяет и выдает в сеть СГ, при этом сама пользуется заверенными результатами других нод (вопрос выверки данных сейчас не рассматриваем). Результаты подсчета голосов любого уровня иерархии – это агрегация (суммирование) данных предыдущего уровня.

Тут есть варианты: некоторые ноды могут не располагать ресурсами для подсчета, но в целом верно. Данные агрегируются кем-то и подписываются.
IgorK писал(а):
...Заказчик при инициации голосования указывает дополнительные (нужные ему) принципы подведения итогов («приписка» голосующего к УИК/ТИК/ОИК/ЦИК или другие - при наличии требуемых атрибутов). В этом случае подсчет голосов на нодах ведется в базовом и других вариантах одновременно (в разных логических БД). Процесс и результаты базового и нужных заказчику подсчетов отображаются в приложении (в WEB) ноды.

А вот тут у вас начинается какая-то жесть. Забудьте про УИК/ТИК/ОИК/ЦИК. У нас система голосований, а не выборов.
IgorK писал(а):
...Собирать более детальные (вплоть до данных голосования на каждой ноде, но не в исходном виде, если требуется) данные будут, возможно, заказчик голосования, штабы кандидатов, избирательные комиссии разного уровня.

Только в открытых голосованиях, в тайных - только до уровня группы.
IgorK писал(а):
6. Интенсивность трафика в СГ в процессе голосования можно (и нужно) регулировать. Подробности сформулирую позже.

Сомнительно.
IgorK писал(а):
7. Алгоритм точно подходит для открытого голосования. По-моему, вы намудрили с тайным голосованием, так как уже на первом уровне агрегации хранятся только результаты голосования без привязки к голосующим. Впрочем, подсчет голосов при тайном голосовании подлежит дальнейшему обсуждению и разработке.

Что именно намудрили, и как бы сделали вы?

Автор:  IgorK [ 23 янв 2012, 11:16 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

yurial, я видел Ваш пост, некоторые ответы здесь, остальные, если останутся вопросы, позже. Пока я в следующем посте распишу все-таки БД ноды при выборах президента - по всяким тикам-уикам. Для наглядности.

Примеры БД при разных принципах подсчета голосов.
Backup записи в примерах не отображены – их, возможно, требуется держать в отдельной БД (или не в БД вообще). На каждой ноде в ИСХОДНОМ виде хранятся только голоса проголосовавших на данной ноде, все остальные записи - результаты расчетов на этой ноде, хранятся в БД в агрегированном виде.
Пока писал, пришла идея, что в исходном виде вообще записи в БД нод хранить не нужно, в базе данных – только результаты подведения итогов!!! С учетом этого и продолжу.
Итак, на ноде проголосовало, допустим, два человека, приписанных разным УИК. Предположим, иерархия комиссий такая: УИК, ТИК, ОИК, ЦИК=РФ (на самом деле уровней иерархии больше). Например:
Иванов.УИК_5622.ТИК_654.ОИК_32.РФ
Петров.УИК_5625.ТИК_654.ОИК_32.РФ

Записи БД ноды при БАЗОВОМ подсчете голосов (по группам нод, ноды обозначеры по иерархической принадлежности к группам):

Все строчки, кроме 1.546.345.55, пришли от других нод группы в агрегированном виде (backup отдельно).
0.546.345.55 за 1 против 0
1.546.345.55 за 1 против 1 тут голосовали Иванов и Петров
…..
1023.546.345.55 за 1 против 0

Это был нижний уровень агрегирования голосов. Нода считает за/против, и формирует следующий уровень агрегации, все строчки в котором, за исключением «546» принимает извне:
0.345.55 за … против …
1.345.55 за … против …
…..
546.345.55 за … против … эту строку подсчитала наша нода сама
…..
1023.345.55 за … против …

Следующий уровень агрегации голосов:
0.55 за … против …
1.55 за … против …
…..
345.55 за … против … эту строку подсчитала наша нода сама
…..
1023.55 за … против …

И наконец, самый последний уровень агрегации в этом примере:
0 за … против …
1 за … против …
…..
55 за … против … эту строку подсчитала наша нода сама
…..
1023 за … против …

Суммируя теперь голоса «за» и «против», получим итог голосования по всей СГ одной строкой.

Автор:  IgorK [ 23 янв 2012, 12:27 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

Многа букафф, но асилил. Первый абзац – из предыдущего поста.

На ноде проголосовало, допустим, три человека, приписанных двум разным УИК. Предположим, иерархия комиссий такая: УИК, ТИК, ОИК, ЦИК=РФ (на самом деле уровней иерархии больше). Например:
Иванов.УИК_5622.ТИК_654.ОИК_32.РФ за
Петров.УИК_5625.ТИК_654.ОИК_32.РФ против
Сидоров.УИК_5625.ТИК_654.ОИК_32.РФ против

Записи БД ноды при группировке-подсчете голосов по избирательным комиссиям, к которым приписаны голосующие.

Самый нижний уровень (уровень УИК). Видно, что на этой ноде «отметились» УИК 5622 и 5625. Поэтому нода собирает агрегированные данные других нод по этим двум УИК. В итоге получаем все данные по этим двум УИК:
УИК_5622.ТИК_654.ОИК_32.РФ за … против …
УИК_5622.ТИК_654.ОИК_32.РФ за 1 против 0 (голос Иванова)
УИК_5625.ТИК_654.ОИК_32.РФ за 0 против 2 (голоса Петрова и Сидорова)
…..
УИК_5622.ТИК_654.ОИК_32.РФ за … против …
УИК_5625.ТИК_654.ОИК_32.РФ за … против …
УИК_5625.ТИК_654.ОИК_32.РФ за … против …

Все строчки, кроме тех, где я указал, кто голосовал (только для пояснения), пришли от других нод (не обязательно этой группы нод) в агрегированном виде – без указания голосующих (backup отдельно).
В итоге все (имеющиеся на текущий момент) данные по двум УИК с номерами 5622 и 5625 собраны.

Начинаем собирать данные по проявившемуся ТИК с номером 654. В итоге получаем агрегированные данные уровня ТИК – данные по всем УИК, входящих в ТИК 654, в БД получаем записи:

УИК_5620.ТИК_654.ОИК_32.РФ за … против … (принята извне)
УИК_5621.ТИК_654.ОИК_32.РФ за … против … (принята извне)
УИК_5622.ТИК_654.ОИК_32.РФ за … против … (считала эта нода сама)
УИК_5625.ТИК_654.ОИК_32.РФ за … против … (считала эта нода сама)
УИК_5628.ТИК_654.ОИК_32.РФ за … против … (принята извне)
УИК_5701.ТИК_654.ОИК_32.РФ за … против … (принята извне)


Следующий уровень – ОИК, собираем данные для ОИК 32 со всех ТИК, входящих в нее:
ТИК_1.ОИК_32.РФ за … против … (принята извне)
ТИК_2.ОИК_32.РФ за … против … (принята извне)

ТИК_654.ОИК_32.РФ за … против … (считала эта нода сама)

ТИК_1265.ОИК_32.РФ за … против … (принята извне)

И наконец, самый последний уровень агрегации в этом примере – уровень ЦИК, т.е. РФ (если был всемирный референдум, то будет, соответственно еще один уровень агрегации голосов). На этом уровне собираются данные со всех ОИК:
ОИК_1.РФ за … против … (приняты извне данные по ОИК 1)
ОИК_2.РФ за … против … (принято извне …)

ОИК_32.РФ за … против … (считала эта нода сама для ОИК 32)

ОИК_99.РФ за … против … (принято извне)

Суммируя теперь голоса «за» и «против», получим итог голосования по всей РФ одной строкой.

Автор:  IgorK [ 23 янв 2012, 13:45 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

yurial писал(а):
IgorK писал(а):
3. Каждая нода СГ производит подсчеты каждого уровня агрегации самостоятельно, заверяет и выдает в сеть СГ, при этом сама пользуется заверенными результатами других нод (вопрос выверки данных сейчас не рассматриваем). Результаты подсчета голосов любого уровня иерархии – это агрегация (суммирование) данных предыдущего уровня.

Тут есть варианты: некоторые ноды могут не располагать ресурсами для подсчета, но в целом верно. Данные агрегируются кем-то и подписываются.

Посмотрите следующие мои посты про БД. Агрегировать/суммировать данные любого уровня (если их собрать) сможет любой пк.

yurial писал(а):
А вот тут у вас начинается какая-то жесть. Забудьте про УИК/ТИК/ОИК/ЦИК. У нас система голосований, а не выборов.

Вы, насколько я понимаю, разрабатываете универсальную СГ, годную для голосования(выборов) по любому вопросу и масштабируемую всемирно. Надо ставить реальные цели :-)

yurial писал(а):
IgorK писал(а):
...Собирать более детальные (вплоть до данных голосования на каждой ноде, но не в исходном виде, если требуется) данные будут, возможно, заказчик голосования, штабы кандидатов, избирательные комиссии разного уровня.

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

yurial писал(а):
IgorK писал(а):
6. Интенсивность трафика в СГ в процессе голосования можно (и нужно) регулировать. Подробности сформулирую позже.

Сомнительно.

А чего сомневаться то. Любая нода - это система с обратной связью. На входе - входящий трафик СГ. На выходе агрегированные данные этой ноды. Делаем обратную связь по этому параметру(трафику) отрицательной. Слишком интенсивный входящий трафик - уменьшаем частоту выдачи информации в сеть (например, обобщая данные о кол-ве проголосовавших с точностью до чел.) Было, скажем, 10. Т.е. если при вычислении кол-ва проголосовавших в группе второго уровня иерархии кол-во проголосовавших изменилось на 10, то в сеть выдавались измененные данные. А теперь эта цифра будет, скажем, 20. Таким образом нода будет реже выдавать данные в сеть СГ. Если так сделают все, интенсивность трафика уменьшится.

yurial писал(а):
IgorK писал(а):
7. Алгоритм точно подходит для открытого голосования. По-моему, вы намудрили с тайным голосованием, так как уже на первом уровне агрегации хранятся только результаты голосования без привязки к голосующим. Впрочем, подсчет голосов при тайном голосовании подлежит дальнейшему обсуждению и разработке.

Что именно намудрили, и как бы сделали вы?

Мысли есть - возможно, завтра отпишусь.

Автор:  yurial [ 23 янв 2012, 15:25 ]
Заголовок сообщения:  Re: Алгоритм подсчета голосов и структура записей в БД нод

IgorK писал(а):
А чего сомневаться то. Любая нода - это система с обратной связью. На входе - входящий трафик СГ. На выходе агрегированные данные этой ноды. Делаем обратную связь по этому параметру(трафику) отрицательной. Слишком интенсивный входящий трафик - уменьшаем частоту выдачи информации в сеть (например, обобщая данные о кол-ве проголосовавших с точностью до чел.) Было, скажем, 10. Т.е. если при вычислении кол-ва проголосовавших в группе второго уровня иерархии кол-во проголосовавших изменилось на 10, то в сеть выдавались измененные данные. А теперь эта цифра будет, скажем, 20. Таким образом нода будет реже выдавать данные в сеть СГ. Если так сделают все, интенсивность трафика уменьшится.

Вопрос не в том, "можно или нет", а "зачем"?

Страница 1 из 3 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/