Posts

A Differential Testing Approach for Evaluating Abstract Syntax Tree Mapping Algorithms

AST mappingは、コードの変更前後のASTを比べてノードの対応関係を見つける手法であり、変更差分検出に使われる。 現状、対応関係の精度を自動で評価する有効な方法はなく、評価には人手による手間がかかる。 多くのノードに1対1の対応関係があることに着目し、異なる2つのAST mappingを同じ変更に適用した結果を比べ、個別の文やトークンごとに、より正確な方を推定するアルゴリズムを提案した。 これを応用し、複数のAST mappingアルゴリズムに同じファイルの変更差分を入力し、アルゴリズムごとの不正確に検出した箇所を自動で推定できることを示した。 特定性能は、Precisionが0.98-1.00, Recallは0.65-0.75だった。

“Ignorance and Prejudice” in Software Fairness

特徴の種類を増やすと、機械学習の予測の公平性と精度を改善できることを5つのデータセットで例示した。 データセットのタスク内容は、性別、人種、年齢を特徴に含み、経済的な裕福さや再犯率を予測するもの。 他方、教師データの数を増やしても公平性は改善されなかった。

Time, Clocks, and the Ordering of Events in a Distributed System

分散システムの各プロセスにおける送受信の半順序関係をすべてのプロセスで起きた送受信の全順序関係に拡張するアルゴリズムを提案し、アルゴリズムを同期処理に応用できることを例示した。 分散システムのプロセスの時刻はほかのプロセスと同期していない可能性がある。 あるプロセスで起きたメッセージの送受信をプロセスでの時刻順に並べられても、その計測時刻を信じて全プロセスで起きたイベントを正しく発生順に並べることはできない。

アルゴリズムは、プロセスごとに論理的なクロックをもたせる。 クロックは、メッセージを送信するときに時を進める。 メッセージを送信するプロセスは、送信時刻をメッセージにふくめる。 受信したプロセスは現在の時刻とメッセージにある送信元の時刻より先の時刻に時を進める。 以上の手続きで、異なるプロセス間の送受信であっても送信時刻が受信時刻より必ず前になり、全プロセスの送受信イベントに全順序関係を定義できる。

The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, unbounded, Out-of-Order Data Processing

データ処理サービスには、処理の正確さ、遅延、システムの複雑さの間にトレードオフがある。 ストリーミング処理サービスのStorm, Samza, Pulsarは、(論文が発表された2015年時点では)メッセージは、exactly-onceではなく、欠損または重複しうる。 MapReduceやSparkなどのバッチ処理サービスは、バッチ処理の単位までデータが集まるのを待たねばならない。 Lambda architectureは、システムの複雑化を許容し、2つのアーキテクチャを使い分けることで、処理の正確さと遅延のバランスをとる。

Playing Planning Poker in Crowds: Human Computation of Software Effort Estimates

プランニングポーカーにみられるように、ソフトウェア開発の工数を見積もる手法は、プロジェクトに一定期間在籍する専門家がいることを前提にする。 しかし、OSS開発はその限りではなく、見積りの対象になるイシューの数は多い。 各イシューの見積りに5分から10分時間をかけるなら、Linux Kernelのバックログを見積りきるのに半年がかかる。

The Byzantine Generals Problem

ビザンチン将軍問題は、故障したコンポーネントが別のコンポーネントに誤ったメッセージを送りうるとき、コンポーネント間でメッセージを交換した結果、全コンポーネントが一つの正しいメッセージを合意する手段を問う。 2つのアルゴリズムがあり、署名付きメッセージを使うかどうかで分かれる。 署名付きメッセージを使うと、受信したメッセージが改ざんされたかをコンポーネントが判断できる。 署名を使わない場合、3分の2より多くのコンポーネントが正常でなければシステム全体が正しい1つのメッセージについて合意にできないことを示した。

The Browsemaps: Collaborative Filtering at LinkedIn

Browsemapsは、LinkedInのアイテムベースで水平型の協調フィルタリングである。 Browsemapは、LinkedInの画面上にある推薦するコンテンツを並べたコンポーネントをさす。 Browsemapsにおける水平型は特徴の種類の違いによらず異なるエンティティを統一的に扱えることであり、実際に、人、仕事、会社など複数のエンティティをBrowsemapsでユーザに推薦している。

Linearizability: A Correctness Condition for Concurrent Objects

オブジェクトを読み書きする並行プロセスの実行系列があるとき、読み書き操作がアトミックであるように観測でき、かつ、プロセスの実行を仮に直列化したときと同じ実行結果をえられる条件を示し、これを線形化可能性とよんだ。 線形化可能性は、直列化可能性と同様に安全性の条件だが、直列化可能性にはないローカル性がある。 いいかえると、各オブジェクトが線形化可能かつそのとき限り、システム全体が線形化可能になる。 また、ローカル性だけでなく、ノンブロッキング性もあり、操作がオブジェクトの任意の状態において定義されていれば、受信したリクエストの操作を保留しているオブジェクトは別オブジェクトの保留した操作の完了を待たずに自分の操作を進行できる。

END-TO-END ARGUMENTS IN SYSTEM DESIGN

分散システムのあるシステムから発せられた通信は、システムより低いレイヤーのネットワークを通り、ほかのシステムに到達する。 論文の発表当時から、分散システムの信頼性にかかわる機能には、途中の低レイヤーではなく高レイヤーの終端におくべきものがあると知られていた。 表題の論文は、それらを列挙し、END-TO-END ARGUMENTSと名付け、原則として提示する。 例えば、データの完全性の保証、メッセージの重複対応、メッセージが到達したことの保証が原則にあてはまる。 これらの機能を途中の低レイヤーにおくと、検証後の経路でメッセージが壊れた場合、送信元が重複メッセージをおくる場合、対向システムが受信したメッセージを処理できない場合に対処できない。 分散システム全体の信頼性をあげるのであれば、信頼性を上げる機能を低レイヤーではなく終端の高レイヤーにおくほうが効率がよい。

A History and Evaluation of System R

System Rは、1970年に発表されたリレーショナルモデルを実装した初めてのリレーショナルデータベースである。 1981年に発表された表題の論文は、System Rの開発プロジェクトを3つのフェーズに分け各フェーズごとにえられた知見をまとめている。 Phase 0は、74年から75年にかけて、シングルユーザ向けにSQLサブセットと対話的なインターフェースを開発した期間にあたる。 Phase 1は、76年から77年の、Phase 0のコードを破棄し、マルチユーザに対応しSystem Rの機能を完全に実装するまでの期間である。 Phase 2は、78年から79年にSan Jose Research Laboratoryなどでの実用にもとづく評価期間にあたる。