P2Pジャンケン解いてみた

p2p logic

P2Pジャンケンは分解すると、以下の3つのフェーズに切れます。

  1. ジャンケングループの形成
  2. ジャンケン
  3. 勝敗の確認

1.では、ジャンケンをするメンバを集めて、確定します。きっかけを作る人をジャンケンリーダと呼ぶことにします。ジャンケンメンバを集める方法は不問とします。メンバの確定ですが、これは、paxos（分散合意アルゴリズム）を使うことでできます。ジャンケンリーダがpaxosにおけるリーダとして機能します。

2.で、実際にジャンケンをしますが、開始のかけ声は誰がかけてもよく、かけ声の合意をpaxosで行います。かけ声の合意のあと、メンバはそれぞれジャンケンの手を決めます。ジャンケンの手は決定後、逆算されないようノイズとなるデータを足してhash値を計算し、そのhash値とノイズデータのhash値の2つをメンバと共有します。その後、手が出そろったことをpaxosを使って合意します。

3.で勝敗の確認をします。このときに実際の手とノイズデータをメンバ内で共有します。手を変えていないことはすでに共有しているhash値で確認できます。


以上、まとめると次のようになります。

  1. ジャンケングループの形成
    • ジャンケンの発議（発議者がジャンケンリーダとなる）
    • ジャンケンメンバを募集（方法は不問）
    • ジャンケンメンバの確定（ジャンケンリーダをリーダとするpaxosアルゴリズムを使用）
  2. ジャンケン
    • ジャンケンのかけ声（paxosで合意）
    • 手を決める（手＋ノイズデータのhash値とノイズデータのhash値をグループ内に同報）
    • 手の出揃ったことを確認（paxosで合意）
  3. 勝敗の確認
    • 実際の手を公開（手とノイズデータをグループ内に同報）
    • 勝敗を確認（hash値を使って手が改竄されていないことを確認）
    • 勝ちが決まらない場合はやり直す。複数メンバが勝ちの場合は、ジャンケンリーダを再選して、1.のメンバの確定から行う。引き分けの時は、2.から行う。

P.S.

  • paxosを使うとメンバの過半数が生きている限り大丈夫なのですが、ここでは、ジャンケンメンバはジャンケン中に突然死や離脱しないことを前提にしています。
  • リーダを決めているのは、マルチpaxosじゃない通常のpaxosでリーダが必要になるためですが、選出方法はそう厳格でなくても構いません。
  • 合意をpaxosで行っていますが、全体を最適化したもっとシンプルなプロトコルがあるかもしれません。
  • hash関数を使って手の改竄を防止していますが、本人確認も含めて電子署名を使うとより強くなります。
  • Twitter実装には落としきれてません。orz
    • -

その後、effyたんより、グーチョキパーのhashじゃ元データがばれるとコメントもらいました。元データにノイズを足す記述を追加しました。
さらに、ノイズのhash値を取る案もeffyたんよりもらいました。（09/09/23 14:15）

P2Pジャンケン

p2p logic

丸山先生が面白いことをtweetしています。

  • ジャンケンって、掛け声って大事ですね。同期が取れないと、「あとだしジャンケン」になるから。二台のコンピュータが、ネット上でジャンケンをするプログラムって、意外と難しそう。誰か考えて、管理サーバなしの、P2Pジャンケン・プロトコル。
  • ジャンケンって、同時性（あとだしなし）、明証性（皆の手が皆にわかる）、非決定性（引き分けあり）、拡張性（何人でもできる）とか、いろいろ特徴がありますね。意外と、非決定性や拡張性が、実装難しいのかも。
  • 先のジャンケンの特徴づけですが、「対称性（皆が同じルールに従う）」もいれたほうがいいかも。
  • 問題を変えましょう。Twitterでジャンケンもどき出来ます？　RTや@やDを使って。


話の中で、Tomoさんのblog（P2Pとマジックプロトコル）も引用されたけど、今回は無理みたい。

  • @nati 拝見しました。ただこれだと、Aが出題してBが答えて、Bの正解・不正解が決まる。A,Bの役割は、対称的ではないですね。Bが負けても、Aが勝ったとはいえないような気がします。あと、3人以上のジャンケンには拡張できないですね。


effyたんによれば、NECの佐古さん（参照：グループ署名の研究）が解いたとのこと。

これって、暗号化技術も絡んでそうで深そうです。

    • -

その後ですが、effyたんのこのつぶやきを参考に解いてみました。

  • ジャンケンには同時性は必要なくて、当初は出した手が互いにわからないこと、出した手が変えられないことと、そして全員が出し終わった後に手を検証できること、を満たせばいい。


こちら（某氏のつぶやき）もいけてます。(^^;;

  • @kibayos 世界で一番簡單なコンピュータ相手のジャンケンプログラム。 1/3 の確率で、勝ち、負け、引分、を表示する。プレイヤーからの入力は必要としない。

構造化オーバレイの一貫性保証

Skip Graph overlay slide

Skip Graphの耐障害性に取り組んでいるところです。
Skip Graphに限らず構造化オーバレイの可用性を高めるためには、ネットワーク上に分散している構造化オーバレイの持つ構造についてなんらかの一貫性管理をする必要があります。構造化オーバレイは不安定なピアを含むP2P環境で動作しないといけない前提があるため、分散構造の一貫性保証は簡単ではありません。
5月に開かれた 3rd Sensor & Overlay Workshop では、クラウドコンピューティングで取り上げられる BASE（Basically Available, Soft-State and Eventual Consistency）をキーワードにこの問題が議論されました。その時の資料の改訂版をここに掲載します。（細かなSkip Graphのアルゴリズムの記述をカットして、unbreakable 構造化オーバレイを追記しました）
尚、クラウドコンピューティングでは、複製も含めネットワーク上に分散するデータの一貫性管理が問題となりますが、ここでは、オーバレイの経路表に対象を絞っています。先はまだまだ長いって感じです。
後半の技術トピックには関連性の高い技術を列記しています。lock free synchronization は、SMPやCPUのマルチコアアーキテクチャにおいて性能を発揮する技術ですが、通信部分をバスからネットワークに拡張した際、同様のアプローチが分散構造の一貫性管理に適用できるだろうと考えています。一方、unbreakableは強い弾力性を持つ、よりsoft state寄りのアプローチになります。問題は一貫性が出るまで待ち時間を要するところにあります。これら2つのアプローチを組み合わせることでシステム全体の可用性が高まるものと考えています。


ところで、"unbreakable" は正式な技術用語ではありません。ご想像の通り、映画 "Unbreakable" から命名しています。(^^;;


ソサイエティ大会にて講演

workshop p2p slide

9/15、新潟で開かれたソサイエティ大会のチュートリアルセッションで、P2P関連の講演をしてきました。
今回は、Skip GraphもPIAXも登場しません。(^^;;　純粋にP2P技術がインターネットの未来と我々の社会にどう寄与するかについて述べてみました。P2Pについてブラックとかグレーとか言っている場合じゃありません。もっと人材も含め、研究資源を投入しないと...

スライド*1の方、掲載します。チュートリアルセッションの模様は、いつもお世話になっている首藤さんのページで確認できます。多岐に及んだ講演で楽しかったですよ。


*1:本スライドは、2009年 電子情報通信学会ソサイエティ大会 チュートリアルセッションBT-2の講演において使用したものです。

時間の計り方

tech

昨日のP2PSIP勉強会で、時間計測の誤差について話題になってました。実装の変化で関数の精度も変わってきてますので、自分の頭の整理も兼ねてちょっとまとめてみました。

経過時間の計測

何も知らずに Linux*1で、timeコマンドもしくは times関数を使うと精度はtick（4msから10ms*2）に制限されてしまいます。WindowsでGetTickTimeを使っても同様です。これは、Javaで System.currentTimeMillis() を使う場合も同様でした。

ミリ秒以下の精度を求める場合は、以下がお薦めです。

  • Linux, Mac OS X
    • gettimeofday()
    • clock_gettime()
      • システムクロックの分解能で紀元からの経過時間を取得できます。
      • 分解能については、clock_getres()を使って取得します。（単位はナノ秒）でも、この返り値はあてにならないことが多いようです。
  • Java
    • System.nanoTime()
      • 利用可能でもっとも正確なシステム時間をナノ秒単位で取得できます。
      • 精度については、OS依存（実装依存）です。


ここで、Javaの nanoTime() の精度が気になるのですが、OpenJDK6 のソースで確認してみました。

これの1343行目以降に定義されています。

  • MONOTONIC_CLOCK をサポートしておれば、clock_gettime() を使う。
  • そうでなければ、gettimeofday() を使う。

となってますので、少なくともマイクロ秒の精度で時間を計測できることが分かります。

指定時間の sleep

Linuxで普通にsleep()関数を使うと、秒単位の精度しかでません。少なくともtick精度を出すために、昔の人間（私も..）は select関数を使っていました。
そんな中、仕様上はマイクロ秒単位、ナノ秒単位で待機可能な usleep(), nanosleep() が登場するのですが、でもやってみると tick精度しか出ないという話になっていました。

Javaの場合も同様で、Java5になるまでは Thread.sleep() の精度はtickでした。


ですが、これも状況が変わって、Mac OS Xや最近のUbuntuでは、usleep(), nanosleep()で数マイクロ秒の精度が出ることが確認されています。



ここに、参考3 で自分が実験した際にYasuさんに作ってもらったグラフを掲載します。

  • 環境
    • CPU: C7（1.0GHz）…できるだけ非力なマシンを選んだ。
      • 以前話題になったARTiGOです。
    • Ubuntu-8.4, linux 2.6.24-19
  • 計測した関数
    • usleep(), nanosleep()
    • select()
    • Java5のThread.sleep()

横軸は指定した待機時間（単位：マイクロ秒）で縦軸は経過時間（単位：マイクロ秒）。ただし、usleep, nanosleep は 100 回ループさせた経過時間で、select と Java sleep は 10 回ループの経過時間です。（なのでグラフの縦位置が一目盛りずれてます）
精度については、下の表のようになりました。Java5のsleepがtick(4ms)ではなく1msの精度になっている点が興味深いところです。

関数 精度
usleep(), nanosleep() 5usec
select() 4msec
Java5のThread.sleep() 1msec

サンプルコード

上で紹介した計測では、gettimeofday関数とJavaのSystem.nanoTime を使っています。ここで紹介した関数、メソッドの使用例として、その時用いたコードを載せておきます。


usleep, nanosleep, selectの計測コード（C）

/*
 * usleep.c
 *
 *     Created: Aug 7, 2008
 *      Author: kibayos
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>

static long base_sec;

void set_base_sec() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    base_sec = tv.tv_sec;
}

long lap_usec() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return (tv.tv_sec - base_sec) * 1000000 + tv.tv_usec;
}

long cal_m_sleep(int n, int times) {
    long stime = lap_usec();
    int i;
    for (i = 0; i < times; i++)
        usleep(n);
    return lap_usec() - stime;
}

/* use this func for testing nanosleep()
long cal_m_sleep(int n, int times) {
    struct timespec ts;
    ts.tv_sec = n / 1000000000L;
    ts.tv_nsec = (n * 1000L) % 1000000000L;

    long stime = lap_usec();
    int i;
    for (i = 0; i < times; i++) {
        nanosleep(&ts, NULL);
    }
    return lap_usec() - stime;
}
*/

/* use this func for testing select()
long cal_m_sleep(long n, int times) {
    struct timeval tv;

    long stime = lap_usec();
    int i;
    for (i = 0; i < times; i++) {
        tv.tv_sec = n / 1000000L;
        tv.tv_usec = n % 1000000L;
        select(0, NULL, NULL, NULL, &tv);
    }
    return lap_usec() - stime;
}
*/

long av_m_sleep(int n, int times) {
    long lap = 0;
    int i;
    for (i = 0; i < 5; i++)
        lap += cal_m_sleep(n, times);
    return lap / 5;
}

void printlap(int n) {
    long av = av_m_sleep(n, 100);
    usleep(10000);
    printf("lap time (%5d): %7ld,%7ld\n", n, av, av / n);
}

int main(int argc, char **argv) {
    set_base_sec();

    printf("** lap time of 100 times usleep(n)\n");
    printf("**  - total usec and (total / n) usec\n");
    printlap(1);
    printlap(2);
    printlap(3);
    printlap(5);
    printlap(10);
    printlap(20);
    printlap(30);
    printlap(50);
    printlap(100);

    return 0;
}


Java5 Thread.sleepの計測コード（Java）

/**
 * @author kibayos
 */
public class CalNanoTime {
    static long callSleeps(int n_usec, int times) {
        int msec = n_usec / 1000;
        int nsec = (n_usec * 1000) % 1000000;
        long stime = System.nanoTime();
        for (int i = 0; i < times; i++) {
            try {
                Thread.sleep(msec, nsec);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return (System.nanoTime() - stime) / 1000;
    }
    
    static long avaragedCallSleeps(int n_usec, int times) {
        long lap = 0;
        for (int i = 0; i < 5; i++) {
            lap += callSleeps(n_usec, times);
        }
        return lap / 5;
    }
    
    static void printlap(int n_usec) {
        long av = avaragedCallSleeps(n_usec, 10);
        System.out.printf("lap time (%6d): %7d,%7d%n",
                 n_usec, av, av / n_usec);
    }
    
    public static void main(String[] args) {
    	System.out.printf("** lap time of 10 times Java sleep(n)%n");
    	System.out.printf("**  - total usec and (total / n) usec%n");
    	printlap(1);
    	printlap(10);
    	printlap(20);
    	printlap(50);
    	printlap(100);
    	printlap(200);
    	printlap(500);
    	printlap(800);
    	printlap(1000);
    }
}

*1:こちらの話は、ほとんどのUNIX系のOSで成り立ちます。Linuxと書いているのは、実装の違いを確認しやすいのとユーザが多いことを意識しています。

*2:タイマ割り込み周期のことで、カーネルビルト時に CONFIG_HZを変更することで独自に設定可能です。カーネル2.6では 4ms（CONFIG_HZ=250）に設定されています。

kvsに穴が生じる確率

数学パズル p2p

お題

kumofsの古橋さんからいただいたお題を紹介します。

n台のマシン（物理ノード）から構成される次のような kvs（key-valus store）がある。

  • 各物理ノードはv個の仮想ノードを担当し、kvs全体はnv個の仮想ノードにより運用される。
  • 物理ノードが担当する仮想ノードのIDはランダムに決定される。
  • key-valueの組は、ノードIDが隣接する3個の仮想ノードに格納される。
  • key-valueの組を保持するノードIDの決定は Consistent Hashing により行う。

このようなkvsにおいて、3台の物理ノードがダウンしたときに、kvsのgetが失敗する事象の起こる確率を求めよ。という問題です。

仮想ノードについては、こちらの図 でイメージしてください。

まずは簡単な問題から

いきなり、この問題を解くのは大変なので、仮想ノードを使わない、つまり v=1 の前提で考えてみます。この場合は問題は次のようになります。

「環状に並んでいる n個のノードの中から任意に3つを取り除いた時に連続する3つのノードが削除される事象の起こる確率を求めよ」

解法について、簡単に書いておきます。ここで、n≧4 としておきます。まず、次のように高校で習うおなじみの順列組合せの問題に変換します。

「n-3個の箱に3個のボールを入れた時に、3個のボールが同じ箱に入ってしまう確率を求めよ」

これは簡単ですね。全体の事象の場合の数は、3つのボールをn-3個の箱に入れるという重複組合せになり、 3個のボールが同じ箱に入ってしまう事象は箱の数と一致するので、これを全体事象で割って、次のようになります。
\frac{n-3}{_{n-3} H_3} = \frac{n-3}{_{n-1}C_3} = \frac{3!}{(n-1)(n-2)}


検算として、n=4の場合を求めてみます。計算すると確率は1.0となります。環状に並んだ 4つのノードからどのように3つを取り除いても、連続する3つのノードが削除されることになるので、大丈夫そうです。
それから、分母に置いている全体事象の各事象が等確率で起こることも確認しておく必要があります。（そうでないと確率が求まりません）

仮想ノードを加味した場合

次に仮想ノードを加味した場合ですが、問題は次のようになります。

「環状に並んでいる vn個のノードの中から任意に3v個を取り除いた時に連続する3つ以上のノードが削除される事象の起こる確率を求めよ」

取り除くノードの数が3から3vに変わったところがポイントです。問題を一般化して、

「環状に並んでいる n個のノードの中から任意にq個を取り除いた時に連続する3つ以上のノードが削除される事象の起こる確率を求めよ。ただし、n＞q≧3」

とするとどうでしょう。仮想ノードを想定しない前提でも、3つ以上の物理ノードがダウンするという問題に拡張させた場合と解き方は同じということになります。

この場合は困ったことに、ボールはq個あるので、3つ以上のボールが同じ箱に入るという事象の場合の数は簡単には求まりません。次のような作戦でいきます。

（求める確率K）= 1 -（どの箱を見てもボールが2つ以下になっている確率L）

Lについてブレークダウンします。ボールが2つの箱の数、ボールが1つの箱の数、ボールが0の箱の数を順に、r, s, t と置きます。箱に入るボールの数qは 2r+s となることが分かります。ここで箱の数 n-q を pとしておきます。
r=0の時は、s=q, t=p-q となり、r=1の時は、s=q-2, t=p-q+1、r=2の時は、s=q-4, t=p-q+2 となることより、一般化すると、s=q-2r, t=p-q+r (0≦r≦[q/2]) となります。
（[q/2] はここでは q/2を越えない最大の整数を表すことにします）

ボール2つがr個の箱に入る事象は 同じものを含む順列 として計算でき、次のようになります。

E_r = \frac{(r+s+t)!}{r!s!t!} = \frac{p!}{r!(q-2r)!(p-q+r)!} \\= \frac{(n-q)!}{r!(q-2r)!(n-2q+r)!}


確率は全体事象で割って、このようになります。

E_r / _{n-q}H_q = E_r / _{n-1}C_q


答えは、次の式で得られます。
K = 1 - \frac{1}{_{n-1}C_q} \sum_{r=0}^{[q/2]} \frac{(n-q)!}{r!(q-2r)!(n-2q+r)!}


おしまい。（ここまでで息切れました。計算はお願いします。orz）

整合性保証の夢

logic

変な夢を見た。
整合性を保証するための簡単で強い条件を考えてみた、というような内容である。
Xというシステムがあり、AとBがXに対して同時にお互いのことを知らずに何を行う。その時、

  • Xにとって何かがAからの処理なのかBからの処理なのか識別できる。
    • 処理を受ける側から見た識別可能性のようなもの ...(i)
  • AやBはXに対して、相異なる箇所に何らかの作用を行う。
    • つまり、処理をする側から見た独立性（他の処理が混ざらない）...(ii)

が満たされているといいんじゃないか、という内容。


つまり、起こりうる不整合に関しては以下のことができないといけない。

  • 検出可能であること。
    • Xは当然として、A,Bも間接的に必要になるかも。
  • さらに、誰が悪さをしたのかがわかる。
    • これは上の条件（識別可能性）があればOK。
  • リトライ可能であること。
    • 結局、A,Bにリトライさせないといけない。このとき、独立性があるとXの手を煩わせないでうまく処理できるのでは、という発想。
    • リトライにも粒度がある。Xのレベルだとすべてのやり直し。A,Bのレベルだと、各処理の発行元の範囲でリトライをすればいい。


さて、最後のリトライ粒度であるが、これはA,Bの処理が互いに素であるかどうかに大きく依存する。互いに素であれば話は簡単である。...(iii)

ここまで、(i)...(iii)の条件が出てきたけど、具体例がないとピンとこない。あいにく夢なので忘れてしまった。また何かの機会に思い出すだろう。