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

Метод репликации и подсчета голосов от Юрия :D
http://gplvote.andyhost.ru/forum/viewtopic.php?f=5&t=343		 Страница 5 из 6
Автор:  IgorK [ 22 янв 2012, 17:48 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial, во-первых, принадлежность (вхождение в список избирателей) конкретной УИК - это, конечно, территориальная принадлежность, но не более - не ПД. И от этих списков реально в ближайшие годы никуда не деться. Более того, представьте любое юридически значимое голосование без них - выборы главы муниципалитета, например. Кто будет иметь при этом право голоса?
И, во-вторых, что самое главное, в ближайшее время именно по УИК, ТИК, ОИК будут подводиться итоги. Значит, структуру записей в БД нод и подсчет голосов все равно НЕОБХОДИМО производить по такому принципу. Или Вы предлагаете подводить итоги и так и так. Подумаешь, размеры БД, подумаешь, лишний трафик (не Вашего компа, разумеется) :-)
Вообще-то выбор принципа разбиения на группы - прерогатива заказчика голосования. Система должна предоставить любую возможность в этом смысле. БД голосов, кстати, естественно, для каждого голосования - своя (логически).
Я в новой ветке расписал алгоритм - да, много букафф. Для обычных людей, не крутых прогеров, вроде Вас с Dim, именно так и надо. И желательно, с поясняющими картинками. В алгоритме не хватает "сверок" - вникайте и дописывайте, плз.
Автор:  Dim [ 22 янв 2012, 18:06 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
1) Сбалансированность дерева зависит от распределения бит в ключах. Если вы не будите создавать ситуацию искусственно - получите сбалансированное дерево.
Как интересно можно создать ситуацию искусственно с распределением бит в ключах да ещё в субъекте?
yurial писал(а):
Зато, для разбиения на группы, нодам не нужно контактировать друг с другом.
По идее нодам в субъекте полюбому надо контактировать.
yurial писал(а):
2) Не сбалансированность дерева практически никак не скажется на процедуре подсчета.
В принципе да. Но и размеры групп будут разными. Группы будут делиться не пополам.

У нас для голосования есть список голосовавших. Для деления можно использовать номер голосующего в этом списке.
IgorK писал(а):
Приведите, пожалуйста, ссылки на принятое решение в текстовом виде и/или на обсуждение(аргументы против) в форуме.
Изначально планировались территориальные субъекты. Затем пришли к тому что субъекты могут совсем не касаться территорий. На данный момент территориальность определяется вхождением в соответствующий субъект.
IgorK писал(а):
Пожалуйста, пример реального голосования, когда требуется подведение итогов по группам нод СГ, а не по группам голосующих.
Легко. Голосование по развитию программного продукта.
IgorK писал(а):
И, во-вторых, что самое главное, в ближайшее время именно по УИК, ТИК, ОИК будут подводиться итоги. Значит, структуру записей в БД нод и подсчет голосов все равно НЕОБХОДИМО производить по такому принципу. Или Вы предлагаете подводить итоги и так и так. Подумаешь, размеры БД, подумаешь, лишний трафик (не Вашего компа, разумеется)
Это внешняя информация по отношению к человеку. Как бы вынужденно приписанная ему информация не присущая от рождения. Кроме того может меняться.
Автор:  yurial [ 22 янв 2012, 23:59 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Dim писал(а):
yurial писал(а):
1) Сбалансированность дерева зависит от распределения бит в ключах. Если вы не будите создавать ситуацию искусственно - получите сбалансированное дерево.
Как интересно можно создать ситуацию искусственно с распределением бит в ключах да ещё в субъекте?

Сговор. Договорились с друзьями сгенерить ключи у которых последние биты равны 0. Создали субъект. Вступили в него.
Dim писал(а):
yurial писал(а):
Зато, для разбиения на группы, нодам не нужно контактировать друг с другом.
По идее нодам в субъекте полюбому надо контактировать.

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

Если ключи не будут генерироваться со спец параметрами (см. п1) то будут примерно делиться пополам.
Dim писал(а):
У нас для голосования есть список голосовавших. Для деления можно использовать номер голосующего в этом списке.

Кажется крайне не эффективным методом.
1) У всех этот список должен быть одним и тем же;
2) Он может быть очень большим;
3) Считать сложнее.
Автор:  yurial [ 24 янв 2012, 00:04 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Dim, еще раз подумал над твоим "оптимистичным" алгоритмом. Мне кажется он действительно заслуживает внимания, однако для его надежности необходимо хорошо продумать механизм "кричалки" о том, что результат не сошелся.

ps Принимаем сам механизм разбиения на группы, основанный на битах хеша ключа?
Автор:  Dim [ 24 янв 2012, 00:42 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
Сговор. Договорились с друзьями сгенерить ключи у которых последние биты равны 0. Создали субъект. Вступили в него.
Неясно выразился. Как такую ситуацию может создать коллективный автор системы?
yurial писал(а):
На самом деле можно сделать "контактирование" на этапе вступления в субъект. Вступил в субъект - найди свою группу и запомни их.
Нашёл группу. Участвую в тайном голосовании. Из группы найденной при вступлении в субъект голосую один. Что дальше?
yurial писал(а):
Если ключи не будут генерироваться со спец параметрами (см. п1) то будут примерно делиться пополам.
Это комбинация трёх случайностей. Ключ набор случайных бит. Люди (не)вступают в субъект тоже до некоторой степени случайно. И в конкретном голосовании тоже участвуют случайно.
С какой вероятностью у вас получатся примерно одинаковые по размерам группы?
yurial писал(а):
1) У всех этот список должен быть одним и тем же;
Мы ведь его синхронизируем. Т.е. это одно из условий начала подсчёта.
yurial писал(а):
2) Он может быть очень большим;
Безразлично. Он есть.
yurial писал(а):
3) Считать сложнее.
Зато никаких допусков на случайности.
yurial писал(а):
Мне кажется он действительно заслуживает внимания, однако для его надежности необходимо хорошо продумать механизм "кричалки" о том, что результат не сошелся.
Оригинальный клиент при несовпадении результата отсылает свой результат тем же образом, как и если бы он отсылал единственный результат. Оригинальный же клиент должен при получении двух результатов для одной группы либо остаётся нейтральным, либо пересчитывает результат группы и помечает ложный результат как ложный. Ещё бы наказывать подписавшего ложный результат. Например лишать права голоса в субъекте. А если продолжает настаивать, то выносить на решение внутри системы о блокировании нод принадлежащих нарушителю (или нарушителям). Что логично. Жульничать то он может только модифицированным клиентом.
yurial писал(а):
Принимаем сам механизм разбиения на группы, основанный на битах хеша ключа?
Надо опять таки смотреть на практике. Может я правда пессимист уж очень. Пока пользователей будет немного, то можно посмотреть как их лучше делить на группы. Если группы будут получаться уж очень неравномерными, то "всегда есть варианты".
Автор:  yurial [ 24 янв 2012, 10:41 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Dim писал(а):
yurial писал(а):
Сговор. Договорились с друзьями сгенерить ключи у которых последние биты равны 0. Создали субъект. Вступили в него.
Неясно выразился. Как такую ситуацию может создать коллективный автор системы?

Не понял про коллективного автора. Ключи генерирует сторона клиента и он вправе выбирать каким ключом пользоваться. Он (и его товарищи) могут генерировать ключи до тех пор пока первые 5 бит не будут равны 0. Таким образом искусственно создав ситуацию неравномерного распределения.
Dim писал(а):
yurial писал(а):
На самом деле можно сделать "контактирование" на этапе вступления в субъект. Вступил в субъект - найди свою группу и запомни их.
Нашёл группу. Участвую в тайном голосовании. Из группы найденной при вступлении в субъект голосую один. Что дальше?

А что бы вы сделали с другим алгоритмом? У нас всегда есть вероятность подобной ситуации.
Dim писал(а):
yurial писал(а):
Если ключи не будут генерироваться со спец параметрами (см. п1) то будут примерно делиться пополам.
Это комбинация трёх случайностей. Ключ набор случайных бит. Люди (не)вступают в субъект тоже до некоторой степени случайно. И в конкретном голосовании тоже участвуют случайно.
С какой вероятностью у вас получатся примерно одинаковые по размерам группы?

Предлагаю проверить :)
Автор:  Dim [ 24 янв 2012, 11:24 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
Не понял про коллективного автора.
В ОС проекте сложно сделать закладку позволяющую создавать неравномерные группы. А то что пользователи генерируют ключи чтобы спецом попасть в одну группу это нас не сильно волнует.
yurial писал(а):
А что бы вы сделали с другим алгоритмом? У нас всегда есть вероятность подобной ситуации.
Если голосующие разделяются на группы по списку проголосовавших, то такая ситуация исключается.
Автор:  yurial [ 24 янв 2012, 18:05 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Dim писал(а):
Если голосующие разделяются на группы по списку проголосовавших, то такая ситуация исключается.

Ага, но это увеличит объем траффика.
А так же еще вопрос, как они будут узнавать друг о друге. Т.е. у нас есть 1 000 000 000 нод, 2 из них проголосовали, как они узнают друг о друге?

Можно попробовать пойти другим путем, и наоборот, пытаться объединить группы с маленьким количеством проголосовавших, до того как будут распространены подписка о голосовании.
Автор:  Dim [ 26 янв 2012, 01:56 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
Ага, но это увеличит объем траффика.
Не должно. Список голосовавших нам так и так синхронизировать. Даже не надо синхронизировать порядок. Можно просто отсортировать (по тому же ключу).
yurial писал(а):
Т.е. у нас есть 1 000 000 000 нод, 2 из них проголосовали, как они узнают друг о друге?
Список проголосовавших будет из двух нод.
yurial писал(а):
Можно попробовать пойти другим путем, и наоборот, пытаться объединить группы с маленьким количеством проголосовавших, до того как будут распространены подписка о голосовании.
Т.е. мы сначала разбиваем на группы. А затем по тому же принципу начинаем объединять те группы которые оказались слишком мелкими. Причём это можно повторять снова и снова только отбрасывая большие группы.
Мысль интересная.
Однако не избавляет нас от ситуации когда в такой группе вдруг в голосовании примет участие незначительное количество участников.
Автор:  yurial [ 26 янв 2012, 03:13 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Dim писал(а):
Однако не избавляет нас от ситуации когда в такой группе вдруг в голосовании примет участие незначительное количество участников.

Пакет "подтверждение об участии" отправляется асинхронно с пакетом голоса, и может вообще не отправляться до наличия определенного количества "голосов". В том числе не отправляться до достижения кворума голосования, что сэкономит нам траффик.

Как вариант:
отправлять пакет "подтверждение об участии" по завершению голосования. группы строить исходя из нод принявших явное участие.

На данном этапе мне видится так:
Сначала все участники субъекта разбиваются на группы по N (допустим 1024).
Голосуют.
По окончанию голосования, все в группе знают сколько было "голосов", на основании их количества, при нехватке, начинается объединение с соседними группами. (Причем объединяться можно смело, уменьшая количество используемых для разбиения бит. Дело в том, что при равномерном распределении нод по группам, количество принимающих участие в голосовании, должно быть у всех примерно одинаковым)
После объединения до приемлемого уровня, все начинают рассылать "подтверждение об участии".
Дальше процесс голосования без изменений.
Страница 5 из 6 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/