Проект "Свободные голосования" http://gplvote.andyhost.ru/forum/ |
|
Метод репликации и подсчета голосов от Юрия :D http://gplvote.andyhost.ru/forum/viewtopic.php?f=5&t=343 |
Страница 4 из 6 |
Автор: | IgorK [ 21 янв 2012, 00:21 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
На самом деле простая логика размышлений приводит и к другому принципу разделения нодов на группы и к немного другому размеру БД. Принцип подсчета голосов в группе и выверки/подписания результатов приведена вами в обсуждении, здесь ее опустим. Цифрами обозначены логические этапы. 1. Все ноды системы разбиваются на группы разного уровня. Каждая нода при этом должна однозначно себя идентифицировать на принадлежность к определенной группе. Более того, для "пересылки" результатов "наверх" должен быть однозначный алгоритм вычисления идентификатора ноды более высокого уровня. Структура БД любой ноды (только результаты голосования), N - кол-во нод в группе: - N записей результов голосования, принятых от групп нижнего уровня; - N записей голосов других нод данной группы ; - агрегированные рез-ты голосования в данной группе - для передачи "наверх". Теперь представим, что на ноде высокого уровня иерархии произошел сбой, фальсификация или другое искажение рез-тов. Очевидно, что такое событие способно значительно исказить результат. Кроме того, если на ноде требуется подвести окончательные (глобальные) результаты голосования, то сделать это сразу не получится. Вывод: при таком подходе ноды неравноценны - не peer. 2. Все ноды однозначно разбиваются на группы одного, нижнего уровня. Логика разбиения позволяет ноде отождествлять себя с иерархическим объединением групп. Структура БД любой ноды: - N записей голосов других нод данной группы ; - N записей агрегированных результатов голосований в групах нижнего (нулевого) уровня; - N записей агрегированных результатов голосований в объединениях групп первого уровня; - ... - N записей агрегированных результатов голосований в объединениях групп последнего (верхнего) уровня. Размер БД голосований теперь можно легко подсчитать. Кроме того, любая нода способна самостоятельно подсчитать результаты голосований - все данные для этого есть (после заполнения БД). 3. Вернемся в реальную жизнь, где принцип агрегирования голосов другой - по месту проживания голосующего. Из этого следует, что на самом деле разбивать голоса на группы следует так, как в п.2, но не по ID ноды, а по месту проживания (или что-то в этом смысле) голосующих. Выводы: 1. при регистрации пользователей системы необходимо присваивать им некий идентификатор, однозначно позволяющий определять их принадлежность к той или иной группе голосующих. По этим группам и по их объединениям в итоге и подводятся результаты голосований; 2. Должна быть некая таблица соответствия идентификатора голосующего и названия группы, к которой он принадлежит; 2. структура БД любой ноды СГ: - N записей голосов других участников данной группы ; - M записей агрегированных результатов голосований в групах голосующих нижнего (нулевого) уровня; - O записей агрегированных результатов голосований в объединениях групп голосующих первого уровня; - ... - Z записей агрегированных результатов голосований в объединениях групп голосующих последнего (верхнего) уровня. Осталось формализовать алгоритмы распостранения и репликации данных. |
Автор: | Dim [ 21 янв 2012, 00:40 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
yurial писал(а): Разбейте голосующих на 2 группы, приведите последовательность действий включающую обмен информацией между группами. В группах нижнего уровня обмен идёт только пакетами с голосами и их синхронизация. Результат подсчётов уже распространяется среди узлов принадлежащих более высокому уровню. (Замечу что нода входит и в родительские группы более высокого уровня.) При этом результат получают как узлы из группы, так и соседние группы. Ноды получившие результат для своей группы от другой ноды при совпадении результата свой результат уже не передают. yurial писал(а): Так же опишите выбор ноды: нужно ли считать или не нужно. Есть ресурсы - считаем. Если долго нет результатов при ограниченных ресурсах, то повышаем приоритет в очереди.Нода не в одном голосовании будет участвовать. Если ресурса хранения не хватает, то не считать. Что логично. Если же есть место, то сложнее. Самое простое считать что в любом случае кроме данной ноды считать некому. Если не занят другим подсчётом, то считать. Если занят то в очередь. Кстати вопрос. Как делить ноды на группы? Не факт, что ноды входящие в субъект будут иметь идентификаторы по которым они не попадут все в одну группу. А кого-то главного у нас нет. |
Автор: | Dim [ 21 янв 2012, 01:02 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
IgorK писал(а): Теперь представим, что на ноде высокого уровня иерархии произошел сбой, фальсификация или другое искажение рез-тов. Очевидно, что такое событие способно значительно исказить результат. Кроме того, если на ноде требуется подвести окончательные (глобальные) результаты голосования, то сделать это сразу не получится. Вывод: при таком подходе ноды неравноценны - не peer. Фальсификации могут быть только на нижнем уровне. Наверху уже просто подсчёты уже зафиксированных данных.В принципе логично при распаде сети остановиться и ждать восстановления. IgorK писал(а): Более того, для "пересылки" результатов "наверх" должен быть однозначный алгоритм вычисления идентификатора ноды более высокого уровня. У нас ноды все одного уровня. Но входят в разные группы. Но любая нода входит в свою группу и в группу более высокого уровня в которую входит её группа. И т.д.Т.о. нода вправе считать что она пуп земли и может заниматься подсчётами в группах на любом уровне в своих группах. Даже в топе. IgorK писал(а): 2. Все ноды однозначно разбиваются на группы одного, нижнего уровня. Логика разбиения позволяет ноде отождествлять себя с иерархическим объединением групп. Вот и Вы вроде о том же?IgorK писал(а): Из этого следует, что на самом деле разбивать голоса на группы следует так, как в п.2, но не по ID ноды, а по месту проживания (или что-то в этом смысле) голосующих. По месту проживания логично для тайных голосований. На месности голоса по вариантам больше распределяются. А то случайно в группу могут попасть участники выбравшие один вариант. И вся тайна псу под хвост. Если же такое на месности произойдёт, то можно применять ядерный скальпель против неугодных. IgorK писал(а): 1. при регистрации пользователей системы необходимо присваивать им некий идентификатор, однозначно позволяющий определять их принадлежность к той или иной группе голосующих. По этим группам и по их объединениям в итоге и подводятся результаты голосований; Входить или нет участнику в субъект устанавливается правилами субъекта и желанием участника. Следовательно мы только присвоить таг. Но вопрос с делением на группы остаётся.
|
Автор: | yurial [ 21 янв 2012, 01:12 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
Dim писал(а): Не факт, что ноды входящие в субъект будут иметь идентификаторы по которым они не попадут все в одну группу. А кого-то главного у нас нет. Пункт 4. Делим группу на подгруппы пока не достигнем нужного количества. В худшем случае получим некую цепочку групп с одной подгруппой, такую цепочку можно будет сократить. Но такое возможно либо при очень маленьком количестве участников, либо искусственно созданная ситуация. Причем нужно постараться, чтобы у ключей совпало много последовательных бит. |
Автор: | IgorK [ 21 янв 2012, 06:54 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
yurial, перечитайте мой пост, плз. Там же вывод на поверхности. Разбиение не нод, а ГОЛОСУЮЩИХ на группы по п.3 (выводы туда же) - это полный аналог существующей сейчас в оффлайне системы голосования и подсчета голосов. Каждый голосующий приписан к УИКу - это группы голосующих нижнего уровня. Следующие уровни - ТИК, ОИК, далее - ЦИК (наверное, уже не уровень - он ведь один всего). Это жесткое деление. Вот оно -техническое решение проблемы "списков избирателей". Для юридически значимых голосований (выборы мэра, например) требуется прописать внятную процедуру применения электронной СГ для ТИКа. Идентификатор голосующего, соответственно, состоит из 3-х обязательных полей, нумерующих УИК, ТИК, ОИК и 4-й части - некий номер собственно голосующего. Он жестко приписан к определенному УИКу. Голосующий поменял место жительства - поменял УИК - изменяется его идентификатор и перед очередным голосованием проходится "процедура регистрации" (выверка списков). Если СГ применяется, например, не для выборов главы чего-либо, то разбиение голосующих на группы и уровни производится по другому принципу. Наверное, можно представить ситуацию, когда разбиваются на группы не голосующие, а ноды системы (приведите пример, если сможете). Так что соглашайтесь и прописывайте (корректируйте, вы их уже сформулировали) алгоритмы подсчета голосов. Деваться Вам, yurial, некуда |
Автор: | Dim [ 21 янв 2012, 09:08 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
yurial писал(а): Пункт 4. Делим группу на подгруппы пока не достигнем нужного количества. И на выходе получаем несбалансированное дерево? Одна группа будет с 7 уровнями. А другая с 3.IgorK писал(а): Деваться Вам, yurial, некуда Поверьте есть. СГ универсальная. А значит территориальное деление будет только у некоторых субъектов.Мы с этого начали. Андрей сейчас это зачищает в серверном варианте. По крайней мере собирался. |
Автор: | IgorK [ 21 янв 2012, 11:01 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
Dim писал(а): IgorK писал(а): Деваться Вам, yurial, некуда Поверьте есть. СГ универсальная. А значит территориальное деление будет только у некоторых субъектов.Мы с этого начали. Андрей сейчас это зачищает в серверном варианте. По крайней мере собирался. Да, система универсальная. Закакзчик опроса/голосования определяет вопросы и принцип (групповой) подсчета голосов. Допустим, его интересует отношения мужщин и женщин к какому-то вопросу. Каждый голосующий в своем ID имеет признак пола. Разбиение голосующих на группы будет идти именно по этому признаку. И подсчет в группах даст ожидаемый заказчиком ответ. Зачем ему нужны при этом результаты голосований на абстактных группах нодов системы? Приведите мне реальный, а не абстактный пример, когда заказчика интересует результаты голосований именно по группам нодов, пожалуйста. |
Автор: | yurial [ 21 янв 2012, 14:46 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
Dim писал(а): yurial писал(а): Пункт 4. Делим группу на подгруппы пока не достигнем нужного количества. И на выходе получаем несбалансированное дерево? Одна группа будет с 7 уровнями. А другая с 3.1) Сбалансированность дерева зависит от распределения бит в ключах. Если вы не будите создавать ситуацию искусственно - получите сбалансированное дерево. 2) Не сбалансированность дерева практически никак не скажется на процедуре подсчета. Зато, для разбиения на группы, нодам не нужно контактировать друг с другом. |
Автор: | IgorK [ 21 янв 2012, 21:33 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
Dim писал(а): СГ универсальная. А значит территориальное деление будет только у некоторых субъектов. Мы с этого начали. Андрей сейчас это зачищает в серверном варианте. По крайней мере собирался. Dim, похоже, я "оспариваю принятые решения" ((с) yurial) Вы с этого начали, вы, очевидно это обсудили в группе разработчиков и отказались от такого подхода. Приведите, пожалуйста, ссылки на принятое решение в текстовом виде и/или на обсуждение(аргументы против) в форуме. А то я пока не в курсе и несу всякую ахинею. Да, и в дискуссии принято отвечать на прямо поставленные вопросы. Пожалуйста, пример реального голосования, когда требуется подведение итогов по группам нод СГ, а не по группам голосующих. p.s. В промежутках между снами додумал структуру БД и метод подсчета голосов. Сегодня-завтра начну по этому поводу новую тему. Welcome, в смысле присоединяйтесь к обсуждению и там. |
Автор: | yurial [ 22 янв 2012, 16:13 ] |
Заголовок сообщения: | Re: Метод репликации и подсчета голосов от Юрия :D |
IgorK писал(а): Да, и в дискуссии принято отвечать на прямо поставленные вопросы. Пожалуйста, пример реального голосования, когда требуется подведение итогов по группам нод СГ, а не по группам голосующих. Например голосование в РГ - там нет никакого территориального деления. А вот тут обсуждение на тему анонимности ключей, раскрытие территориальной принадлежности = персонализация ключа: viewtopic.php?f=3&t=25&p=4332&hilit=%D0%B0%D0%BD%D0%BE%D0%BD%D0%B8%D0%BC%D0%BD%D1%8B%D1%85#p4332 И чем вам, наконец, не нравится предложенный механизм? Все просто и производительно. |
Страница 4 из 6 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |