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

Метод репликации и подсчета голосов от Юрия :D
http://gplvote.andyhost.ru/forum/viewtopic.php?f=5&t=343		 Страница 1 из 6
Автор:  yurial [ 16 янв 2012, 22:20 ]
Заголовок сообщения:  Метод репликации и подсчета голосов от Юрия :D
Репликация:
1) Субъект разбивается на "группы вычислений".
2) Изначально такая группа одна.
3) Размер группы кратен 2;
4) Как только группа достигает численности в 2^limit, она разбивается на 2.
Если быть точнее, количество групп задает Х.
Для определения принадлежности ноды к группе берется X последних бит ключа.
X = up_round( log2(size) ) - limit.
5) Все ноды в группе имеют полное реплицирование.

1) При подсчете голосов, все ноды в группе считают результат, подписывают его.
2) Gередают узлу из соседнего поддерева.
3) Если какой-то подписи не хватает - принимающая сторона сама проверяет результат и подписывает его.
4) Суммируют результат с результатом своей группы, подписывают его.
5) Поднимаются по дереву групп на 1 уровень.
6) while (1 != livel ) goto 2;
Автор:  evorios [ 17 янв 2012, 15:09 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Но, естественно, право выбрать механизм подсчета предоставить юзеру, пускай и глубоко в настройках.
Автор:  yurial [ 17 янв 2012, 17:59 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Скорее сделать дополнительную тычку "проверка результата".
Правда для больших голосований это займет значительное время.
Автор:  Dim [ 17 янв 2012, 22:11 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
1) При подсчете голосов, все ноды в группе считают результат, подписывают его.
Как вариант считают те кто имеет желание и/или ресурсы.
И можно ограничиться только некоторым количеством подписавших. Не обязательно подписывать всем. Если проверить подсчёты можно в любое время, то подписавшие неправильный результат снижают себе репутацию. При наличии двух результатов каждый сможет просто пересчитать по новой и снизить репутацию фальсификатору.
Автор:  yurial [ 18 янв 2012, 00:05 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
В частности я думал сделать следующим образом.
Каждый узел (по возможности) считает результат в группе (это не сложно и в принципе регулируется размером группы)
Результат подписывается ключом.
Участники с четными (не четными) ключами обмениваются результатом.
Участники с не четными (четными) ключами загружают подписи результата и результат с подписями соседней группы.
Считают и подписывают результат более верхнего уровня.
Половина участников с нечетными ключами (имеющими только что посчитанный результат) обмениваются им с второй половиной (которая до этого не участвовала в подписании) и те считают результат более верхнего уровня.

Пример:
Допустим в каждой группе по 1024 участника.
512 участников подписывают результат группы.
Остальные 512 участников этой группы и 512 участников второй группы скачивают его и считают суммарный.
Половина из этих участников (опять же 512) обмениваются результатом с подобным себе множеством из 512 участников.
и т.д.
На каждом из этапов (кроме самых последних), одинаковое количество участвующих в подсчете нод.
В подписании всегда участвуют те ноды, которые до этого в подписании не участвовали.
И всегда остается столько же не участвующих нод.
Таким образом каждая нода (в идеале) участвует в общей проверке результата.

Алгоритм при несовпадении результата, или слишком большой недоступности необходимых участников (меньше некоторого порогового значения) еще пока не формализован. Но что-то в голове крутится.
Автор:  Dim [ 18 янв 2012, 01:33 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Юрий, всё несколько проще.
Подсчётом голосов в группе может заниматься вообще только одна нода. Остальные ноды в группе присланные голоса могут просто коллекционировать. И в итоговый подсчёт результат тоже может отослать только одна нода заверив его. Остальные могут для контроля посчитать. (Так сказать "для себя".) И проверить в итогах какой результат от их группы. Сравнить со своим. При несовпадении (а данные синхронизированы) можно заявить о фальсификации результата. Разбор полётов по большинству. После чего на владельца(ев) неправильного результата в группе вешается ярлык фальсификатора(ов).С заменой результата группы в общем итоге.

Как такой вариант?
Автор:  yurial [ 18 янв 2012, 09:15 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
1 нода может фальсифицировать.
Чтобы это выявить, нужно, чтобы и какая-либо другая нода этот же результат подсчитала.
Для подсчета результата более верхнего уровня соседним группам необходимо обменяться результатом. С кем именно необходимо обмениваться?

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

На самом деле варианты очень схожи, просто мой чуть более детерминирован.
Автор:  Dim [ 18 янв 2012, 13:46 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
1 нода может фальсифицировать.Чтобы это выявить, нужно, чтобы и какая-либо другая нода этот же результат подсчитала.
Считать могут хоть все в группе. Но если отправленный в общий подсчёт результат соответствует самоподсчитанному, то нет смысла заявлять ещё один результат. Другой вопрос если я подсчитал одно, а отправляю другое, то все кто посчитал результат могут заявить о том что я фальсификатор.

Своего рода презумпция доверия. Присланному результату можно доверять если не доказано обратного.
Что резко сокращает объёмы данных.
yurial писал(а):
На самом деле варианты очень схожи, просто мой чуть более детерминирован.
Только в том что для моего варианта надо обеспечить чтобы более одного узла считали результаты. Но это можно как-то заложить в протокол.
Автор:  yurial [ 18 янв 2012, 14:18 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Опишите действия которые должны выполнить участники для подсчета результата уровня +1.
Автор:  Dim [ 18 янв 2012, 14:56 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Обмениваемся голосами.
Синхронизируем результат.
Проверяем их.
После этих этапов данные должны быть идентичны.
Считаем.
Подписываем результат.
В аналогично начинаем обмениваться результатами подсчётов.
В суммарных результатах присланные результаты от группы отбрасываются при равенстве все кроме одного. При неравенстве вычисляем "редиску" по большинству и распространяем всем в группе сообщение о попытке фальсификации. Все кто может и не считал начинают пересчёт.
По окончании синхронизируем промежуточный результат.
Считаем.
Подписываем уже этот результат.
Обмениваемся.
И т.д. пока не будет подсчитан окончательный результат.
Страница 1 из 6 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/