On 03/27/2013 10:30 AM, Janko Mivšek wrote:
Hi Paul,
Can you continue describing your idea so that one will grasp the essentials without needing to open first the Wikipedia links. Idea looks promising, just not clarified yet enough. I'm pretty user you can continue evolving it by yourself.
Best regards Janko
Sure I'll give it a shot, but caveat emptor:
Dne 27. 03. 2013 17:39, piše Paul DeBruicker:
This is the second of two not well fleshed out ideas.
On 03/26/2013 04:36 AM, Janko Mivšek wrote:
Title:
Implement Fast Byzantine Paxos in Slang
Paxos is a system for ensuring consensus across a network of processors (e.g. multiple images on multiple computers or cpus on the same hardware). Fast Byzantine Paxos is Paxos extended to ensure reliability in the face of arbitrary failures among processors, lying from processors, collusion among more than once lying processor, etc. Fast Byzantine Paxos is just a version of Byzantine Paxos that omits a step seemingly trading network latency for additional CPU work. But I'm not sure of the tradeoffs.
Level: (beginner, intermediate, advanced)
Advanced
Possible mentor: (if already known)
Possible second mentor: (if already known)
I am willing to help out but I'm sure there's someone better as I don't know slang or how to go about implementing Paxos. yet.
Description
Paxos (https://en.wikipedia.org/wiki/Paxos_%28computer_science%29) is a framework for solving consensus in a network of unreliable processors. A python implementation is available here: http://openreplica.org/
My basic understanding is that among a set of images (technically "processors" but I'm going to use image because it seems more relevant here) you construct a quorum. That quorum calculates and agrees on a response to a client request. The quorum survives and is the unit of computation but the individual images inside it change in make up and number through time as images and machines die and come back. The quorum maintains and replicates the state among its member images. The images in the quorum can at any time assume at least one of 5 roles (client, acceptor, proposer, learner, leader) for that quorum and most play all but leader all the time. The images can participate in more than one quorum. There is only one 'leader' per quorum (but the leader can be any image in the quorum and is 'elected' by the quorum members) and sends messages to others in the quorum to process. I'm not sure of the gory details but the client sends a request to the quorum, the quorum processes it, and sends back the one agreed upon response regardless of how many machines are in the quorum that fail or fail to respond during the computation. Paxos describes all the intra process communication that needs to take place to ensure that the quorum provides reliable responses to requests in the face of hardware and network failures. Implementing it in Slang would potentially make it faster than in image (guessing) because C and it could be a plugin.
Technical Details
Could just port ConCoord (the openreplica.org's backend) from Python to Slang rather than starting from scratch.
It is my understanding that implementing Paxos from scratch and covering all corner cases and failure modes is very very hard. Probably also confusing. Sorry I don't know more but here's a zip of the papers I've collected that describe ways and issues around implementing it: http://dl.dropbox.com/u/4460862/paxos-papers.zip
Benefits to the Student
Learn Smalltalk, Slang. Implement something hard.
Also build a robust distributed Smalltalk system.
Benefits to the Community With enough images you can just persist everything in the image and each image can be a reasonable size.
Other benefits include making a (hardware, network) failure resistant server Smalltalk process