1. Q: Give an example of where an address of an entity Eneeds to be further resolved into another address to actuallyaccess E.
A: IP addresses in the Internet are used to address hosts.However, to access a host, its IP address needs to be resolved to,for example, an Ethernet address.
2. Q: Would you consider a URL such ashttp://www.acme.org/index.html to be location independent? Whatabout http://www.acme.nl/index.html?
A: Both names can be location independent, although the firstone gives fewer hints on the location of the named entity. Locationindependent means that the name of the entity is independent of itsaddress. By just considering a name, nothing can be said about theaddress of the associated entity.
3. Q: Give some examples of true identifiers.
A: Examples are ISBN numbers for books, identification numbersfor software and hardware products, employee numbers within asingle organization, and Ethernet addresses (although someaddresses are used to identify a machine instead of just theEthernet board).
4. Q: How is a mounting point looked up in most UNIXsystems?
A: By means of a mount table that contains an entry pointingto the mount point. This means that when a mounting point is to belooked up, we need to go through the mount table to see which entrymatches a given mount point.
5. Q: Jade is a distributed file system that uses per-username spaces (see In other words, each user has his own, privatename space. Can names from such name spaces be used to shareresources between two different users?
A: Yes, provided names in the per-user name spaces can beresolved to names in a shared, global name space. For example, twoidentical names in different name spaces are, in principle,completely independent and may refer to different entities. Toshare entities, it is necessary to refer to them by names from ashared name space. For example, Jade relies on DNS names and IPaddresses that can be used to refer to shared entities such as FTPsites.
6. Q: Consider DNS. To refer to a node N in a subdomainimplemented as a different zone than the current domain, a nameserver for that zone needs to be specified. Is it always necessaryto include a resource record for that server’s address, or is itsometimes sufficient to provide only its domain name?
A: When the name server is represented by a node NS in adomain other than the one in which N is contained, it is enough togive only its domain name. In that case, the name can be looked upby a separate DNS query. This is not possible when NS lies in thesame subdomain as N, for in that case, you would need to contactthe name server to find out its address.
7. Q: Is an identifier allowed to contain information onthe entity it refers to?
A: Yes, but that information is not allowed to change, becausethat would imply changing the identifier. The old identifier shouldremain valid, so that changing it would imply that an entity hastwo identifiers, violating the second property ofidentifiers.
8. Q: Outline an efficient implementation of globallyunique identifiers.
A: Such identifiers can be generated locally in the followingway. Take the network address of the machine where the identifieris generated, append the local time to that address, along with agenerated pseudo-random number.
Although, in theory, it is possible that another machine inthe world can generate
the same number, chances that this happens arenegligible.
9. Q: Give an example of how the closure mechanism for aURL could work.
A: Assuming a process knows it is dealing with a URL, it firstextracts the scheme identifier from the URL, such as the stringftp:. It can subsequently look up this string in a table to find aninterface to a local implementation of the FTP protocol. The nextpart of the closure mechanism consists of extracting the host namefrom the URL, such as www.cs.vu.nl, and passing that to
the local DNS name server. Knowing where and how to contactthe DNS server is an important part of the closure mechanism. It isoften hard-coded into the URL name resolver that the process isexecuting. Finally, the last part of the URL, which refers to afile that is to be looked up, is passed to the identified host. Thelatter uses its own local closure mechanism to start the nameresolution of the file name.
10. Q: Explain the difference between a hard link and asoft link in UNIX systems.
A: A hard link is a named entry in a directory file pointingto the same file descriptor as another named entry (in possibly adifferent directory). A symbolic link is a file containing the(character string) name of another file.
11. Q: High-level name servers in DNS, that is, nameservers implementing nodes in the DNS name space that are close tothe root, generally do not support recursive name resolution. Canwe expect much performance improvement if they did?
A: Probably not: because the high-level name serversconstitute the global layer of the DNS name space, it can beexpected that changes to that part of the name space do not occuroften. Consequently, caching will be highly effective, and muchlong-haul communication will be avoided anyway. Note that recursivename resolution for low-level name servers is important, because inthat case, name resolution can be kept local at the lower-leveldomain in which the resolution is taking place.
12. Q: Explain how DNS can be used to implement ahome-based approach to locating mobile hosts.
A: The DNS name of a mobile host would be used as (ratherpoor) identifier for that host. Each time the name is resolved, itshould return the current IP address of the host. This implies thatthe DNS server responsible for providing that IP address will actas the host’s name server. Each time the host moves, it contactsthis home server and provides it with its current address.
Note that a mechanism should be available to avoid caching ofthe address. In other words, other name servers should be told notto cache the address found.
13. Q: A special form of locating an entity is calledanycasting, by which a service is identified by means of an IPaddress (see, for example, Sending a request to an anycast address,returns a response from a server implementing the serviceidentified by that anycast address. Outline the implementation ofan anycast service based on the hierarchical location servicedescribed in Sec. 4.2.4.
A: Each service has a unique identifier associated with it.Any server implementing that service, inserts its network-leveladdress into the location service at the directory node of the leafdomain in which the server resides. Lookup requests use theidentifier of the service, and will automatically return thenearest server implementing that service.
14. Q: Considering that a two-tiered home-based approach isa specialization of a hierarchical location service, where is theroot?
A: The root is formed jointly by all home locations, but ispartitioned in such a way that each mobile entity has its own rootserver.
15. Q: Suppose it is known that a specific mobile entitywill almost never move outside domain D, and if it does, it can beexpected to return soon. How can this information be used to speedup the lookup operation in a hierarchical locationservice?
A: Simply encode the domain D in the identifier for the entitythat is used for the lookup operation. The operation can then beimmediately forwarded to the directory node dir(D), from where thesearch continues.
16. Q: In a hierarchical location service with a depth ofk, how many location records need to be updated at most when amobile entity changes its location?
A: Changing location can be described as the combination of aninsert and a delete operation. An insert operation requires that atworst k +1 location records are to be changed. Likewise, a deleteoperation also requires changing k +1 records, where the record inthe root is shared between the two operations.
This leads to a total of 2k +1 records.
17. Q: Consider an entity moving from location A to B,while passing several intermediate locations where it will residefor only a relatively short time. When arriving at B, it settlesdown for a while. Changing an address in a hierarchical locationservice may still take a relatively long time to complete, andshould therefore be avoided when visiting an intermediate location.How can the entity be located at an intermediatelocation?
A: Combine the hierarchical location service with forwardingpointers. When the entity starts to move, it leaves behind aforwarding pointer at A to its next (intermediate) location. Eachtime it moves again, a forwarding pointer is left behind. Uponarrival in B, the entity inserts its new address into thehierarchical location service. The chain of pointers issubsequently cleaned up, and the address in A is deleted.
18. Q: When passing a remote reference from process P1 toP2 in distributed reference counting, would it help to let P1increment the counter, instead of P2 ?
A: No, because in that case, process P2 may decide toimmediately remove its reference before P1 has a chance toincrement the counter at the object. Consequently, when P2 sendsits decrement message, the counter may drop to zero and the objectmay be incorrectly removed.
19. Q: Make clear that weighted reference counting is moreefficient than simple reference counting. Assume communication isreliable.
A: Creation or removal of reference can be done with only asingle message, as is also the case with simple reference counting.Passing a reference is much cheaper, as it can be done with onlyone message containing the copied reference with its partial weightset to half of the weight of the original reference. There is thusno need to contact the object, in contrast to simplereference
counting.
20. Q: Is it possible in generation reference counting,that an object is collected as garbage while there are stillreferences, but which belong to a generation the object does notknow of?
A: No. Whenever a reference of generation k is removed (sothat possibly the associated entry in G[k ] becomes zero), theobject is always informed about any outstanding references ofgeneration k +1. If that generation was not yet known to theobject, it will be at the time a reference of generation k isremoved.
21. Q: Is it possible in generation reference counting,that an entry G[i ] becomes smaller than zero?
A: Yes. Suppose a reference of generation k is copied, leadingto a reference of generation k +1. If the latter is removed beforethe reference from which it was copied, G[k +1] will be decrementedby one. If no reference of generation k had yet been removed, G[k+1] will then drop below zero.
22. Q: In reference listing, if no response is receivedafter sending a ping message to process P, the process is removedfrom the object’s reference list. Is it always correct to removethe process?
A: No. It may be possible that the process is temporarilyunreachable due to a network partition, for example, caused by afailing router or gateway. In that case, the reference is lost andthe skeleton may falsely decide that the object can be removed ifthe list becomes empty.
23. Q: Describe a very simple way to decide that thestabilization step in the tracing-based garbage collector of Langet al. has been reached.
A: Assume that each process can decide whether its localgarbage collector has changed any of the markings on proxies orskeletons during the local propagation step. A very simple,nonscalable solution, is to report whether or not any changes havebeen made to a central coordinator. As soon as that coordinator hasrecorded that no more changes have occurred, it tells eachprocess
to start reclaiming garbage.