Guesstimate A Programming Model For Collaborative -Books Pdf

GUESSTIMATE A Programming Model for Collaborative
07 Apr 2020 | 11 views | 0 downloads | 11 Pages | 324.50 KB

Share Pdf : Guesstimate A Programming Model For Collaborative

Download and Preview : Guesstimate A Programming Model For Collaborative

Report CopyRight/DMCA Form For : Guesstimate A Programming Model For Collaborative


jected 1 Otherwise if an operation has no precondition violations on different portions of the puzzle Maintaining the state of the ma. it is immediately executed on the guesstimated state without any chine in a server is inflexible and can lead to poor response times. blocking The same operation is executed again at commit time on Thus we might wish to replicate the state of the puzzle locally in. a different copy of the shared state referred to as committed state each of the machines. that is guaranteed to be identical in all machines In between issue Programming such an application with replicated state is non. and commit of an operation issued by a machine mi operations trivial In each machine we need to have three components 1. from other machines can commit and G UESSTIMATE attempts to model that maintains the state of the puzzle 2 a component that. update the guesstimated state of mi with the knowledge of these manages the user interface and 3 a synchronizer that performs. committed operations from other machines As a results each op synchronization between the states of various machines The syn. eration can be executed several times on the guesstimated state as chronizer is responsible for communication between all the repli. it progressively converges toward the committed state For the class cated instances of the model in various machines Whenever the. of applications we study we expect that most of the time the result model changes in any machine the synchronizer needs to propagate. of the various executions of an operation from issue to commit are changes to all other machines There could be conflicts because two. identical but this is not guaranteed updates by two different machines could violate the constraints of. We believe that the G UESSTIMATE programming model is par Sudoku mentioned above There could be races because both the. ticularly useful in building collaborative distributed applications UI and synchronizer could simultaneously update the model in each. where a group of users are collaborating to perform a shared task machine Programming the application correctly taking all these is. such as solving a puzzle for example We have built six such ap sues into account is difficult G UESSTIMATE s goal is to hide much. plications with G UESSTIMATE a multi player Sudoku game an of this complexity from the programmer and offer a simplified pro. event planning application a message board application a car pool gramming model where the programmer only needs to worry about. system an auction system and a small twitter like application see expressing the application logic All the complex logic related to. Section 6 G UESSTIMATE provides facilities by which the pro keeping the model synchronized across various machines is han. grammer can annotate operations with particular kinds of specifica dled by the run time system. tions and use off the shelf program verifiers to check that the im We describe how G UESSTIMATE s programming model can be. plementations of the operations satisfy these specifications These used to program this application Figure 1 shows the class Sudoku. facilities enable the programming model to guarantee that even if which represents the model state shared by multiple computers In. there are certain kinds of discrepancies between the results of ex G UESSTIMATE the programmer declares shared objects by deriv. ecution of the operation on the guesstimated state and the actual ing from the abstract base class GSharedObject Other than deriv. committed state as long as these differences do not matter with ing this abstract base class which forces providing code for a Copy. respect to the specification of the operation the model can simply method the programmer can program this class in whatever way. tolerate them For other more extreme kind of discrepancies which she wants In this case the class has a 9x9 array puzzle declared. violate the specification of the operation the model provides com in line 2 The method Check defined in lines 4 10 returns true if on. pletion functions which can be used to inform the user of discrep updating puzzle row col with val the constraints of Sudoku. ancies and have the users deal with such discrepancies Challenges are satisfied and false otherwise The method Update defied in. also arise due to interaction between operations A user might per lines 12 23 updates puzzle r c to value v if it is a legal update. form two operations o1 and o2 where the inputs to o2 depend on the and returns true If the update is not legal it returns false Finally. results of o1 Thus a discrepancy in the execution of o1 affects the the programmer has to define a copy method line 24 that when. execution of o2 G UESSTIMATE provides facilities by which such passed a source object copies the array puzzle from the source. operations with dependencies can be grouped into atomic opera to the this object Note that other than deriving from the abstract. tions with an all or nothing execution semantics In the extreme base class GSharedObject the programmer does not have to do. the programmer might want one copy serializability for some im anything different from the way she would write this class for a. portant operations and this can be implemented by the programmer non distributed application. explicitly doing blocking until the operations commit Figure 2 shows the user interface class for this applica. This paper explores such a programming model presents an op tion which uses the Sudoku class from Figure 1 In line 6. erational semantics for the programming model a language exten a new instance of the Sudoku class is created using a call to. sion to C to use this programming model and our experience in Guesstimate CreateInstance Internally G UESSTIMATE cre. writing some applications with the programming model ates an instance of the Sudoku class and assigns it a unique identi. fier Other machines can now share this Sudoku instance by calling. 2 Programming with GUESSTIMATE the JoinInstance method All machines that have joined this Su. doku instance can now update this object while the run time takes. We motivate G UESSTIMATE s programming model using the care of all communication and synchronization. example of a multi player collaborative Sudoku puzzle The Su In lines 15 24 of Figure 2 we see the event handler in the UI. doku puzzle consists of a 9x9 square where each square needs to that is executed in response to an update of row r column c with. be filled with some integer between 1 and 9 The 9x9 square is value v In response to this event in the case of a non distributed. divided into nine 3x3 sub squares uniformly Each instance of the program this code would simply call s Update r c v With. puzzle comes with some pre populated numbers The objective of G UESSTIMATE the programmer has to create an operation us. the game is to fill all the entries in the 9x9 square subject to 3 con ing Guesstimate CreateOperation as seen in line 17 and is. straints 1 the same number cannot repeat in a row 2 the same sue the operation using Guesstimate IssueOperation as seen. number cannot repeat in a column 3 the same number cannot re in line 19 When the operation is issued G UESSTIMATE exe. peat in a 3x3 sub square Suppose we wish to program a collabora cutes it on the guesstimated copy of the Sudoku object If the. tive Sudoku game where players are distributed across the Internet execution fails due to violation of any of the constraints of Su. That is we wish to allow different players to collaboratively work doku that is s Update r c v returns false the operation is. dropped Otherwise G UESSTIMATE submits it internally to a. 1 In addition to better response times the user gets feedback on operations queue to be committed later simultaneously in all machines The. that fail on the guesstimated state quickly so that they can potentially alter code in lines 22 23 calls the redraw function if the operation suc. the operation and resubmit it,1 class Sudoku GSharedObject 1 public class UI. 2 private int 9 9 puzzle 2 enum Color RED YELLOW GREEN BLUE COLORLESS. 3 3 Sudoku s, 4 private bool Check int row int col int val 4 OnCreate. 5 5 Here is how we create a shared object, 6 returns true if adding val at puzzle row col 6 s Sudoku Guesstimate CreateInstance typeof Sudoku. 7 does not violate the constraints of Sudoku 7,8 and false otherwise 8. 9 9 void ReDraw int r int c COLOR color,10 10 Guesstimate BeginRead s.
11 11 Board r c Text s puzzle r c, 12 public bool Update int r int c int v 12 Guesstimate EndRead s. 13 13 Board r c BackColor color,14 adds value to puzzle r c if all constraints 14. 15 are satisfied 15 void OnUpdate int r int c int v. 16 if r 9 r 0 return false 16 the operation we want to do is s Update r c v. 17 if c 9 c 0 return false 17 Operation op Guesstimate CreateOperation s Update r c v. 18 if v 9 v 0 return false 18 Issue the shared operation together with a completion function. 19 if Check r c v 19 bool res Guesstimate IssueOperation op. 20 return false 20 bool b if b ReDraw r c Color GREEN. 21 puzzle r c v 21 else ReDraw r c Color RED,22 return true 22 if res. 23 23 ReDraw r c Color YELLOW,24 public void copy GSharedObject src 24. Figure 1 Sudoku class Figure 2 UI class, ceeded on the guesstimated copy The Redraw function lines 9 GUESSTIMATE API The above example motivates the various.
14 reads out the updated value from the guesstimate copy and re aspects of the G UESSTIMATE programming model We now give a. freshes the UI by changing the text on the square and painting it complete description of the G UESSTIMATE API. YELLOW Enclosing reads within Guesstimate BeginRead and. Guesstimate EndRead ensures that they are isolated from con GSharedObject CreateInstance Type type takes the. current writes via the synchronizer type of the shared object as input and creates a unique object of. At the time of commitment this operation s Update r c v that type and returns it to the client The new object is internally. may succeed or fail In particular the operation can fail if between assigned a unique identifier and is registered with G UESSTI. the time instant when s Update r c v was issued and the time MATE. instant when the operation is committed operations issued by some List string AvailableObjects returns a list of. other machine got committed and these other operations violate the unique identifiers of all objects. precondition for the execution of s Update r c v, Type GetType string uniqueID returns the type of a. After commitment G UESSTIMATE calls a completion func. tion which is supplied as a delegate in the last argument of shared object given its unique identifier as input. Guesstimate IssueOperation lines 20 21 The completion string GetUniqueID GSharedObject obj returns the. function takes a boolean value as argument This boolean is the uniqueID of a shared object. result of executing the shared operation in this case Update dur GSharedObject JoinInstance string uniqueID takes. ing commitment The completion operation is used to change the the uniqueID of an available object and returns a reference to. colors on the UI as follows If the update operation is successful that object In addition the machine executing this operation is. the completion operation changes the color of the square at row r registered for future synchronizations on the object. column c to GREEN and if update fails the color is set to RED The. way colors are manipulated by the UI in this example demonstrates sharedOp CreateOperation GSharedObject. how G UESSTIMATE allows the programmer to deal with changes obj string methodName params object. to the shared state if some operations succeeded initially but failed parameterList takes a shared object the method name and. later due to conflicting operations from other machines the parameters of the method as input and returns a shared. Thus programming with G UESSTIMATE involves the following operation of type sharedOp. A programmer can combine multiple shared operations to form. 1 Create shared classes that is classes for objects that hierarchical operations A shared operation can have a hierarchical. the programmer wants to be shared across multi structure as defined in the grammar below. ple machines such that they are derived from the SharedOp PrimitiveOp AtomicOp OrElseOp. abstract base class GSharedObject When creating AtomicOp Atomic SharedOp. shared objects use Guesstimate CreateInstance OrElseOp SharedOp OrElse SharedOp. or Guesstimate JoinInstance methods provided by An AtomicOp is treated as an indivisible operation with all. G UESSTIMATE or nothing semantics That is if any one of the enclosed fail then. none of the operations update the shared state If all the enclosed. 2 To invoke an operation on a shared object first create the oper operations were to succeed then the shared state is updated by all. ation using Guesstimate CreateOperation and then issue of them The implementation of Atomic operations is done using. the operation using Guesstimate IssueOperation copy on write at the granularity of objects see Section 4 The. 3 Supply a completion function to OrElseOp is a hierarchical operation that allows the programmer. Guesstimate IssueOperation to reconcile the client to specify an alternate operation in case of failure The semantics. of the shared object in case the operation fails during commit of op1 OrElse op2 is that at most one of op1 or op2 is allowed. to succeed with priority given to op1 If both op1 ad op2 fail then machines in the distributed system this is an invariant that can be. op1 OrElse op2 fails The programmer is allowed to arbitrarily proved by induction on the operational semantics The sequence. nest these two hierarchical constructors The following API is used P consists of pending operations that have been submitted at this. to create and issue shared operations machine and guesstimated state g is obtained by executing this. sharedOp CreateAtomic List sharedOp ops takes a, sequence of operations P starting from the committed state c. Since the sequence P may be different for different machines the. list of shared operations as input and returns a hierarchical. guesstimated state g could be different for different machines As. shared operation, the system proceeds executing operations from P are moved to C. sharedOp CreateOrElse sharedOp op1 sharedOp and the guesstimated state g and the committed state c converge. op2 takes two shared operations as input and returns a new to the same value when P becomes empty. hierarchical shared operation The set of machine states is denoted by The state of the. IssueOperation sharedOp s completionOp c takes as distributed system is a function from machine index to We. first parameter a sharedOp s created using CreateOperation use the notation h i C i c i P i g i i to denote the state. CreateAtomic or CreateOrElse and a second parame of the ith machine i. ter of type completionOp The type completionOp is a. delegate type defined with the signature delegate void Operations Each machine can modify its local state using local. CompletionOp bool v IssueOperation applies s to up operations that can read the guesstimated state and local state. date the guesstimated state immediately Further the opera but can update only local state A local operation therefore has. tion is added to a pending list for committing on all machines signature Local operations do not change shared. G UESSTIMATE also remembers the machine m that submitted state and they are not applied on other machines In addition to. the operation At the time of commitment the completion oper managing local state local operations can be used to maintain. ation c is executed on machine m More details can be found in information regarding submitted operations or to query the shared. Section 3 state before applying an operation to change the shared state The. set of all local operations is L, void BeginRead GSharedObject object void A shared operation reads and updates the shared state Shared. EndRead GSharedObject object these methods can operations can succeed or fail We can think of each shared opera. be used to directly read the guesstimated state without issuing tion as having a precondition 0 and the operation fails if it. operations All reads enclosed within BeginRead and EndRead is attempted to be executed from a state 6 0 For example if a. are guaranteed to be isolated from concurrent writes to the shared operation tries to buy tickets on an airplane then it can fail. object through the synchronizer if there are not enough seats available Thus in addition to updating. Apart from using this API to create shared objects and issue oper the shared state a shared operation returns a boolean value as well. ations on shared objects the programmer can choose to implement A shared operation therefore has signature B The set. the application as she pleases of all shared operations is S. We associate a specification s with every shared, operation s A shared operation s conforms to specification s if.
3 Formal Model for any pair of shared states 1 and 2 1 if s 1 h 2 truei. In this section we describe the G UESSTIMATE programming then h 1 2 i s and 2 if s 1 h 2 falsei then 1. model formally and give an operational semantics for the model 2 That is a shared operation either returns true and satisfies. The programming model is presented at the level of abstraction a its specification or returns false and does not modify the shared. programmer needs to understand in order to write programs Thus state We use specifications on shared operations to reason about. the internal details of how the G UESSTIMATE runtime performs applications written using G UESSTIMATE More details can be. replication and synchronization are somewhat hidden in this pre found in Section 5. sentation Section 4 presents the G UESSTIMATE runtime and ar A completion operation reads the local state shared state and a. gues that the runtime indeed faithfully implements the operational boolean value and updates the local state A completion operation. semantics presented in this section therefore has signature B The set of all completion. operations is C, Objects and state A distributed system is a pair hM Si where M. A composite operation o is a pair hs ci where s S is a shared. is a tuple of M machines hm1 m2 m M i and S is a set of. operation and c C is a completion operation In a composite. shared objects In the example in Section 2 the Sudoku object is a. operation the boolean value produced by the shared operation is. shared object An application can have several such shared objects. passed as an argument to the corresponding completion operation. A shared state is a valuation to the set of shared objects is the set. The set of all composite operations is O The semantics of a. of all shared states In addition each machine mi M maintains. composite operation hs ci can thus be understood as. a set of local objects Li and this set could be different for different. machines A local state is a valuation to the local objects is the let 1 b s in. set of all local states The programming model has four kinds of let 1 c 1 b in. operations 1 local operation 2 shared operation 3 completion 1 1. operation and 4 composite operation described formally below. The state of a machine is a 5 tuple h C c P g i where Given a composite operation o hs ci we use the notation o or. is the local state at the machine C is a sequence of equivalently hs ci to denote a function with signature. completed shared operations c is the committed state at the with the following semantics. machine P is a sequence of pending composite operations at the. machine and g is the guesstimated state at the machine hs ci let 1 b s in 1. The committed state c is obtained by executing the sequence We also extend the notation to map a sequence of composite. of completed operations C from the initial state The programming operations to function with signature with the semantics. model guarantees that the sequence C of completed operations is. identical across all machines and thus C and c are equal for all o1 o2 on on on 1 o2 o1. R1 o L issued at machine i i o g i i,o hs ci C issued at machine i P i Append P i o. s g i true g i o g i,P i AllButFirst P i,C i Append C i s. c i i o c i i,R3 o hs ci First P i,j 6 i C j Append C j s. j 6 i c j s c j,j 6 i g j P j s c j,Figure 3 Operational semantics.
Operational semantics Each machine mi issues a sequence of In reality this takes several rounds of communication between the. local and composite operations oi1 oi2 Local operations are machines but the programming model gives the illusion that the. executed locally on each machine with no communication to other commitment happens atomically on all machines Section 4 gives. machines Each composite operation is first executed locally on details on how the runtime implements atomic commitment Dur. the guesstimated state of the issuing machine and queued in the ing the commitment process the completion routine c is run on the. sequence of pending operations Atomically a pending operation machine mi which issued the operation and if the operation s fails. is picked from the front of a pending queue of some machine and then the completion routine c will have the opportunity to take re. executed and committed on all machines medial action. The operational semantics of G UESSTIMATE is given by the. three rules in Figure 3 The rules are guarded commands of the Invariants G UESSTIMATE guarantees that when the system qui. form 0 where is the current state is a guard a esces and the pending queues of all machines is empty the guessti. predicate that needs evaluates to true on current state and inputs mated state and the committed state of all the machines converge. for the rule to be enabled and 0 is the next state 0 is obtained to the same value. by updating some components of We use the notation c1 Formally every machine state h C c P g i satisfies the in. v1 c2 v2 to denote a new state where component c1 in variant P c g The entire system which comprises all ma. gets updated to value v1 component c2 in gets updated to chine states satisfies the invariant that for any pair of machines mi. value v2 etc Any component not specified as updated retains its and mj we have that c i c j and C i C j These. old value invariants can be proved by induction over the transition rules R1. To state the operational semantics formally we need a few R2 and R3 allowed by the operational semantics. definitions The function First list returns the oldest entry in. list The function AllButFirst list removes First list from 4 The GUESSTIMATE runtime. the list and returns all the other elements preserved intact in the. same order The function Append list o returns a new list with Synchronization The operational semantics given in Section 3. o appended as the last element of list suffices to use G UESSTIMATE In this section we describe our spe. Rule R1 states that a local operation at machine i merely mod cific implementation of synchronization in G UESSTIMATE runtime. ifies the local state at machine i Rule R2 states that a composite In particular we describe how we simulate the atomic commitment. operation issued at machine i is appended at the end of the pending and how the implementation ensures that each operation is exe. queue at machine i and updates the guesstimated state at machine cuted at most three times If the reader is merely interested in using. i Note that this rule has a guard s g i true which re G UESSTIMATE this description can be skipped However if the. quires that the operation s succeed before it is added to the pending reader is curious about how the G UESSTIMATE runtime guarantees. queue If s g i false then the operation o is dropped the semantics given in Section 3 we give some details below. Rule R3 describes commitment of a shared operation A shared The synchronizer component of the G UESSTIMATE runtime. operation o hs ci is picked from the front of the pending queue maintains all the necessary state needed to coordinate among the. P i of some machine i The operation is removed from the pend machines At each machine mi it maintains a list of all shared. ing queue P i of machine i and moved to the committed queue objects in the system all calls to CreateInstance and a list of all. C i of machine i The committed state c i and local state i objects that machine mi is subscribed to calls to JoinInstance. of machine i are updated by executing the operation o For every made by mi For each object that machine mi is subscribed to the. machine j such that j 6 i the shared operation s is also exe synchronizer keeps two copies of the object one to maintain the. cuted to update the committed state c j The operation is also committed state c i and another to maintain the guesstimated. appended to the committed sequence C j and updates the guessti state g i It also maintains an ordered list of pending operations. mated state g j by executing the pending operations P j on the P i and a list of committed operations C i Every operation that. updated committed state The rule R3 does not have a guard which is issued by machine mi via IssueOperation is added to P i. requires that the operation s be successful The operation is exe To communicate between machines the synchronizer uses Peer. cuted regardless of whether the operation s is successful or not Channel a peer to peer P2P communication technology that is. Also note that the guesstimated state g i does not need to be part of NET 3 5 PeerChannel allows multiple machines to be com. updated since the concatenation of C i followed by P i is in bined together to form a mesh Any member of the mesh can broad. variant due to the operation the first element of P i is moved to cast messages to all other members via a channel associated with. be the last element of C i During commitment the operation s the mesh G UESSTIMATE uses two meshes one for sending sig. is executed on all machines simultaneously and atomically and up nals and another for passing operations Both meshes contain all. dates the committed state and guesstimated state in each machine participating machines. Synchronization among the machines is done in a master slave nization operations are used from within the Synchronizer and. mode One of the machines is designated to be the master and is none of them involve more than one machine While the current. responsible for periodically initiating the synchronization process implementation uses pessimistic concurrency control lock free im. The synchronization happens over 3 stages plementations and optimistic concurrency control could also have. been used For example the pending list could be implemented as a. 1 AddUpdatesToMesh In the first stage the pending opera lock free queue and updates to the shared state could be serialized. tions from all machines are gathered to construct a consol with optimistic concurrency control This would be useful espe. idated pending list Pall i at each machine mi This hap cially if the shared state were large as it would allow concurrent. pens as follows Starting with the master each machine mi independent operations to be applied without blocking. on its turn flushes out all operations in P i as triples of All or nothing semantics are provided for atomic operations. the form hmachineID operationnumber operationi via the using copy on write The first time an object is updated within. Operations channel to all the other machines and then passes an atomic operation a temporary copy of its state is made and. the turn to the next machine i 1 via a confirmation message from then on all updates within the atomic operation are made to. on the Signals channel We will refer to the time instant at this copy If the atomic operation succeeds the temporary state is. which machine mi starts flushing operations as tBeginF lush i copied back to the shared state. and the time instant at which it completes flushing operations as. tEndF lush i In the time interval between tBeginF lush i and Conformance to the operational semantics It can be shown. tEndF lush i the implementation does not allow any new oper that there is a simulation relation between the state transitions in. ations to be issued Therefore at the time instant tEndF lush i the G UESSTIMATE runtime and the rules for operational seman. P i is empty tics in Figure 3 The proof for local operations corresponding to. The number of operations sent on the Operations channel is R1 and issuing composite operations corresponding to R2 are. also sent along with the confirmation message As all machines straightforward For commitment of operations corresponding to. see these confirmation messages and know the number of par R3 the crux of the argument is that even though commitment. ticipating machines they know the number of operations to ex takes several rounds of messages all composite operations sub. pect in Pall i Once confirmation messages from all the par mitted in this duration can be thought of as being submitted ei. ticipants are received the master signals the beginning of the ther before or after the entire commitment operation completes. second stage ApplyUpdatesFromMesh In particular all composite operations issued at machine mi be. fore tBeginU pdate i can be thought of as issued before the atomic. 2 ApplyUpdatesFromMesh Each machine mi waits until it re commit and all composite operations issued at machine mi af. ceives all the expected operations and then applies operations ter tEndU pdate i can be thought of as issued after the atomic. from Pall i to the committed state c i in lexicographic or commit Note that no operations can be issued in the interval. der of the pair hmachineID operationnumber i Once an op tBeginU pdate i tEndU pdate i. eration has been applied it is moved to the Completed list C i. Bounded re executions A salient feature of the implementation is. An operation o in Pall i can update the state of machine that though the operational semantics allows an operation to be ex. mi in one of two ways If the operation o hs ci were ecuted multiple possibly unbounded number of times our imple. submitted by machine mi then o updates c i i to the mentation of the G UESSTIMATE runtime ensures that an operation. value of o c i i If the operation were submitted by is executed at most three times including issue and commit We. some machine j 6 i then o updates c i to s c i Once present an argument for why an operation can execute at most three. machine mi has applied all operations in Pall i it sends an times. acknowledgment on the Signals channel After sending the An operation can be submitted at machine mi either outside the. acknowledgment the guesstimated state on mi namely g i time interval tBeginF lush i tEndU pdate i or within the time. is updated to P i g i to reflect the changes made since interval tEndF lush i tBeginU pdate i note that no operation. the synchronization began This is done by first copying the can be submitted in the intervals tBeginF lush i tEndF lush i. committed state to the guesstimated state by calling Copy and and tBeginU pdate i tEndU pdate i. then applying each operation in P i We will refer to the Suppose an operation o is submitted outside the time inter. time at which machine mi begins copying the committed state val tBeginF lush i tEndU pdate i Then operation o is executed. on to the guesstimated state as tBeginU pdate i and the time at once during issue During the next synchronization the operation. which the last operation from P i has finished updating g i o is guaranteed to get committed because all operations in the. as tEndU pdate i In the time interval between tBeginU pdate i pending list are guaranteed to be committed The operation o is. and tEndU pdate i the implementation does not allow any new executed once again during commit thus executing a total of two. operations to be issued times, 3 FlagCompletion Once the master receives acknowledgments Suppose an operation o is submitted within the time inter. from all the machines the synchronization is complete The val tEndF lush i tBeginU pdate i As before operation o is ex. master can start another synchronization any time after this ecuted once during issue Next at the time tBeginU pdate i op. eration o is part of the pending list P i and all operations that. committed during the current synchronization have updated the. Concurrency control Within the guesstimate runtime concurrent. committed state c i o is executed for the second time some. updates to shared state are possible Fine grained locks are used in. where in the time interval tBeginU pdate i tEndU pdate i to up. ternally by the Synchronizer to avoid races These locks are used. date the guesstimated state and re establish the invariant g i. to ensure the following i operation are queued atomically into the. p c i Finally during the next synchronization the operation. pending list ii in the time interval tBeginF lush i tEndF lush i. o is guaranteed to commit and executes one more time as in the. no operations are issued iii the execution of an operation on. previous case thus executing a total of three times. the guesstimated state happens atomically iv In the time interval. tBeginU pdate i tEndU pdate i no operations are issued v All Entering and leaving the distributed system Machines can dy. reads to shared state enclosed within BeginRead and an EndRead namically enter and leave the distributed system When an appli. are guaranteed to be atomic Note that all these blocking synchro cation written with G UESSTIMATE is started up on a new machine. the G UESSTIMATE runtime adds the machine to the Signals and that during the execution of the method on the guesstimated state. Operations meshes and broadcasts a special message on the sig the user gets a ride on vehicle v3 and by the time the operation is. nals channel The master processes this message before the next committed vehicle v3 is full We have written a predicate GetRide. synchronization and sends the new device both the list of available which is satisfied if the user gets a ride on some vehicle and estab. objects and the list of completed operations The new device ini lished that the implementation GetRide conforms to GetRide using. tializes its state based on these and intimates the master who then Boogie This ensures that as long as GetRide succeeds in the com. begins synchronization A machine that leaves the system intimates mitted sequence the user will have some ride though perhaps not. the master and the master removes this machine from the next syn in the initial vehicle v3 that was obtained during execution on the. chronization onward guesstimated state, This design pattern is easily extended to hierarchical OrElse. Failures and fault tolerance When the master starts a new syn. operations If operations s and t both conform to a specification. chronization phase it assumes all machines are active However if. it can be established that the operation s OrElse t also conforms. the synchronization is stalled for more than a threshold duration. to Thus the programmer can compose several alternatives to. the master goes through the log of messages sent on the signals. achieve a goal using using the OrElse constructor and still re. channel to detect the stalling machine It resends the signal to which. spect this design pattern allowing the flexibility that the operation. the machine failed to respond If the fault were transient the ma. could succeed using one alternative during the execution on the. chine might respond to this resent signal If the machine still does. guesstimated state and another alternative during commitment. not respond the master removes the machine from the current syn. chronization phase and sends it a restart signal On receiving the Completions Writing specifications for each shared operation and. restart signal the machine shuts down the current instance of the checking for conformance greatly simplifies the task of writing. application and restarts the application Upon restart the machine completion routines If we use this discipline then completion. re enters the system in a consistent state routines can be written using the form. Our current implementation is not tolerant to failure of the bool b. master This support can be added by designating a new machine as if b. indicate in UI that the, master if no synchronization messages are received for a threshold operation successfully committed. duration else,indicate in UI that the operation failed. and ask the user to take remedial action,5 Design Patterns.
The two main advantages of programming with G UESSTIMATE Note that the completion routine for the Sudoku application. are simplicity and responsiveness The programming model is very seen in Figure 2 follows this pattern. close to sequential programming in that the programmer creates In essence the above two design patterns split up the respon. shared objects and issues shared operations on them which exe sibility for handling variances between the guesstimated state and. cute synchronously without blocking on the guesstimated state The actual committed state between the programmer and the user The. simple and common case is when the results of the operation dur programmer codes up several alternatives for achieving the goals of. ing the commitment phase are the same as the results obtained from an operation s such that the operation s returns true if any of these. the guesstimated state However the programmer needs to handle alternatives can be executed successfully and ensures that a speci. the case when the two results are indeed different We encountered fication s derived from the goal of the operation holds for each. several such situations in the applications we have written using of these alternatives using static analysis If all the alternatives fail. G UESSTIMATE and we have been able to handle these using a few during commitment the completion routine throws up the problem. design patterns involving specifications completions atomic oper to the user and asks the user to deal with the failure. ations and blocking constructs We describe these design patterns Atomic operations There are two kinds scenarios where we have. below found use for atomic operations The first is obvious when we. Specifications As noted in Section 3 we recommend a program want a set of operations to be executed with all or nothing seman. ming discipline where every shared operation s conforms to a spec tics This happens in our event planning application when a user. ification s recall from Section 3 that s conforming to s wants to sign up for two events or none. means that if s returns true then s respects s and if s returns false The second kind of scenario where we have found use for. then the shared state is unchanged We have written such specifica atomic operations is when there is a value dependency between. tions s using Spec 2 and checked that the body of s conforms operations Suppose we have two operations s and t such that a. to s using the Boogie program verifier 3 location written by s is read or written by t Then there is the pos. Consider a machine mi that executes a sequence of operations sibility that s and t succeed during execution on the guesstimated. s t where each shared operation s conforms to a specifi state and that s could fail during commitment and t could succeed. cation s Suppose all these operations succeed during execution In such situations if the dependence has to be enforced we suggest. on the guesstimated state Suppose also that each of the opera grouping s and t together as a single atomic operation. tions succeeds during commitment we consider the case where. Blocking operations Finally there are certain situations where we. some of these operations fail during commitment later This means. really want to be sure that an operation commits before executing. that the committed sequence of operations could be of the form. subsequent operations We have encountered this situation for in. o11 s o2i t where operations oij submitted by other stance in our event planning application where we first require a. machines are interleaved between the operations s t How user to login and we do not want to allow the user to do anything. ever due to definition of conformance the pre and post states of before we are sure that the login has succeeded. operations s and t in the committed sequence necessarily satisfy We have been able to program such scenarios by blocking the. s and t respectively main thread on issuing the operation and waiting until the comple. For example in our car pool application a method tion routine unblocks it The general template for doing so is as. GetRide Event e searches through various ride sharing options below. to get a ride for the user to attend event e The operation succeeds res IssueOperation loginOperation. if some vehicle has space for the user However it may so happen bool b. if b 1 private void button signin Click object sender EventArgs e. release the thread and allow access 2 string usrnm textBox username Text. else 3 string passwd TextBox password Text, release the thread and deny access 4 sharedOp op Guesstimate CreateOperation handle usrnm passwd. if res 5 Semaphore s new Semaphore 0 1, block the thread 6 bool res Guesstimate IssueOperation op. In summary we have presented four design patterns that we 8. 9 if b my name username s Release, have found useful in writing G UESSTIMATE applications Our ex 10 else. perience is that the above design patterns provide simple ways to 11 register failed r new register failed. handle common situations that arise in programming collaborative 12 r ShowDialog s Release. applications using G UESSTIMATE 13,6 Experience 16 if res. 17 this Close, We have built 6 collaborative applications using the G UESSTIMATE 18 else.
programming model These are a collaborative multi player Su 19 this Cursor Cursors WaitCursor. doku puzzle an event planning application a message board appli 20 s WaitOne. 21 this Cursor Cursors Default, cation a car pool system an auction system and a small scale twit 22 this Close. ter application In all these applications the shared state and shared 23. operations are encapsulated together in a shared object class This 24. class derives from the abstract base class GSharedObject exposed. through G UESSTIMATE and implements a copy method For exam Figure 4 Sample code to implement a blocking operation. ple the Sudoku class contains a 9x9 array and an update operation. that form the shared data and operation respectively It also imple. ments a copy method that when passed a source object copies the not see updates from operations submitted elsewhere In our final. 9x9 array from the source to the this object At a high level the design we choose to call refresh based on user activity Every time. rest of the application design typically involves having to call ap the user moves the mouse around on a grid or the grid comes to the. propriate API functions to create new instances of shared objects fore refresh is called So as long as the user is active the display is. and issue operations based on user interaction All applications are kept up to date Our user experience study suggests that this is an. written with about 500 700 lines of code Below we share our ex effective solution Additional API support that provides a call back. perience in developing these applications using G UESSTIMATE by for changes to a shared object via remote operations could provide. highlighting some interesting design decisions that we made an alternate solution. Updating local state While the shared state is kept globally con Blocking via completion operations In five of the applications. sistent and up to date by the runtime the programmer has to en all but Sudoku we needed to implement two functionalities signin. sure that the local state is kept up to date The state used by the and new user registration as blocking functions New user registra. GUI has to not only be updated in response to user actions but tion is made blocking to ensure that the same username is not si. also in response to synchronizer events and this can be done us multaneously registered at two machines And we choose to make. ing G UESSTIMATE s completion operations signin blocking to ensure that a user is signed in only on one ma. Designing completion operations correctly for the multi player chine at a time. Sudoku was challenging Our first design of the GUI was as de Blocking is implemented as shown in Figure 4 by waiting on. scribed in Section 2 where initially when an operation is submitted a semaphore until the completion operation releases it Here the. the color of the square is changed to yellow and later depending login operation is created in line 4 and issued in line 6 If the. on success or failure the color is changed to green or red respec result of the IssueOperation is true then the issuing thread. tively However this design differentiated successful operations of simply waits on semaphore s at line 20 The wait is released by the. the current user from the successful operations done by other users completion routine executing s Release in line 9 Apart from. and our users did not like this distinction Ultimately we chose to these two functionalities the rest of the operations in all applications. remove the green color all together and depict all successful op are better suited to a non blocking design. erations from all users uniformly Thus we decided to use special. Atomic and OrElse Operations Atomic operations and OrElse. markings only for tentative operations and failing operations When. operations are used extensively in the event planner application. an operation succeeds at commit time we use the completion op. Users can choose to join one among many events and we im. eration to remove tentative markings, plemented this using an OrElse operation Atomic operations are. Another interesting design decision was with regards to refresh. used when a user wants to perform multiple operations with all or. ing the GUI In most applications the GUI displays only user spe. nothing semantics for example a user chooses to go to a party only. cific information in detail while displaying other information only. if she also gets a ride to the party Atomic operations are also used. on demand For example in event planner the list of activities. when there is a value dependence via the shared state In the event. joined by the user is always on display and is kept up to date via. planner a request to join an event can fail either because there is no. completion operations On the other hand information regarding va. more vacancy in the event or because the user has already joined. cancy status of events is not displayed unless asked for Therefore. the maximum allowed events In case a user wants to join an im. it is often sufficient to frequently refresh only the user specific state. portant event eventa but cannot because she is already used her. of the GUI while updating other state less frequently Completion. quota she might want to leave some other event eventb and join. operations are well suited to do this, eventa However she wants to retain eventb unless she can join. The one exception we found is in Sudoku where it is essential. eventa for sure We use Atomic operations to ensure that such de. for updates from other users to reflect on the grid as and when they. pendencies are respected during execution, happen In our initial design the grid was refreshed every time the. user submitted an operation and every time a completion operation Specifications and contracts We designed all classes that imple. was run However this alone was not sufficient The user often did ment GSharedObject in Spec Specifications of two kinds were. useful Method contracts were used to specify that when a shared Synchronization time Figure 5 plots the distribution of the time. operation returns false no updates are made to the shared state and taken for synchronizations over a long run of the application in. when it returns true changes are made only to the relevant parts volving 8 users solving 2 Sudoku grids It can be seen that the time. Object invariants were used to express that both the state before taken by guesstimate to complete a synchronization is within 0 5. and after a method satisfy the object invariant seconds most of the time There are 2 outliers in the distribution. Spec translates contracts into a set of assertions and uses Boo where a synchronization takes more than 12 seconds These corre. gie to statically verify these assertions Boogie classifies assertions spond to the times when synchronization stalled and the master had. into provably correct assertions provably failing assertions these to perform a fault recovery However owing to the non blocking. are flagged as warnings at compile time and other assertions which nature of guesstimate even during these times the user could con. cannot be proven statically Spec translates the last category of as tinue performing operations Any blocking implementation would. sertions into checks and throws up a warning if there is a violation have rendered the system unresponsive at these times. at runtime Programming with Spec helped us in a few occasions. to catch bugs in our application logic For example the Sudoku. grid row check had an off by one error in array indexing which was. caught with the aid of Spec For our final version of Sudoku with. contracts Spec generated 323 assertions out of which boogie was. able to verify 271 as correct while the remaining 52 were translated. into runtime checks, Maintaining local state All updates to shared state happen via.
G UESSTIMATE and are internally protected by locks from within. the G UESSTIMATE runtime However ensuring that updates to. local state are protected by locks is the programmers responsibility. Particularly as both completion operations and local operations. can update local state all state accessed within completion. operations must be synchronized appropriately For example. in the event planner application both the local operations that. mark tentative changes and the completion operations update a Figure 6 Average time to synchronize vs number of users. tentative joined list Care must be taken to protect this list. with a lock Figure 6 shows the impact of number of users on synchroniza. tion time both in the presence and absence of user activity The. In our experience we find that the non blocking nature of average synchronization time is measured by ignoring the outliers. G UESSTIMATE is well suited to programming collaborative dis time 12 seconds as including them would skew the average. tributed applications In the rare cases that blocking operations are away from the median Two interesting observations can be made. required they can implemented as shown in Figure 4 from this plot First the plot indicates that presence or absence of. user activity does not affect the synchronization time by much This. 7 Performance Evaluation indicates that the dominant component of the time for synchroniza. tion is network delay, In this section we report the performance of the G UESSTIMATE Second it can be seen that the time for synchronization in. runtime in terms of the time it takes for each synchronization all creases linearly with number of users This can be attributed to. three stages put together to complete We also study the scalability the serial nature of the first stage AddUpdatesToMesh of syn. of applications written with guesstimate by measuring how increas chronization refer to Section 4 However even assuming a linear. ing the number of users impacts i the synchronization time and ii increase guesstimate should easily scale to a 100 users as even with. the number of conflicts All measurements were made while run 100 users the average time to synchronize would be within 3 sec. ning the Sudoku application with 2 to 8 users within a local area onds This is reasonable even for a high user activity event like a. network over a one hour time period We chose to use Sudoku as multi player game but possibly not for a highly sophisticated real. the test application since we could get several volunteers to use it time game For collaborative applications which do not have such. with concurrent user activity high user activity guesstimate in its current form should scale to. a 1000 users To scale it further we would have to parallelize the. first stage which should also not be very hard In our current de. sign the first stage is kept serial purely for ease of monitoring and. Conflicts Figure 7 shows the number of instances when an oper. ation that succeeded on issue failed at commit time during our ex. periments These measurements were made by adding a new user. for every 100 synchronizations performed by the runtime As can. be seen conflicts are very rare even the presence of 8 active users. Failure and recovery During the one hour period for which we. gathered statistics G UESSTIMATE encountered three failures once. when one of the machines was restarted while the application was. running and twice when the synchronization was stalled possibly. because a message was lost in transmission G UESSTIMATE recov. ered in all three cases automatically once by resending the lost. Figure 5 Distribution of time taken for synchronization message and twice by removing the machine from the stalled syn. soon as they are submitted Operations received from other replicas. are suitably transformed before being applied so that their seman. tic effect is preserved While this is well suited for text applications. where transformations can be carefully defined writing such trans. formers is hard for other applications Some of the design principles. of G UESSTIMATE like replication availability and conflict resolu. tion are also used in the design of replicated and distributed file. systems such as Unison 13 Coda 15 and GFS 8, Mace is a language extension for C that allows the program. mer to specify components of a distributed system in the form of. a state transition model and transforms them into a C imple. mentation Mace also enables the use of code profilers and model. checkers to help identify performance and correctness errors in dis. tributed applications G UESSTIMATE on the other hand provides. specific support for the development of interactive applications and. Figure 7 Number of conflicts vs number of users chooses a particular design point in the performance consistency. trade off that is well suited to such applications Other languages. like X10 6 target distributed systems with a partitioned global ad. chronization loop and sending a restart message and none of the dress space Extensions to software transactional memory that scale. other users were even aware of the failure to distributed systems with a partitioned global address space have. also been proposed 5 G UESSTIMATE is not restricted to any par. 8 Related Work ticular distributed system architecture. In summary the twin goals of providing a performance. Distributed systems have existed for several decades now Early re consistency trade off that is well suited to collaborative applica. search on consistency guarantees for data shared across distributed tions and a programming API that allows the programmer to build. systems was from the database community 4 The notions of such applications sets G UESSTIMATE apart from existing work. replicated databases with one copy serializability was introduced. One copy serializability allows for pessimistic replication as the. replicas are kept consistent at all times These systems guaran 9 Limitations and Future Work. tee high consistency but can lead to low performance and avail G UESSTIMATE has several limitations We list them below together. ability 16 Optimistic replication on the other hand allows for with some directions for future work. higher availability and faster performance than pessimistic repli. cation However the replicas can diverge and safeguards need to Modularity and layering Applications are often written in a lay. be provided to ensure that some form of consistency is guaran ered fashion While we have abundant experience using G UESSTI. teed Systems with optimistic replication typically guarantee even MATE to write applications in which the user directly interacts with. tual consistency 14 the API via a user interface we do not know if we can develop. Many systems have been built for mobile and Internet services multi layered software with it. that support optimistic replication with an eventual consistency. guarantee The work most closely related to the guesstimate sys Size of shared state G UESSTIMATE maintains multiple copies of. tem is the mobile database system Bayou 12 Bayou replicates the shared state and copies the committed state to the guesstimated. a database on multiple servers and allows clients to submit SQL state at the end of each synchronization Dealing with large shared. like queries to the database This query is processed in one server objects could therefore slow down guesstimate However optimiz. and then propagated across to other servers using pairwise entropy ing copy on write has been studied in several contexts such as. It allows for specification of per write merge functions to resolve STMs 1 and by using programming language features to inform. conflicts Bayou relies on features in the database storage system the runtime about side effect free code and optimize copying in. to log all operations on the database and to rollback and re execute such situations. them multiple times so that all servers see operations in the same. Updating local state With G UESSTIMATE updating the local state. order Little is known about the way to program applications for. whenever changes are made to shared state still remains the pro. Bayou G UESSTIMATE differs in that it provides a well defined. grammer s responsibility Completion operations provide one way. API to build applications for distributed systems It also does not. to update local state but these do not handle updates from remote. need any guarantees from the underlying storage system Unlike. operations A mechanism to register a callback function for remote. Bayou G UESSTIMATE maintains all state in memory In addition. updates could prove useful, to OrElse operations that are similar to the merge functions de. fined in Bayou G UESSTIMATE provides completion operations to Scalable run time As mentioned in Section 7 the current version. notify application users about conflicts Further it allows users to of G UESSTIMATE might not scale beyond 1000 nodes as the syn. naturally express related operations as Atomic operations chronization time increases linearly with number of users While. The IceCube system 10 allows for users to specify constraints the non blocking nature of G UESSTIMATE ensures that users are. on the order in which operations should be executed Constraints not blocked during synchronization slow synchronization affects. like either op1 or op2 should be performed and op1 should only be the lag between submission and completion and hence affects user. performed if op2 is performed can be specified The final commit experience One possibility is to parallelize the first stage of the. order can then be any order that satisfies all constraints G UESSTI synchronization protocol so that the time taken depends only on the. MATE respects the natural or causal ordering between operations number of operations and the network delay but not on the number. submitted by the same user In addition it allows for hierarchical of users. operations, Operational transformation 7 is a technique used for building Fault tolerance While the current version of G UESSTIMATE tol. collaborative applications that allows operations to be committed as erates some faults since it is designed as a single master system. the master remains a single point of failure One possibility is to ex 15 M Satyanarayanan The evolution of coda ACM Trans Comput. tend the implementation to dynamically change the master in case Syst 20 2 2002. the master fails 16 Haifeng Yu and Amin Vahdat The costs and limits of availability for. replicated services In SOSP 01 Symposium on Operating systems. Off line updates G UESSTIMATE does not currently support off principles 2001. line updates Adding such support could be non trivial in the sense. that if the time gap between the executions on the guesstimated and. committed states is large the scope for discrepancy and conflicts. also becomes large,ACKNOWLEDGMENTS, We thank Jim Larus Dave Detlefs Dave Campbell Anders.
Hejlsberg Rama Ramasubramanian Sanjiva Prasad and the anony. mous reviewers for their insightful comments on earlier drafts of. this paper,References, 1 Ali Reza Adl Tabatabai Brian T Lewis Vijay Menon Brian R. Murphy Bratin Saha and Tatiana Shpeisman Compiler and runtime. support for efficient software transactional memory In PLDI 06. Programming language design and implementation 2006. 2 Mike Barnett K Rustan M Leino K Rustan M Leino and Wolfram. Schulte The spec programming system An overview In CASSIS. 04 Construction and Analysis of Safe Secure and Interoperable. Smart Devices 2004, 3 Mike Barnett Bor yuh Evan Chang Robert Deline Bart Jacobs and. K Rustanm Leino Boogie A modular reusable verifier for object. oriented programs In FMCO 05 Formal Methods for Components. and Objects 2006, 4 Philip A Bernstein Vassos Hadzilacos and Nathan Goodman. Concurrency Control and Recovery in Database Systems 1987. 5 Robert L Bocchino Vikram S Adve and Bradford L Chamberlain. Software transactional memory for large scale clusters In PPoPP. 08 Principles and practice of parallel programming 2008. 6 Philippe Charles Christian Grothoff Vijay Saraswat Christopher. Donawa Allan Kielstra Kemal Ebcioglu Christoph von Praun and. Vivek Sarkar X10 an object oriented approach to non uniform. cluster computing In OOPSLA 05 Object oriented programming. systems languages and applications 2005, 7 C A Ellis and S J Gibbs Concurrency control in groupware. systems In SIGMOD 89 SIGMOD international conference on. Management of data 1989, 8 Sanjay Ghemawat Howard Gobioff and Shun Tak Leung The.
google file system In SOSP 03 Symposium on Operating systems. principles 2003, 9 Maurice P Herlihy and Jeannette M Wing Linearizability a. correctness condition for concurrent objects ACM Trans Program. Lang Syst 12 3 463 492 1990, 10 Anne Marie Kermarrec Antony Rowstron Marc Shapiro and Peter. Druschel The icecube approach to the reconciliation of divergent. replicas In PODC 01 Principles of distributed computing 2001. 11 Leslie Lamport How to make a multiprocessor computer that. correctly executes multiprocess programs IEEE Trans Computers. 12 Karin Petersen Mike Spreitzer Douglas Terry and Marvin Theimer. Bayou replicated database services for world wide applications In. EW 7 Proceedings of the 7th workshop on ACM SIGOPS European. workshop 1996, 13 Benjamin C Pierce and Je ro me Vouillon What s in Unison A formal. specification and reference implementation of a file synchronizer. Technical Report MS CIS 03 36 Dept of Computer and Information. Science University of Pennsylvania 2004, 14 Yasushi Saito and Marc Shapiro Optimistic replication ACM.

Related Books

COMM 1110 PUBLIC SPEAKING - University of West Georgia

COMM 1110 PUBLIC SPEAKING University of West Georgia

Introduction to Public Speaking August 21-23 Introductory Speeches Overview of the Communication Process Homework: TBA Chapters 2, 3 and 5 Overview of the Speechmaking Process Ethics and Free Speech Analyzing your Audience August 22 - 24 The Informative Speech Audience Analysis Developing the Central Idea and Purposes The Speech Outline Homework: TBA Chapters 6, 7, 11 and 15 Gathering Support ...

The Business Case for Protein Diversification

The Business Case for Protein Diversification

the top 100 restaurants increased their meat alternative offerings between 2017 and 2018.4. The Business Case for Protein Diversiffication 4 Increased foot traffic Many restaurants are reporting that diversifying protein options attracts new customers. During testing, Burger King locations selling the Impossible Whopper saw foot traffic soar by 18.5%, while foot traffic at its other U.S ...

Error Analysis and Statistics for Students in Introductory ...

Error Analysis and Statistics for Students in Introductory

7 How representative of the lawn is the sample area ? Need to take more samples in different areas of the lawn to find the difference between

Video-based Reconstruction of Animatable Human Characters

Video based Reconstruction of Animatable Human Characters

Video-based Reconstruction of Animatable Human Characters Carsten Stoll MPI Informatik Juergen Gally ETH Zurich Edilson de Aguiarz Disney Research Sebastian Thrunx Stanford University Christian Theobalt{MPI Informatik Figure 1: Frames of a real-time animation that was created with a fully-animatable character model that we reconstructed from multi-view video. An animation artist created a new ... Glenn Fabry 2008

www glennfabry co uk Glenn Fabry 2008

Glenn Fabry June 2008 slaine 2 Early work 3 Hellblazer 5 Graphic Novels 7 Games & cards 9 Preacher 11 Endless Nights 13 Other Projects 13 neverwhere 15 Anatomy Books 17 Figurines 17 authority 17 Work so far 18 Contact 20 Glenn Fabry Studios 116 Rodmell Avenue,

UV / EB radcure Product Guide -

UV EB radcure Product Guide 7577748 s21d 7 faiusrd com

UV / EB radcure Product Guide Version 5.1 2014 DISCLAIMER The information and recommendations provided in this product catalogue are presented in good faith and believed to be correct. IGM Resins makes no representations or warranties as to the completeness or accuracy of the information provided. The information is provided on the condition that the persons receiving it will make their own ...

Bibliography: CDA, Discourse Analysis & Pragmatics

Bibliography CDA Discourse Analysis amp Pragmatics

Bibliography: CDA, Discourse Analysis & Pragmatics Compiled by Melonie Fullick (2013) Agger, B. (1992). The discourse of domination: from the Frankfurt School to postmodernism. Evanston: Northwestern University Press. Althusser, L. (1971). Ideology and ideological state apparatus: Lenin and philosophy. London: New Left Books. Alvesson, M. & Karreman, D. (2000). Varieties of discourse: On t

Contents - TAFE NSW

Contents TAFE NSW

Office 2016 (or 2013, 2010) Depending on your course, you may need some or all the following Microsoft applications on your computer so that you can download some or all of the following file types. Microsoft Word Microsoft PowerPoint . TAFE Digital - Online Learning Support - FAQ 3 | P a g e Uploading to the OLS Overview Your assessments are located under the Assessments tab for each unit ...

Fiber-Optic Communication Systems - Optiwave

Fiber Optic Communication Systems Optiwave

Optical Receiver Communication Channel Electrical Input Electrical Output Transmitter and Receiver Modules Optical Source Optical Modulator Driving Circ uit Modul ator Electroni cs Electrical Input Optical Output Photodetector E le ctri a Dem odulat r r ivng C irc t Dem odul t r Ele troni s Electrica l Outpu t Optic l Inp t Fiber-Optic Communication Channel. 7/66 JJ II J I Back Close ...

non-destructive Testing Techniques: Leak Testing at Level 2

non destructive Testing Techniques Leak Testing at Level 2

non-destructive Testing Techniques: Leak Testing at Level 2 Vienna, 2012 Training g uidelines in n on-destructive Testing Techniques: Leak Testing at Level 2 Training Course s eries 52. Training Guidelines in Non-destructive Testing Techniques: Leak Testing at Level 2 . AFGHANISTAN ALBANIA ALGERIA ANGOLA ARGENTINA ARMENIA AUSTRALIA AUSTRIA AZERBAIJAN BAHRAIN BANGLADESH BELARUS BELGIUM BELIZE ...