CS677: Programming Assignment 2Renaldo Part Deux: A Server-less GameDistributed Operating Systems Spring 2003Department of Computer ScienceUniversity of Massachusetts, Amherst, MA 01003 [email protected] The problemThis project has tree purposes, namely to gain experience with. . .• issues concerning distributed consistency• transactional techniques• leader election algorithms• clock synchronizationYou are encouraged to re-use your work from your first programming assignmentas much as possible. In this project, you need to design a server-less version ofyour centralized multi-player game from programming assignment 1.2 IntroductionAfter learning of the wonderful work of CS677 students on their Renaldo gameconcept, Fundingo game corporation has decided to pick up the Renaldo gameproject. A meeting with Dr. Jane Dasani, Fundingo’s Chief Scientist and proudUMass-CompSci Alumna, has resulted in the edict, ”Hey, make it scale.” Afterhours of technical discussion, the descision was made. ”Dude, go server-less.”3 The conceptIn programming assignment 1, you implemented a centralized client-server ap-proach. In the client-server game system, clients issue requests to a centralized1server which implements game dynamics and computes global game state. Ina server-less environment, each client maintains its own game state. In this as-signment, we no longer employ a centralized game server. A server-less gamingenvironment can be thought of as a peer network. A peer environment has manyadvantages over a centralized approach. These include robustness and scalabil-ity. A peer environment is more robust because a single failure only affects thefailing node. A peer environment is more scalable because it induces a naturalpartition of load (computation of state) among participants in the game. As isthe case with many distributed systems issues, these advantages come at a cost.Because each client computes its own game state, there is a real possiblilityfor inconsistency across each client participating in the game. That is, twoparticipants may come to a different ”understanding” of the current state ofthe game. For example, two Renaldo clients can incorrectly think that s/he hasconsumed the same food item in the same grid square.Because of this, each participant must implement a means of coping withcomputation of distributed state. Simply put, the participants (or peers) in thegame must reach agreement or consensus on a number of things. Consensus is arecurring theme you will see in distribted systems in areas such as leader election,distributed synchronization, and transactions [3]. Generally, in a distributedsystem, consensus is reached among participants by the exchange of messages.The format, meaning, and response to these messages are our protocol. Whenyou think of what is a client and what is a server, think about what role eachplays. A client initiates a request. A server receives a request, performs somecomputation and returns the reply. A peer can assume both a client and serverrole. It acts as a client when it initiates requests. It also acts as a server whenit receives requests, performs a computation and returns a response.4 Game DetailsTo simplify things a little, your game will be limited to 4 players. Each playermaintains a copy of the grid world including the grid squares, and walls(figure1). When a participant makes a move, he must inform his peers in the game.This is to be accomplished using application-level multicast. By this approach,a list of peers on the network is maintained and a unicast message is sent to each(figure 2). Thus, each peer implements an application-level multicast client toperform application-level multicast (ALMC).One of the peers is to be designated as the chairperson (chair). The chairis responsible for managing the placement of food and publication items inthe department. Thus, the chair implements a food/publication client whileeach peer implements a food/publication server. Renaldo’s advisor, Prof. RheaSarch, has gone on sabattical for a semester. While this means that Renaldo’sadvisor will not be present (at least for programming assignment 2), Renaldomust still ”read” publication items in addition to eating food and drinking coffee.When the chair places a food item or publication, his ”move” is ALMC’ed topeers on the network. The game begins with a single peer. As new peers join2Figure 1: Server-less gameFigure 2: Application-level multicasting of moves3Figure 3: State changes due to request messagesthe game, they must be informed of the current game state. It is also the job ofthe chair to bring the new graduate student up to date. The department chairalso implements a bootstrapping service used to bring newly joining peers upto date on game state. Thus, each peer implements a bootstrap client whilethe department chair implements a bootstrap server. It is assumed that peersperform graceful joins and leaves for the game. When a new peer joins thenetwork, it discover’s the department chair and engages in a bootstrappingprotocol to acquire state from the department chair. As update requests areserviced by a peer, its local state moves through a sequence s0, s1, s2, . . . ofstates. Define stto be the state of a peer at timestep t. Given a request rij, astate transition (si, sj) is effected (figure 3).If the the current state (at timestep t) is such that st6= si, then the request isa conflicting message. When this happens, the peer has reached an inconsistentstate. Assuming a total ordering on request messages, system state must bereverted to the last known consistent state si. In transaction processing, this isknown as rolling back system state (figure 4). To implement rollback, a log ofstate history must be kept. Because we are not concerned about durability ofsystem state, this log does not have to be made persistent. An in-memory log ofup to 100 messages is adequate. Exactly how logging is implemented dependson the type of actions performed.The two classes of actions with which we are concerned are known in transactionprocessing as unprotected and real actions [2]. This distinction is made based onwether or not the change in state brought about by an action can be reversed orundone by executing an operation or compensating action similar to the originalaction. In our server, actions are unprotected. For an unprotected action, thesystem requires knowledge of the compensating action ciand a piece of data