Session Chair

Jean Bacon is a lecturer at the University of Cambridge Computer Laboratory. She is the author of "Concurrent Systems", Addison Wesley 1993. Her research interests include distributed systems, multimedia systems and storage service architectures.

M. van Steen, A. Tanenbaum, I. Kuz and H. Sips
Vrije University, The Netherlands

Presented by Maarten van Steen

The current performance problems experienced on the world wide web could be considered to be scalability problems. These performance problems could be resolved by using replication mechanisms. However replication in turn introduces it's own problems, namely: what needs to be cached, where should it be placed and who is in control? The development of coherence models represents a solution. Maarten identified that different documents can do with different coherence. Also different documents have different protocol requirements so "no one size fits all". He then went on to describe The Globe Approach which uses distributed shared objects physically distributed across multiple machines. This involves full encapsulation including object specific policies for replication migration and security. This means that only basic common sevices such as naming and location need to be provided.

The middleware layer can be built on top of existing network infrastructures such as TCP/IP. This differs from normal approaches to distributed objects. A number of diagrams were shown, illustrating the invocation of a thread on an interface by a client object which in turn invokes a local object. The developer should construct Web pages as normal and then collect them in a state archive where a subdirectory structure is maintained. There is no need for fancy things, ie: symslinks and code is collected into a class archive.

The speaker concluded by describing a prototype system which had been built for the purposes of feasibility checking. He also described ongoing work to develop a generic global document web proxy that can talk to most web browsers and support global web documents. In the near future work on replication strategies and secure global servers would be carried out.

One question was forthcoming from the floor: This solution involves embedding replication strategy within documents, but the required replication strategy may be dependent on my needs not yours. How does the architecture deal with this? Maarten replied that the replication strategy may be layered so the document strategy may be overidden by the network. Thus, the strategy will not be the same for all times and places.

R. van Renesse, Y. Minsky and M. Hayden
Cornell University, USA

Presented by Robbert van Renesse

Acute failure detection is difficult if not impossible in a distributed network. However, the problem can be simplified if mistakes can be allowed. Failure detection is useful for system administration, replication, load balancing and group communication. Existing failure detectors are not reliable. A list of desirable properties for failure detectors was given.

In the Gossip model each member maintains a list of addresses and heartbeat pairs. Periodically each member gossips by incrementing it's own heartbeat and sending the list to a randomly chosen member. The absence of an increment indicates failure. However the gossip message grows linearly with time, resulting in a linear slow down. Some equations formulating this performance were shown, as were graphs illustrating performance. The result is that gossips can overload network. This can be resolved by adopting a multi level protocol. The solution is to gossip mostly within subnet of the host which is gossiping and only occasoonally within the whole domain.

The relationship between subnet and domain gossips was described. This results in the generation of broadcasts with high probability at least every 60 seconds and on average every 30 seconds, each broadcast carrying part of the membership list. Several graphs showing performance results were shown.

There were a few questions. firstly, how does each member decide which subnet to broadcast to? The answer was that if the member has not heard a message within 30 seconds the probability of transmision goes up. When the transmission occurs it goes to every subnet that it's ever heard of. The next question was what happens if machine goes down and up before noticed? Robbert replied that this does happen. Finally, it was queried that advertised products quote failure detection times of 30 seconds. Protocols can detect faster, but OS's block detection. Can this system overcome this? Robbert's reply was that the longest delay encountered when pinging was 300 milliseconds, so this is not problem in Solaris.

Y. Chawathe and E. Brewer
University of California at Berkeley, USA

Presented by Yatin Chawathe

The motivation for the work was given as proliferation of network based services. As this took place some critical issues emerged: incremental and linear system scalability, availability and fault tolerance. A reuseable SNS framework was described. Clusters of w/s are ideal for internet services but clusters are difficult to manage because services must distribute load across the cluster. The cluster service must grow the cluster with increasing load. This was illustrated with a diagram.

In the SNS architecture, workers are grouped into classes. Workers can recieve tasks from the outside world or from other workers. A task originator sends a task to the consumer specifying the class and inputs to the tasks. It is assumed that tasks are short lived, atomic and restartable. Worker driver provide the interface between the SNS substrate and the worker applicaction.

The SNS manager is a seperate entity which is intentionally centralised because it makes it easier to reason about and implement. However, it is necessary to ensure is fault tolerant and not a bottleneck. The SNS manager has three key functions: resource allocation, fault tolerance and scalability.

Load balancing is achieved by each worker keeping track of local load. Workers periodically report their current load to the SNS manager. The manager piggybacks load reports on its beacons to the rest of the system. Each worker tries to perform local load balancing decisions using lottery scheduling with tickets. Auto launch scalability involves worker replication to handle short bursts so requests are handled in parallel. If the load on classes of workers gets too high, the SNS manager launches a new one. There is an overflow pool for long bursts on a non-dedicated set of machines (eg desktop machines) so that when all dedicated nodes are exhausted this overflow pool can be used.

Fault Tolerance is achieved through the use of the Starfish model: if an arm is chopped off, the rest of system grows back to same size. Peer monitoring is used to monitor performance; no client host monitoring is used. If the SNS manager dies each worker starts a timer. The first to time out launches a new SNS manager and rebuilds the list of services. Beaconing ensures synchronisation and also that multiple SNS managers do not exist.

There are several example applications of the system, including: Transend, Wingman, Media Pad and MARS. This approach presents a reusable architecture for building internet service applictions. Application developers program services to well defined, narrow interfaces. SNS takes care of resource location, load balancing and fault tolerance and a number of interesting applications have been developed using it.

One quick question from the floor asked what functionality was lost due to a crash? Yatin answered that clients experience loss of service for short periods. For example, a client gets lost if the worker goes away when using current protocols.

Panel

Chair: Jean Bacon
MVS: Maarten van Steen
RVR: Robbert van Renesse
YC: Yatin Chawathe

Question: The solution appears to solve poverty by allowing everyone to say how much money they need. So how do you stop everybody replicating everything? Is the decision made by the manager?
MVS: The document is not in full control of replication. The proxy also has control of what is cached. The Object provides hints about what suitability it has for replication.

Comment: How to decide on replication is very difficult problem and INRIA identified this in their earlier work.
MVS: Little data is available on wide area networks and this work is in part intended to gather information and through experimentation point to solutions.