分散合意アルゴリズム Raft を TLA+ で検証する - 俺の Colimit を越えてゆけ
はじめに 分散合意アルゴリズム Raft とは 分散合意アルゴリズムとは Raft の特徴 Raft が満たす性質 Election Safety Leader Append-Only Log Matching Leader Completeness State Machine Safety TLA+ とは TLA+ による Raft の形式的仕様 TLA+ による Raft の検証方法 TLA+ Toolbox のインストール 新規 Spec の作成 Model の作成と実行 補足: コマンドラインでの検証 Raft の拡張について Leadership Transfer Membership Change Log Compaction Client Interaction おわりに Raft 理解度を調べるクイズ 参考資料 Raft に関する資料 TLA+ に関する資料 はじめに この
自動テストに限界を感じた私がなぜ形式手法に魅了されたのか - 若くない何かの悩み
長らく自動テストとテスト容易設計を生業としてきましたが、最近は色々な限界を感じて形式手法に取り組んでいます。 この記事では、既存の自動テストのどこに限界を感じてなぜ形式手法が必要なのかの私見を説明します。なお、私もまだ完全理解には程遠いため間違いがあるかもしれません。ご指摘やご意見はぜひ Kuniwak までいただけると嬉しいです。 著者について プログラマです。開発プロセスをよくするための自発的な自動テストを支援する仕事をしています（経歴）。ここ一年は R&D 的な位置付けで形式手法もやっています。 自動テストの限界 自動テストとは 私がここ数年悩んでいたことは、iOS や Web アプリなどのモデル層のバグを従来の自動テストで見つけられないことでした。ただ、いきなりこの話で始めると理解しづらいと思うので簡単な例から出発します。 この記事でいう自動テストとは以下のようにテスト対象を実際に
A Proof for Log Matching Property of Raft - 俺の Colimit を越えてゆけ
背景 Log Matching Property の証明 データ構造と述語の定義 AppendEntries 関数の性質 leader の log に関する性質 Log Matching Property の証明 参考資料 背景 分散合意アルゴリズム Raft は kubernetes のクラスターの構成情報を保存する etcd の内部で使われておりお世話になっている方も多いアルゴリズムだと思います。 この記事では Raft の満たす重要な性質である Log Matching Property について証明します。 元々、『Raft を TLA+ で検証する』というタイトルの記事を書こうと考えて Raft の考案者 Diego Ongaro の博士論文を読み始めました（その記事は後日公開予定です）。 アルゴリズムは論文の 3 章に書かれているのですが、そこで Raft が常に成り立つことを
ゼロから学んだ形式手法 - DeNA Testing Blog
2020年1月に入社し、SWETの仕様分析サポートチームに加わったtakasek（@takasek）です。 仕様分析サポートチームでは、社内のプロダクト開発に対する形式手法の活用可能性を模索しています。当ブログでも、継続的に形式手法に関する情報発信をしています（形式手法 カテゴリーの記事一覧）。 この記事では、加入3か月を経てようやく形式手法の輪郭が掴めてきた私の視点から、学習前後での理解の変化について振り返ります。想定読者として学習前の私と近い属性——すなわちコンピュータサイエンスや数学の専門教育を受けておらず、主に現場での実務と自習に頼ってきたソフトウェアエンジニアを想定しています。 形式手法を学ぶ前の認識と疑問 ソフトウェアエンジニアとしての私の一番の興味関心は設計手法です。設計は、なんらかの解決したい問題に対して、ある一面を切り取った構造（モデル）を与え、そのモデルを解決の機構に落
The Kubernetes Scheduler
Kubernetes is a Container Orchestration Engine designed to host containerized applications on a set of nodes, commonly referred to as a cluster. Using a systems modeling approach, this series aims to advance the understanding of Kubernetes and its underlying concepts. The Kubernetes Scheduler is a core component of Kubernetes: After a user or a controller creates a Pod, the Kubernetes Scheduler, m
TLA+の社内勉強会スライド公開します - takaha.siの技術メモ
Raftを使ってDFSを作るという仕事を数年前ぐらいから続けています。そのためか最近、形式仕様記述（特にTLA+）とかModel checkingとかTheorem provingとかが私の中でアツいです。TLA+とかAlloyとかVDM++とかSpin周りのやつです。 ソフトウェアの仕様を形式仕様で厳密に書き下して検証、証明するという手法がある！ということ自体は院生時代に見聞きして知ってたんですが「難しそう」とか「一部のすごい人にしか使えなさそう」といった先入観があってなんとなく敬遠してました。正直、当時は自分の身近な問題であると感じられていませんでした。 あれから10年以上たって最近形式仕様記述とかModel checkingとかTheorem provingというものは「必須なものである」という認識がようやく私の中にも芽生えたようです。仕事で分散システムの開発を通じて「これは人間の頭
Introduction to TLA+ Model Checking in the Command Line
Otherwise known as “wait, you mean I can use the TLA toolbox from the command line?” I started playing around with TLA+ and its more programmer friendly variant PlusCal about a year ago. At that time the amount of documentation that was understandable to people like me who do not enjoy reading white papers full of mathematical notation was slim to none. (Today you can buy Hillel Wayne’s excellent
テスト駆動開発から証明駆動開発へ #JTF2019 / July Tech Festa 2019
July Tech Festa 2019 で使用したスライドです。 近年、テストを書く文化は広く普及しており、開発フローにおいて自動テストを組み込むことはもはや常識となりました。しかしよく考えてみると、有限個のテストケースが保証しているのは、所詮「特定の有限個の入力に対する出力」にしか過ぎません。では「あり得る全ての入力」に対してプログラムの性質を保証することは果たして可能でしょうか？ この問いに対する答えのひとつが「定理証明」と呼ばれる手法です。定理証明では、数学的な「証明」をプログラム上でエンコードすることにより、真に「全ての入力」を扱うことができます。本セッションではこの定理証明を取り上げ、従来のテストとの考え方の違いや具体的な適用方法について、サンプルを交えつつ解説します。 イベント概要：https://2019.techfesta.jp/speakers#A10
Wadler's Blog: How Amazon Web Services Uses Formal Methods
How Amazon Web Services Uses Formal Methods by Newcombe et al, appeared in Communications of the ACM in April 2015. It describes the use of Leslie Lamport's TLA+ (Temporal Logic of Actions) to refine the design of web services such as Dynamo DB and S3. (S3 stored 2 billion objects and handled 1.1 million transaction per second back in 2013.) Thanks to Jessica Kerr for pointing me to this paper aft
形式手法の分類 - 応用事例DB
形式手法の導入を検討する上で参考となる実システムに対する実践的な応用事例について、費用対効果や導入時の課題・工夫点等を中心にまとめています。 現在は、「フォーマルメソッド導入ガイダンス」第４部付録 12.応用事例情報 と同じ内容ですが、今後事例の数を増やしていく予定です。 キーワードで検索する
Formal Reasoning About Programs
This is the web site for the early stages of a book introducing both machine-checked proof with the Coq proof assistant and approaches to formal reasoning about program correctness. Grab a Draft Source on GitHub Quasi-latest PDF draft Quasi-latest source-code tarball Quasi-latest source-code tarball, library only (warning: the author really does not recommend using it in serious projects!) Use in
ファイルシステムにおける名指しと解釈：XPathを使って - 檜山正幸のキマイラ飼育記 (はてなBlog)
一昨日書いた記事、それと過去の2つの記事（↓）で扱っていることは、「プラットフォームやコマンドごとに、ファイル名／ディレクトリ名の解釈が違うよ」ってな話です。 cp, mvコマンドとcopy, moveコマンドの微妙な違い：実例とまとめ ディレクトリを再帰的にコピーするには 便利な厄介者： ディレクトリを指すシンボリックリンク 僕は、このような違いを個別の事例としては知ってましたが、系統的に考えたことはなかったです。そこで、LinuxのようなPOSIXベースのシステムとWindowsにおいて、名指しの方法や名前の解釈がどう違うかを例示してみます。XPath言語の小さなサブセット言語を使った形式的記述も紹介します -- これが本題ですので、鬱陶しい実例を飛ばして「XPath言語のサブセット」へ飛んでもいいです。 内容： ファイルシステムのツリー構造 Windowsのcopyにおけるファイル名
Oregon Programming Languages Summer School
Oregon Programming Languages Summer School — July 16-28, 2012 Logic, Languages, Compilation, and Verification Speakers Organizers Curriculum Schedule Participants The program consists of 80 minute lectures presented by internationally recognized leaders in programming languages and formal reasoning research. Technical Lectures Logical relations — Amal Ahmed Lecture 1 part 1 part 2 part 3 Lecture 2
Okasaki's Lazy Queues - LiquidHaskell
The “Hello World!” example for fancy type systems is probably the sized vector or list append function (“The output has size equal to the sum of the inputs!”). One the one hand, its perfect: simple enough to explain without pages of code, yet complex enough to show off whats cool about dependency. On the other hand, like the sweater I’m sporting right now, it’s a bit well-worn and worse, was never
Coqの型クラスの使い方：バンドル方式とアンバンドル方式 - 檜山正幸のキマイラ飼育記 (はてなBlog)
「Coqで定理を記述してみる、型クラスとか使って」に次のような断り書きを入れました。 ミート半束のような代数構造をどう定義するのが良いのか、あんまり分かってないのですが、まーまー使える方法を紹介します。この方法には課題があることを注意しておきます。今回の目的ではうまくいきますが、より大規模な記述にはもっと効率的な方法が必要かも知れません。 代数構造を定義する別な方法である、スピターズ／ファンデル・ウィーゲンの方式をかいつまんで紹介します。 内容： Bundling is bad 追記： 方式の呼び名 オールインワン方式 バンドル方式 アンバンドル方式 何が違うの？ ソースコード Bundling is bad 「Coqで定理を記述してみる、型クラスとか使って」では、ミート半束と（最大元付き）順序集合を定義するために、「マグマのクラス」と「法則（公理系）を書いたクラス」を使いました。スピター
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
LTSmin
TechCrunch | Startup and Technology News
AWS は形式手法の夢を見るか？ - モデル検査器 Alloy によるインフラ設計
bitbucketの使い方
Amazon.co.jp: Type Theory and Formal Proof: An Introduction (English Edition): Nederpelt, Rob, Geuvers, Herman: Digital Ebook Purchas