Background: Not all machines support the same data formats. For example, the DEC Alpha and Intel 80x86 families pack bytes into words in little-endian order, while the Sun SPARC packs bytes into words in big-endian order. IBM mainframes still use the EBCDIC character set instead of ASCII, and while the IEEE floating point format is emerging as a standard, many machines still use other proprietary formats.
The Problem, part A: Does the ISO OSI protocol hierarchy address this problem? If so, at what level?
The Problem, part B: In the context of an RPC relationship between client and server, where should any data format conversion required be done?
The diameter of a network is the longest shortest path in the network. That is, if the length (in point-to-point hops) of the shortest path between i and j is L_{i,j}, then the diameter of the network is max_{i,j}(L_{i,j}).
Our clocks are not perfect. Some run slightly fast, and some slightly slow. The maximum rates of clock drift is .01 second per second.
The Problem, part A: Given that the network has diameter 10, what is the maximum difference that you could observe between any two clocks in the network.
The Problem, part B: Given that individual clock drift rates are randomly distributed over the allowable range of drift rates, what accuracy would you expect of the composite clock, assuming that there were 100 clocks in the network.
For this problem, assume point-to-point communications and assume that no knowledge of the network topology is available. Also, assume that you are not free to change the basic synchronization algorithm, but that you are able to optimize it by such means as maintaining local information about the state of remote processes. Note that the relevant state information includes both information about the variables N and C for each process, but also the state of that process (outside, selecting N, waiting entry, inside). Assume that messages are never lost and that processes never die.
The problem: Optimize Lamport's algorithm for the network context.
The problem, part A: Explain why some mutual exclusion algorithms can be modified to construct election algorithms, while others cannot. Again, short answers are required!