Answer to CS5204 Homework #3
Due: Sept 23, 1999
1. (4 points) One aspect of a remote procedure call or a remote invocation is representing the arguments being passed from the client to the server or the results returned to the client by the server as a linear byte stream suitable for transmission over a network. The term serialization or marshalling is used to refer to the process of converting the arguments or returned result from possibly complex objects into a linear form by the sender and accurately reconstructing the objects from the data stream by the receiver. Consider a remote invocation that involves an array such as:
T x[10]; // an array of 10 elements of type T
remoteObject.meth(x); // invoke the method "meth" on the remote object
// passing the array "x" as an input argument
Assuming that values of the base type of the array (the type T in the above example) can be converted to a byte stream, how can the array of these values be represented? To answer this question show two different ways in which the array can be serialized. Be sure that your answer shows how the length of the array is represented and how undefined array elements are handled.
Answer:
We can have the first byte (or word) of that stream represent the size of the array, followed by a list of actual array elements. This is illustrated in (Fig 1).
Another way of representation is to use a special terminate symbol, an equivalence of the NULL in ASCIIZ scheme. Of course, you have to guarantee that this special value will not be any possible valid value in your base type. This is illustrated in (Fig 2).
To distinguish undefined elements in an array, you need design a tag field before the value of an element. If the tag contains a "1", the followed value is valid. Otherwise, it is an undefined element in the array. Of course, you can also use a special symbol to fill in all the undefined elements in the array.
2. (2 points) The C-Linda program on page 450 of the "Linda in Context" paper is incorrect. Identify and correct the mistake.
Answer:
The client’s second ‘out’ operation should have "request" other than "server" as its first element.
3. (4 points) Show how to represent a linked list data structure in a tuple space. Your representation must be able to support typical linked list operations such as traversal of the list, and insertion and deletion of elements. You need to describe the representation and give a simple example.
Answer:
First, we need a structure to identify the head of a list:
(list_name, ID)
where list_name is the name of that list and ID is the index value of the first tuple in the list.
The linked list can have following structure:
(list_name, ID, value, ID_NEXT)
where ID_NEXT indicates the next element’s ID value. If the tuple is the tail of a list, it’s ID_NEXT should be some special value (e.g. –1) to convey the information that this is the end of a list. Now we discuss how can we implement typical list operations on such kind of data structure.
Now we will show algorithms below that are not required parts of the answer.
Traversal:
Given an ID of the head of a list, we can traverse the whole list.
1 CurId = ID
2 While (CurId != TERMINITE)
3 {
4 rd(CurId, ?value, ?NextId);
5 access(value);
6 CurId = NextId;
7 }
We access the value of a tuple at line 5 above. And TERMINITE at line 2 is the special symbol denoting the end of a list.
Insertion:
Given an ID of a tuple, we can insert a new tuple with value VALUE after it in the list:
1 in(ID, ?OldValue, ?NextId);
2 NewId = generate_an_ID();
3 out(ID, OldValue, NewId);
4 out(NewId, VALUE, NextId);
This code segment does not consider concurrent access to the list. In such a situation, mechanism for mutual exclusion should be added.
Deletion:
If we want to delete a tuple with index value ID in the list, we need first to know its predecessor’s index in the list, just as things go with the ordinary list.
1 in(?PreIndex, ?value, ID);
2 in(ID, ?temp, ?NextId);
3 out(PreIndex, value, NextId);