--------------------------------------------------- Return-Path: owa@linen Received: from linen.cs.washington.edu (linen.cs.washington.edu [128.95.2.245]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id TAA29192 for ; Wed, 8 Jan 1997 19:16:38 -0800 Received: (owa@localhost) by linen.cs.washington.edu (8.7.2/7.2ws+) id TAA06266; Wed, 8 Jan 1997 19:16:38 -0800 (PST) Date: Wed, 8 Jan 1997 19:16:38 -0800 (PST) From: owa@linen Message-Id: <199701090316.TAA06266@linen.cs.washington.edu> To: bershad@cs Subject: Grapevine 552-reading summary Grapevine can be refered as a distributed system as it has multiple processing elements (Grapevine servers), Interconnection HW(Internet), Independent failure mode (client can access an another server), and Shared state (registration database). Though it provides performance and availability to some extent by having replicated database and servers, it has problem with reliability and scalability. The replicating methods does not ensure answers from different servers are consistent. It also needs human help for system configuration such as adding registry replicas, creating servers. This could be the weakest point of the system. -- owa --------------------------------------------------- Return-Path: rgrimm@cs.washington.edu Received: from june.cs.washington.edu (june.cs.washington.edu [128.95.2.4]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id WAA01243 for ; Wed, 8 Jan 1997 22:42:33 -0800 Received: from [128.95.8.128] (h125.dyn.cs.washington.edu [128.95.8.125]) by june.cs.washington.edu (8.8.3+CSE/7.2ju) with SMTP id WAA10113 for ; Wed, 8 Jan 1997 22:42:30 -0800 X-Sender: rgrimm@june.cs.washington.edu Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 8 Jan 1997 22:40:18 -0800 To: bershad@cs From: rgrimm@cs.washington.edu (Robert Grimm) Subject: Grapevine 552-reading Grapevine provides users with a single-image, content independent, highly available message delivery system. Internally, its functionality is divided between a registration and a message service. Both services are provided in a distributed fashion by several Grapevine servers. The registration service maps a two-level name-space into message inboxes (for individual users), into lists of names (for groups of users) and into locations (for grapevine servers) and, thus, serves as an uniform name server for all grapevine functionality. It also supports user authentication (through the use of clear-text passwords) and rudimentary access control (by testing if a name is member in a specific group). The registration database is partitioned by the higher level of the name space and is replicated at this granularity. The message service consists of several message servers that forward messages and provide message inboxes to users. Three design decisions in Grapevine clearly limit the complexity of the Grapevine system: First, while Grapevine replicates the registration database over several servers, messages themselves are not replicated. Each message is stored on exactly one message server. If this message server fails, that particular message may not be available for the user, but some other message server can still provide the user with newly incoming messages. As a result, the Grapevine system itself is highly available, at the cost of the availability of individual messages. Second, modifications to the registration database are first executed on one particular server and then lazily (in the sense that a consistent state is guaranteed to be reached eventually) propagated to other sites. Temporary inconsistencies are thus traded off against update protocol complexity. Finally, Grapevine uses both the registration and messaging services to provide its own functionality. For example, Grapevine server locations are maintained by the registration and registration updates are propagated by the message service. This economy of mechanisms avoids special internal protocols and simplifies the overall structure of Grapevine. --------------------------------------------------- Return-Path: sparekh@cs.washington.edu Received: from june.cs.washington.edu (june.cs.washington.edu [128.95.2.4]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id AAA02380 for ; Thu, 9 Jan 1997 00:34:19 -0800 Received: from yoda (h225.dyn.cs.washington.edu [128.95.8.225]) by june.cs.washington.edu (8.8.3+CSE/7.2ju) with ESMTP id AAA14838; Thu, 9 Jan 1997 00:34:16 -0800 Message-Id: <199701090834.AAA14838@june.cs.washington.edu> From: "Sujay Parekh" To: Cc: Subject: Grapevine 552-reading summary Date: Thu, 9 Jan 1997 00:37:30 -0800 X-MSMail-Priority: Normal X-Priority: 3 X-Mailer: Microsoft Internet Mail 4.70.1155 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Grapevine is a distributed system for providing resource location, access control, message delivery and authentication. The goal of message delivery is to be efficient, reliable and fault-tolerant. In addition, facilitating decentralized administration is a goal of the entire system. As in most distributed system, scalability is also a desirable property. Grapevine distinguishes "names" from "addresses", and maintains a registration database for storing them and mapping one to the other. The registration database is replicated on several registration servers. Although no one server needs to have the entire registry, between them they span the entire database. The degree of replication is sufficient to provide enhanced availability in case of faults. Similarly, there are several message servers which provide the messaging functionality of Grapevine. Message servers store messages for some subset of the users. Users are allowed to have mailboxes on several servers to provide increased availability. The mailboxes are not replicated on these servers; instead they serve as backups in case the preferred server is unavailable. Any server can be used to provide the message delivery service. Message servers use the registry servers to locate resources, while the registry servers use the message servers to deliver messages to other hosts and users. A neat feature of the Grapevine registry is that the Grapevine setup is itself described in the registry and is accessed with the same semantics and protocols as the messaging service. Indeed, the Grapevine registry can be used to provide many other services besides messaging. The Grapevine protocols are resistant enough to simple failures, network partitioning and hardware errors. However, they seem less tolerant of software bugs. Also, the registry update protocols seem quite ad-hoc. This is probably because in several tricky cases they chose to prefer human intervention rather than use some complicated and expensive protocol to maintain consistency of the registry. It may be a good engineering decision, but it makes the system less elegant. --------------------------------------------------- Return-Path: tian@wally Received: from wally.cs.washington.edu (wally.cs.washington.edu [128.95.2.122]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id CAA03228 for ; Thu, 9 Jan 1997 02:11:03 -0800 Received: (tian@localhost) by wally.cs.washington.edu (8.8.3+CSE/7.2ws+) id CAA27384; Thu, 9 Jan 1997 02:11:02 -0800 (PST) Date: Thu, 9 Jan 1997 02:11:02 -0800 (PST) From: tian@wally Message-Id: <199701091011.CAA27384@wally.cs.washington.edu> To: bershad@cs Subject: Grapevine 552-reading summary The Grapevine paper describes an early distributed system based on a single reliable message passing mechanism. Its design emphasizes distinguishing transport protocol from application protocol, reliable and available services through replication, authentication, decentralized administration and scalability. Messaging is performed by message servers that forward messages to user inboxes. Naming is done through a distributed database. The database is divided into registries that are kept consistent by propagating changes through the Grapevine registry servers. The database is used to store access control information as well as locate individuals, groups, message/registry servers, and other registries. Reliability and availability are supported by replication - a user may have multiple copies of his/her inbox, multiple message servers may field message send requests and registries are duplicated across registry servers. However, there appears to be a single point of failure when sending a message - the message server that first receives a message from a client is solely responsible for forwarding it to its destinations. Should it crash, the sending client has no way to know that the message is lost, even though there are alternate delivery paths available (i.e. in the absence of acks in the messaging protocol, there is no automatic way to exploit the extra availability). Also, registry updates by propagation are a problem - besides the fact that registries may reach inconsistent states, it does not necessarily scale, as C&C has experienced. However, the result of using simple protocols and a single message mechanism is a simple system. --------------------------------------------------- Return-Path: yasushi@silk Received: from silk.cs.washington.edu (silk.cs.washington.edu [128.95.2.238]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id IAA05687 for ; Thu, 9 Jan 1997 08:08:38 -0800 Received: (yasushi@localhost) by silk.cs.washington.edu (8.7.2/7.2ws+) id IAA09162; Thu, 9 Jan 1997 08:08:38 -0800 (PST) Date: Thu, 9 Jan 1997 08:08:38 -0800 (PST) From: yasushi@silk Message-Id: <199701091608.IAA09162@silk.cs.washington.edu> To: bershad@silk Subject: Grapevine 552-reading summary This paper describes an internet service designed primarily for email exchange. The service is provided by servers managing names and messages. The naming database is managed by a replicated set of registration servers. Single data format is used for both user names and server names. Name groups are used to support both mailing lists and replicated server groups. The database is updated by multicasting timestamped messages to the replica. At the replica side, the message with the latest timestamp wins. This approach allows temporal inconsistency among replica, but is simple and robust. Messages are persistent in Grapevine; they will be eventually delivered even if the sender or the receiver crash during transfer. Any message server can be used to send a message from anyone to anyone, but per each delivery, only one sender and one receiver message servers are involved. Therefore a message may get stuck if the sender or the receiver crash, but other messages can still be delivered, possibly to another inbox. Message servers utilize a cache to speedup the name lookup. Cache entry is really a hint, and if it turns out to be wrong, the uptodate value is re-fetched from the naming database. y --------------------------------------------------- Return-Path: sungeun@wormwood Received: from wormwood.cs.washington.edu (wormwood.cs.washington.edu [128.95.2.107]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id IAA05920 for ; Thu, 9 Jan 1997 08:30:08 -0800 Received: (sungeun@localhost) by wormwood.cs.washington.edu (8.8.3+CSE/7.2ws+) id IAA11289; Thu, 9 Jan 1997 08:30:06 -0800 (PST) Date: Thu, 9 Jan 1997 08:30:06 -0800 (PST) Message-Id: <199701091630.IAA11289@wormwood.cs.washington.edu> From: Sung-Eun Choi To: bershad@cs Subject: Grapevine 552-reading summary Reply-To: sungeun@cs.washington.edu Grapevine is a distributed system that provides availability of services/information and "failure containment" via replication. Grapevine also includes message delivery, authentication (passwords) and access control. Information about services, users, etc. is maintained in a distributed and replicated data base that is kept (mostly) coherent. As expected, performance issues arise with respect to obtaining services/information as well as information coherence. The implementors take advantage of the way in which the system is used to improve performance (i.e. optimizing for the common case). For example, it is highly unlikely that two administrators will modify the data base in a similar way at almost exactly the same time. "Optimizations" such as asynchronous actions and caching of "hints" are used to improve performance for clients in the system. All such optimizations can "fail" (e.g. two asynchronous updates collide or the hints can be incorrect) and thus either Grapevine must deal with the failures or employ administrator intervention. Finally, though Grapevine's naming scheme appears to be scalable, its performance may not be. Grapevine uses indirection to achieve scalability, but indirection usually implies increased access time. Moreover, some the "optimization" techniques (as mentioned above) will be more likely to fail. Perhaps the nature of the system will help here. For example, it seems likely that the set of services used by a particular user or group of users does not grow as the size of the network grows. Such services can be kept "close to the source" whenever possible. Also, the size of the "hint" cache will probably not grow as the system does. --------------------------------------------------- Return-Path: echris@merganser Received: from merganser.cs.washington.edu (merganser.cs.washington.edu [128.95.2.192]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id IAA06246 for ; Thu, 9 Jan 1997 08:51:32 -0800 Received: (echris@localhost) by merganser.cs.washington.edu (8.8.3+CSE/7.2ws+) id IAA06936; Thu, 9 Jan 1997 08:51:31 -0800 (PST) Date: Thu, 9 Jan 1997 08:51:31 -0800 (PST) From: echris@merganser Message-Id: <199701091651.IAA06936@merganser.cs.washington.edu> To: bershad@cs Subject: Grapevine 552-reading summary Reply-to: echris@cs.washington.edu A distributed system, called Grapevine, is described. It provides facilities for message delivery, resource location, and rudimentary database lookup on an internet of machines. The paper describes Grapevine in the context of its use in the implementation of an email service, though other "interesting" distributed services, such as file servers, may be built on Grapevine. Registries, registration servers, and message servers are fundamental components of the Grapevine system. A registry is a collection of names that are in some way logically related (such as "people at PARC"). A registration server contains registries, that is, it contains information about names in registries. A single registry may reside on several registration servers, i.e., it may be replicated. A message server accepts messages for delivery, delivers messages to other message servers, queues messages, and delivers messages to clients when they are requested. The mail submission service is replicated in that a message server accepts ANY mail submission. It appears that Grapevine can do a fine job delivering mail in a small scale internet. It is insufficient for faster-than-human services, because many of the design decisions assume the email context and defer to the human ("...the nature of the services dependent on the registration data allows a looser definition of consistency..." p268). For example, a down machine can trap messages in a queue for an indefinite period of time ("...failure to arrive is likely to be noticed outside the system." p267), and the case when two admins create the same name on two different registration servers is ignored ("...there is usually some human-level centralization of name creation." p270). Fixing these problems is fundamentally at odds with Grapevine's biggest feature, its high degree of availability. --------------------------------------------------- Return-Path: mernst@nishin.cs.washington.edu Received: from june.cs.washington.edu (june.cs.washington.edu [128.95.2.4]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id JAA06358 for ; Thu, 9 Jan 1997 09:01:29 -0800 Received: from nishin.cs.washington.edu (nishin.cs.washington.edu [128.95.4.39]) by june.cs.washington.edu (8.8.3+CSE/7.2ju) with ESMTP id JAA03748; Thu, 9 Jan 1997 09:01:18 -0800 Received: (from mernst@localhost) by nishin.cs.washington.edu (8.8.4/8.8.2) id JAA09991; Thu, 9 Jan 1997 09:01:18 -0800 Date: Thu, 9 Jan 1997 09:01:18 -0800 Message-Id: <199701091701.JAA09991@nishin.cs.washington.edu> From: Michael Ernst To: bershad@cs.washington.edu Subject: Grapevine 552-reading summary Grapevine is a distributed, replicated system primarily designed for email delivery (but also supporting other similar services). It is composed of multiple servers, but clients see it as a single entity and never name individual components of Grapevine. It is distributed because some Grapevine services require use of multiple Grapevine servers, and replicated because some services can be provided by any of a number of Grapevine servers. Any Grapevine server can accept most requests, then forwarding messages to eventual locations or updating the internal state of other Grapevine servers. Grapevine's design goals include correct performance in the face of client-side errors (only the incorrect client should be affected) and decentralized administration; it is also intended to be a test use of distributed computing. Grapevine maintains a registration data base containing group membership information and the mailboxes and locations of users. --------------------------------------------------- Return-Path: matthai@franklin.cs.washington.edu Received: from franklin.cs.washington.edu (franklin.cs.washington.edu [128.95.2.103]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id MAA09195 for ; Thu, 9 Jan 1997 12:25:50 -0800 Received: from localhost (localhost [127.0.0.1]) by franklin.cs.washington.edu (8.8.3+CSE/7.2ws+) with SMTP id MAA07643 for ; Thu, 9 Jan 1997 12:25:49 -0800 (PST) Message-Id: <199701092025.MAA07643@franklin.cs.washington.edu> X-Mailer: exmh version 1.5.3 12/28/94 To: bershad@franklin.cs.washington.edu Subject: Grapevine 552-reading summary Reply-to: Matthai Philipose Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Thu, 09 Jan 1997 12:25:49 PST From: Matthai Philipose Grapevine is a distributed system for e-mail delivery. It meets Schroeder's criteria for a distributed system, because there are many computers involved (those of mail senders, receivers, and servers), they're connected by a network, and they have common state (e.g. the registration database). The designers pay particular attention to providing appropriate reliability semantics (either deliver or notify of failure to do so), availability (by replication of system components), interactive ease of use (by ensuring latencies between a message send and its delivery and reception are low), and decentralized administration. I thought the designers did a good job of using the particular characterisitics of the problem domain (i.e. mail delivery) to guide/simplify the architecture of the distributed system. The level of reliability in the messaging system, the lack of ordering among mail messages, the relaxed consistency of registration database update protocols, the lack of atomicity in message broadcasts to groups all resulted in a simple system which nevertheless maintained the level of confidence and "interactive feel" that a user requires of a mail system. Some features, such as automatic user authentication, are Grapevine stamdards missing even in modern messaging systems. Others, such as automatic load balancing (for instance, by using the messaging server with the lowest load instead of the first one on the list) would be needed in modern systems, but don't seem to have been an issue when Grapevine was built. In summary, the Grapevine system was a remarkably far-sighted one, and a good argument for having your innovative systems built by a team of idle, interest-driven engineers rather than by overworked, market(or PhD)-driven ones! --------------------------------------------------- Return-Path: ddion@june Received: from june.cs.washington.edu (june.cs.washington.edu [128.95.2.4]) by whistler.cs.washington.edu (8.8.3/7.2ws+) with ESMTP id PAA11698 for ; Thu, 9 Jan 1997 15:34:43 -0800 Received: (ddion@localhost) by june.cs.washington.edu (8.8.3+CSE/7.2ju) id PAA08782; Thu, 9 Jan 1997 15:34:42 -0800 From: ddion@june (David Dion) Message-Id: <199701092334.PAA08782@june.cs.washington.edu> Subject: Grapevine 552-reading summary To: bershad@cs Date: Thu, 9 Jan 1997 15:34:41 -0800 (PST) Cc: ddion@june (David Dion) X-Mailer: ELM [version 2.4 PL23] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit (second attempt at getting the subject line right) Grapevine is a system whose primary goal is to provide message delivery over a network. It also provides authentication, access control, and resource location services. Its implementation is distributed, in that it is spread over multiple networked computers, and replicated, in that services are provided equally well by more than one machine. Grapevine is characterized by several design goals. First, its services are accessible to a large variety of heterogeneous clients. The nature or integrity of clients is unpredictable and should have no effect on services provided to other clients. Second, it is reliable in both the delivery of messages and the availability of services. Messages accepted for delivery are either delivered or returned with an error, and the failure of a Grapevine server should not mean that a service becomes unavailable to clients. Third, administration is decentralized. Administrators can invoke policy without requiring cooperation across the entire network. Fourth, Grapevine should scale to a large number of servers and/or clients. Finally, Grapevine should provide authentication of senders and receivers of messages Central to the implementation of Grapevine is a naming service known as the Registration Database. The Registration Database provides authentication, resource location, and group membership services. The namespace is hierarchical, allowing for scalability and distributed management. The Registration Database is implemented by a set of registration servers, while message delivery is provided by a set of message servers. Both registration servers and message servers are distributed and replicated throughout the Grapevine system. Client machines run a software package that communicates with registration and message servers, which run on dedicated Grapevine machines. A secondary goal of Grapevine is to study the implementation of a distributed system. One significant tradeoff is between availability and consistency. For instance, modifications to a registry are not propagated immediately throughout the system. This eliminates the need to lock multiple servers (better availability) but leaves data obsolete for an unspecified period of time and creates the potential for conflicting updates (poor consistency). Another lesson learned in the implementation of Grapevine is the value of caching and hints, which are used in the locating delivery sites for messages.