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

Метод репликации и подсчета голосов от Юрия :D
http://gplvote.andyhost.ru/forum/viewtopic.php?f=5&t=343		 Страница 2 из 6
Автор:  yurial [ 18 янв 2012, 15:34 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Dim писал(а):
Синхронизируем результат.

Вы имеете ввиду синхронизация самих голосов? - ок
Dim писал(а):
Проверяем их.

Голоса? - ок
Dim писал(а):
Подписываем результат.

т.е. сначала считаем, а потом подписываем? - ок
Dim писал(а):
В аналогично начинаем обмениваться результатами подсчётов.

Достаточно обменяться подписями результата.
Dim писал(а):
В суммарных результатах присланные результаты от группы отбрасываются при равенстве все кроме одного. При неравенстве вычисляем "редиску" по большинству и распространяем всем в группе сообщение о попытке фальсификации. Все кто может и не считал начинают пересчёт.

До этого места у нас одинаково, кроме того, что у меня жестко указывается кто должен считать и сколько.
Dim писал(а):
По окончании синхронизируем промежуточный результат.
Считаем.
Подписываем уже этот результат.
Обмениваемся.
И т.д. пока не будет подсчитан окончательный результат.

А вот это я уже не понял. Где у нас обмен между группами подсчета?
Автор:  Dim [ 18 янв 2012, 16:16 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
Достаточно обменяться подписями результата.
Не достаточно. Результаты подсчёта знают только в группе, а тут обмен внутри группы в которую входит эта группа.
140 000 000
140 х 1 000 000
1 000 000
1000 х 1000
yurial писал(а):
А вот это я уже не понял. Где у нас обмен между группами подсчета?
Там где как Вы считаете достаточно обменяться подписями результата.
Автор:  yurial [ 18 янв 2012, 18:12 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Ок, тогда все еще хуже.
Вот в группе подсчитались данные.
Как группы между собой обмениваются данными? У вас по 1024 ноды в каждой группе, ип и паблик ключи вы знаете.
Автор:  Андрей [ 18 янв 2012, 18:24 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
В идеале, если не разбиваться на группы, все участики субъекта должны подписать результаты голосования.

По логике вещей, дальше эти посубъектные результаты должны рассылаться всем и у каждого должен формироваться и подписываться общий результат.
Автор:  yurial [ 18 янв 2012, 18:33 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Андрей писал(а):
В идеале, если не разбиваться на группы, все участики субъекта должны подписать результаты голосования.

Не реально.
Андрей писал(а):
По логике вещей, дальше эти посубъектные результаты должны рассылаться всем и у каждого должен формироваться и подписываться общий результат.

Тем не менее быстро посчитать все нельзя.
Автор:  Dim [ 18 янв 2012, 19:17 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
Как группы между собой обмениваются данными?
Ровно также как и в группе. Только в пакете данные не по одному голосу, а по группе.
yurial писал(а):
Не реально.
В больших субъектах нереально.
yurial писал(а):
Тем не менее быстро посчитать все нельзя.
Этот вариант быстрее просто потому что подсчёты в группах идут параллельно над небольшим объёмом данных. А затем суммируются уже результаты.
И мы в результате не тянем за собой необходимость подписывать результат всеми. Достаточно ограниченного количества подписей. Причём мне кажется даже одной.
Автор:  yurial [ 18 янв 2012, 22:59 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Dim писал(а):
yurial писал(а):
Как группы между собой обмениваются данными?
Ровно также как и в группе. Только в пакете данные не по одному голосу, а по группе.

У вас есть 1024 ноды в одной шруппе и 1024 ноды в другой, все начинают стучаться к друг-другу генерируя много траффика.
Для подсчета результата более высокого уровня будет обмен между группами по 2048 нод, и так далее.

В моем же алгоритме, количество нод которые "должны" считать - неизменно. Они же и подписывают результат. Поэтому считаю свой вариант алгоритма более продуманным, хотя и далеким от совершенства.
Dim писал(а):
И мы в результате не тянем за собой необходимость подписывать результат всеми. Достаточно ограниченного количества подписей. Причём мне кажется даже одной.

Одной мало, я б такому результату не поверил, а вот подписей в половину группы подсчета (т.е. 50% посчитали одинаково) думаю достаточно и не сильно накладно.

Есть аргументы против предложенного мной алгоритма?
Автор:  Dim [ 20 янв 2012, 01:00 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Объясняю на кисках.
Открытое голосование. (При закрытом тоже самое, но для простоты открытое.)

Два варианта.
Андрей 1
yurial 2
Сергей 2
Dim 1
IgorK 1
Андрей на мега-копе и мгновенном канале посчитал быстрее всех. За 1 вариант 3 голоса, за 2 - 2 голоса. Подписал результат и начал рассылку результата. Сергей посчитал вторым и получил тот же результат, но ему уже пришёл подсчёт Андрея. Он запомнив для себя что согласен с результатом подсчётов далее рассылает результат подписанный Андреем. У Dim ситуация та же посчитал - согласен. Но у нас два товарисча которые не считали вообще: yurial и IgorK. Им пришёл результат подписанный Андреем. Но мы помним что они голосовали за разные варианты. IgorK результаты устраивают и он не возражает. yurial оказавшийся в меньшинстве имеет на выбор два варианта. Первый. Увидев что возражений нет согласиться с результатом подписанным Андреем, но запомнив что не проверял его. Второй. Взять голоса и пересчитать. Получив тот же результат что и Андрей.Тем самым оказавшись в ситуации Сергея: результат не устраивает но посчитано правильно. Остаётся ему только согласиться.

Как мне кажется оказывается достаточно одной подписи.
Автор:  Dim [ 20 янв 2012, 01:13 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
yurial писал(а):
Есть аргументы против предложенного мной алгоритма?
Только количество хранимых данных. Мы уже храним первичные данные с подписями. И к ним добавляются подписи результатов.

Причём, то что нужно хранить подписи только половины проголосовавших погоды не делает. В моём варианте количество сохраняемых подписей уменьшается на 3 порядка.

Можно проверить оба и посмотреть во что обходятся они на практике.
Автор:  yurial [ 20 янв 2012, 09:40 ]
Заголовок сообщения:  Re: Метод репликации и подсчета голосов от Юрия :D
Если группа 1024 ноды, то хранить надо по 512 подписей на "уровень".
8 млрд = 23 уровня. Подпись 512б (вообще, конечно же зависит от ключа, для для примера пусть будет эта константа)
Итого: 23 * 512 *512 = 6мб.

6мб для голосования с 8 млрд. нод.
Для маленьких голосований и количество нод в группе будет меньше (если не требуется сверх надежность) и количество уровней.
Страница 2 из 6 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/