The ISIS System Manual, Version 1.1

K. Birman, R. Cooper, T. Joseph, K. Kane and F. Schmuck

\begin{matrix}c \\ ◯ \end{matrix}1988 by The ISIS Project ^{1} December 21, 1988

Contents

1 Getting Started 1

2 Basic Facilities 37 2.1 Sites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4 Broadcasts and replies . . . . . . . . . . . . . . . . . . . . . . 49 2.5 Process groups . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.6 Monitors and watches . . . . . . . . . . . . . . . . . . . . . . 63 2.7 State transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.8 Start sequence . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3 More About Messages 81 3.1 Creating and deleting a message . . . . . . . . . . . . . . . . 82 3.2 The msg put, msg gen, and msg get routines . . . . . . . . . 83 3.3 Message fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.4 Defining new field types . . . . . . . . . . . . . . . . . . . . . 89 3.5 Other useful message routines . . . . . . . . . . . . . . . . . . 91 3.6 Input and output of messages . . . . . . . . . . . . . . . . . . 92

4 The Lightweight Task Subsystem 95 4.1 Basic task mechanisms . . . . . . . . . . . . . . . . . . . . . . 95 4.2 Two common misunderstandings . . . . . . . . . . . . . . . . 96 4.3 Task creation . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.4 Task synchronization . . . . . . . . . . . . . . . . . . . . . . . 98 4.5 Scheduling rule . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.6 Urgent fork and signal . . . . . . . . . . . . . . . . . . . . . . 101 4.7 Stack overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5 The Broadcast Interface 107

5.1 The ISIS broadcast and reply primitives . . . . . . . . . . . . 107 5.2 Forking off a remote procedure call as a task . . . . . . . . . 113

6 Virtual Synchrony 117 6.1 Virtually synchronous executions . . . . . . . . . . . . . . . . 117 6.2 The ideal virtually synchronous world . . . . . . . . . . . . . 119 6.3 External actions and communication that bypasses ISIS … 121 6.4 Dealing with stable storage . . . . . . . . . . . . . . . . . . . 122

7 Replicated Data 125 7.1 Normal case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7.2 Replicated data with unordered broadcasts . . . . . . . . . . 127 7.3 Synchronization needed . . . . . . . . . . . . . . . . . . . . . 128 7.4 Updates from an exclusive sender . . . . . . . . . . . . . . . . 128 7.5 State transfer and recovery from logs . . . . . . . . . . . . . . 129

8 Distributed and Parallel Executions 131 8.1 Parallel and replicated execution . . . . . . . . . . . . . . . . 131 8.2 Redundant computation . . . . . . . . . . . . . . . . . . . . . 132 8.3 Coordinator-cohort computation . . . . . . . . . . . . . . . . 134 8.4 Subdivided computations . . . . . . . . . . . . . . . . . . . . 140 8.5 Updating replicated data in distributed executions . . . . . . 145 8.6 Disk files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 8.7 Aborting a distributed execution before it terminates . . . . . 147

9 Synchronization Facilities 151 9.1 Token passing . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 9.2 Some comments about the token algorithm . . . . . . . . . . 157 9.3 Token tool interface . . . . . . . . . . . . . . . . . . . . . . . 158 9.4 Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

10 Transactions 165 10.1 Coordinators and Participants . . . . . . . . . . . . . . . . . . 166 10.2 Some ways of using transactions . . . . . . . . . . . . . . . . 170

11 Guards 175 11.1 Guard statement and guarded broadcasts . . . . . . . . . . . 176 11.2 Guards are closely associated with process groups. . . . . . . 177 11.3 Guards must be “turned on” before they can be used . . . . . 177 11.4 Guarded operations are automatically transferred during pg join177 11.5 Guard expression format . . . . . . . . . . . . . . . . . . . . . 178 11.6 Event identifiers . . . . . . . . . . . . . . . . . . . . . . . . . 179 11.7 Pattern matching rules . . . . . . . . . . . . . . . . . . . . . . 179 11.8 Use of the after clause . . . . . . . . . . . . . . . . . . . . . 180 11.9 Example of guards and their meanings . . . . . . . . . . . . . 181 11.10Example: token passing . . . . . . . . . . . . . . . . . . . . . 182 11.11Example: atomic transaction . . . . . . . . . . . . . . . . . . 186

12 The Logging Facility 187 12.1 The Automatic Mode . . . . . . . . . . . . . . . . . . . . . . 188 12.2 Recovery in the Automatic Mode . . . . . . . . . . . . . . . . 192 12.3 End-of-Replay Processing . . . . . . . . . . . . . . . . . . . . 195 12.4 Manual Log Flushing . . . . . . . . . . . . . . . . . . . . . . . 196 12.5 Restrictions on the Automatic Mode . . . . . . . . . . . . . . 199 12.6 The Manual Mode . . . . . . . . . . . . . . . . . . . . . . . . 202 12.7 General Restrictions and Notes . . . . . . . . . . . . . . . . . 209

13 Broadcast Types and Order 213 13.1 The fbcast broadcast primitive. . . . . . . . . . . . . . . . . . 213 13.2 The cbcast broadcast primitive. . . . . . . . . . . . . . . . . . 214 13.3 Lazy asynchronous cbcasts . . . . . . . . . . . . . . . . . . . 216 13.4 The abcast primitive. . . . . . . . . . . . . . . . . . . . . . . 217 13.5 The gbcast primitive. . . . . . . . . . . . . . . . . . . . . . . 217 13.6 Picking the right protocol . . . . . . . . . . . . . . . . . . . . 218

13.6.1 Example 1: a distributed information service . . . . . 218 13.6.2 Example 2: a fault-tolerant lock manager . . . . . . . 220

14 Advanced Facilities 223 14.1 Building large process groups . . . . . . . . . . . . . . . . . . 223 14.2 The remote exec facility . . . . . . . . . . . . . . . . . . . . . 225 14.3 Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 14.4 Forking off a child from within ISIS . . . . . . . . . . . . . . . 228 14.5 Interacting with files and devices . . . . . . . . . . . . . . . . 229 14.6 Using ISIS in an X-windows program . . . . . . . . . . . . . . 230 14.7 Using ISIS in a suntools program . . . . . . . . . . . . . . . . 231 14.8 News facility . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

14.8.1 How to post and receive news messages . . . . . . . . 233 14.8.2 Example: a load monitoring program . . . . . . . . . . 235

14.8.3 Diagnostics . . . . . . . . . . . . . . . . . . . . . . . . 236 14.9 The recovery manager . . . . . . . . . . . . . . . . . . . . . . 236 14.10Cmd – the interactive ISIS control program . . . . . . . . . . 238

14.10.1 Running the cmd tool . . . . . . . . . . . . . . . . . . 238 14.10.2 Sending interactive messages . . . . . . . . . . . . . . 239

14.11Creating and interpreting client dumps . . . . . . . . . . . . . 242 14.12Creating and interpreting protocol process dumps . . . . . . . 248 14.13Load monitoring utility . . . . . . . . . . . . . . . . . . . . . 252 14.14How the system behaves under heavy load . . . . . . . . . . . 255

A Setting Up ISIS 257

B Quick Reference 265 B.1 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 B.2 Sites and addresses . . . . . . . . . . . . . . . . . . . . . . . . 265 B.3 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 B.4 Broadcasts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 B.5 Process groups . . . . . . . . . . . . . . . . . . . . . . . . . . 271 B.6 Monitoring and watching . . . . . . . . . . . . . . . . . . . . 273 B.7 Coordinator-cohort . . . . . . . . . . . . . . . . . . . . . . . . 275 B.8 State transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 B.9 Tasking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 B.10 Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 B.11 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 B.12 Implementation status . . . . . . . . . . . . . . . . . . . . . . 279 B.13 Protection status . . . . . . . . . . . . . . . . . . . . . . . . . 280

C Performance of the Toolkit Facilities 281

D Twenty questions and other demo software 283 D.1 Twenty Questions . . . . . . . . . . . . . . . . . . . . . . . . 283 D.2 The bank program . . . . . . . . . . . . . . . . . . . . . . . . 285 D.3 Parallel make program . . . . . . . . . . . . . . . . . . . . . . 286

Preface

This manual describes the structure and use of the ISIS toolkit for distributed and fault-tolerant programming. The material is structured so that a user unfamiliar with ISIS should be able to write and test a distributed application after reading just the first two chapters. Subsequent chapters cover the various tools provided by ISIS in much greater detail, and the reader who works through them should emerge with a thorough practical understanding of what ISIS does and how to make use of it.

Throughout the manual, an attempt has been made to include code samples as often as possible. Our hope is that in many cases, the reader will be able to copy these code samples, making only a small number of changes to adapt them into the environments where they will actually be used.

The structure of the manual is as follows:

Chapter 1. Getting Started An introduction to ISIS, focusing on an example of a small but typical ISIS application.

Chapter 2. Basic Facilities Basic data structure and ISIS system calls. How to maintain replicated data using ISIS.

Chapter 3. More About Messages A more detailed discussion of the ISIS message subsystem.

Chapter 4. The Lightweight Task Subsystem A more detailed discussion of the ISIS lightweight task subsystem.

Chapter 5. Broadcast Interface The long form of the broadcast system call, and the options it supports.

Chapter 6. Virtual Synchrony A more detailed presentation of the idea behind virtual synchrony and its impact on programming in ISIS.

Chapter 7. Replicated data A discussion of how to maintain replicated data using ISIS.

Chapter 8. Distributed and Parallel Executions Techniques for obtaining distributed and parallel executions in ISIS.

Chapter 9. Synchronization How to obtain synchronization and locking using ISIS.

Chapter 10. Transactions Dealing with transactional databases and files from within ISIS.

Chapter 11. Broadcast Guards A mechanism for delaying the delivery of a broadcast until some other event occurs.

Chapter 12. The Logging Facility How to use the ISIS logging facility to develop software that can recover from total failures without losing its state.

Chapter 13. Broadcast Types and order Types of broadcasts available and how their delivery ordering guarantees vary.

Chapter 14. Advanced Facilities Discussions of a number of advanced topics, including reception and generation of signals, forking from within ISIS clients, the remote execution facility, rules for interacting with devices from within ISIS, using ISIS in an X-windows program, using ISIS in a suntools program, the recovery manager, an interactive ISIS control program, creating and interpreting client and protocol process dumps, and how the system behaves when overloaded.

Appendix A. Setting Up ISIS A section aimed at the systems administrator responsible for setting up ISIS on a network.

Appendix B. Quick Reference A summary of the ISIS system.

Appendix C. Performance of the toolkit facilities Will contain detailed performance information about the broadcast primitives and the toolkit as a whole in a future version of the manual.

Appendix D. Demonstration programs ISIS comes with several demo programs. This appendix explains how to run them.

Chapter 1

Getting Started

There is perhaps no better way to learn about a new system than by actually using it, so let us begin by using ISIS to develop a simple application. A typical ISIS application has parts that run on several different machines and can be expanded to include more machines or be removed from some machines even as the application is running. The reason for distributing the application over a number of machines may be to share the work, to obtain faster response time, or to be able to continue operation despite the failures of some of the machines. The example below has been chosen with the idea of exposing you to most of the basic features of ISIS rather than to illustrate a real-life ISIS application. Yet, you will see that ISIS makes it simple to write a program that is distributed, dynamically expandable, and fault-tolerant.

We will consider a distributed “time-card” service for an organization with several departments. The organization hires a number of temporary workers, who may work in several different departments in a given week, covering excess work where and when required. Each department separately records the number of hours each temporary employee works in that department. The object of the time-card service is to enable someone to give the service the name of an employee and obtain the number of hours that the employee worked in the various departments the previous week. (The employee will presumably be paid on this basis.) The time-card service will have to search through the records of the individual departments before giving its response.

If the organization has a number of workstations connected by a network (and they have ISIS), this service could be implemented to run on several of these machines instead of on just one machine. One advantage is that the records of different departments can be scanned in parallel on several machines, instead of one after the other on a single machine. This means that queries will be answered sooner. A second advantage is that we can ensure that the service remains available even when some of the machines are not operational because of a failure or because they have been taken off-line for maintenance or for other reasons. Let us assume that each department

keeps its records in a file called department1, department2, department3,

and so on, and that each record is simply a line giving the employee’s name followed by the number of hours he or she worked. We will also assume that these files are available on all the machines on which the service runs.

Before we go any further with our example, we need to introduce some of the ideas that are central to programming with ISIS.

Process groups and broadcasts

One of the most basic mechanisms that ISIS provides is a means of grouping processes together and naming them as a unit. A process group could contain just a single member, but will often consist of a number of processes residing on machines anywhere in the system. The membership of a process group could change with time, as new processes join the group or as existing members leave it, either out of choice or because of a failure of some part of the system. A process can be a member of more than one process group.

ISIS also provides a broadcast mechanism that enables you to send a message from a process to a process group. To do this, the sending process first asks ISIS to “look up” the name of the process group and obtains an “address”. It then performs a broadcast^{1} giving this address, the message, and other relevant information as arguments. The effect of this is to send a copy of the message to each of the current members of the process group. All members will eventually receive the message, although they may receive it at different times.

The broadcast mechanism also allows the recipient of a message to send a reply, or to forward it to some other process that will send a reply. A process broadcasting a message can indicate that it wants to wait for a specific number of replies, or that it wants a reply from all the recipients of the message. The broadcast function call returns when the requested number of replies have been received. If the group is not large enough, or if so many recipients terminate (possibly because of failures) that the required number of replies cannot be collected, ISIS will collect as many replies as possible and notify the sender of the shortfall. This reply mechanism allows the ISIS broadcast facility to be used as a generalized remote procedure call mechanism.

1The term “broadcast” is used in many different ways; we use it to mean the sending of a message from one process to others using the ISIS broadcast function call.

The most common reason for making a set of processes into a process group is to be able to broadcast messages to the group as a whole, even when its membership may be changing. As a special case, the simplest way to send a message to an individual process is to make it a member of a process group containing only itself, and broadcast messages to this group. If a process will receive messages both as an individual and as a member of a process group, it can be made a member of two process groups. Process groups are cheap in ISIS, so this should not pose performance problems.

There is another reason why you might want to make a set of processes into a process group. ISIS provides simple-to-use tools that permit members of a process group to access shared or replicated information, to perform certain forms of coordinated distributed execution, and to tolerate and recover from failures, among other things. If a set of processes wishes to make use of these tools, they would typically be made members of a process group. These tools will be described in later sections.

Process groups provide a convenient way of giving an abstract name to the service implemented by the members of the group. Other processes interact with the service using the name of the group and the broadcast facility. They need not be aware of the actual membership of the group. This means that the group implementing the service can grow, shrink, move to different machines, or add new capabilities without any interruption to the service, and with the users of the service being unaware of these changes. It is this feature that makes it possible to develop applications that are modular, dynamically expandable, and tolerant of failures. Figure 1.1 provides an illustration of this. It shows a process P communicating with a process group that implements a print service. The important thing to notice is that in all three cases P addressed its message to the group PrintService. ISIS keeps track of the group membership and delivers the message to the current members. P thus thinks of the group as an abstract service implementing some function (print documents) and does not care about how many members the group has or where they happen to be currently located.

It should be noted that the ISIS namespace is actually structured into naming “scopes” in order to limit the cost associated with this addressing Figure 1.1: Process groups provide a unit of abstraction. mechanism. However, one can use ISIS without worrying about this issue, and we will defer discussion of it until later in the manual.

Tasks and entries

Readers familiar with UNIX will know that a UNIX “process” has a private address space within which a single thread of control lives. Some newer operating systems like MACH have introduced a notion of lightweight tasks that coexist within a single process, sharing the address space. Although ISIS was built on top of UNIX, we needed a task mechanism to implement the system. Consequently, a process in an ISIS application is internally structured into a number of tasks. An ISIS task looks just like a C function, and shares the same address space and global variables as all the other tasks and functions in the process. The difference is that a task (and not just the function called main) can be invoked by the system and start executing in response to certain events, the most common of which is message delivery. A task that is started up in response to a message delivery is called an “entry”. A process can have many entries and each one is given a different “entry number”. When a message is sent, it is addressed to a particular entry number. On delivery, (a pointer to) the message is passed as a parameter to the entry, which typically reads the contents of the message and acts accordingly.

Programming with tasks is not very different from programming with regular C functions, except for two things. When a task makes certain ISIS system calls, it is possible for a new task to be started up and begin executing before the system call returns. The original task will later continue from where it left off. As an example, consider a task that made a system call to broadcast a message and is now waiting for replies. If a new message arrives before the replies come, another task (an entry) may be started up to handle the new message even though the first task has not terminated. Normally this poses no problem, but if the second task changes the values of global variables, then the first task has to be aware of the fact that their values might change between when it performs the broadcast system call and when the system call returns. System calls that allow other tasks to be started up before they return are called “blocking” system calls because they “block” the execution of the task that performs the call. This documentation will indicate which system calls may block, and under what conditions.

The other thing to keep in mind when programming with tasks is that they have a stack limit of 32k bytes. This is sufficient for most purposes, but extremely deep nesting of function calls (as might happen with recursive calls) or allocation of large arrays or data structures on the stack may lead to the limit being exceeded. ISIS will usually, but not always, detect this. You can increase (or decrease) this limit with a one-time declaration, but be aware that all tasks will have this new stack size, and if it is made too large you may have problems with memory allocation. ISIS includes a way to call a subroutine without imposing the stack size limit, provided that the subroutine will not invoke any ISIS functions before it returns. This is convenient when, for example, an ISIS task must call a large piece of software over which the ISIS programmer has no control, and which might not respect the ISIS conventions. We’ll say more about this later.

Monitoring events

A process can instruct ISIS to notify it when certain types of events occur. It does so by giving ISIS the name of a task to invoke (and an argument to pass to the task) when that type of event takes place. Among the types of events that can be monitored are process group membership changes, process termination, and site failures. This facility may be used to reapportion the work load when new members join or leave a process group, or to take over work from a process or site that fails, among other things.

Example: the time-card service

From the discussion above, it follows that the time-card service should be implemented as a process group consisting of a number of processes running on different machines. We will call the group timeservice. The reason for putting the processes in one process group is to be able to use the broadcast mechanism to send queries to the group as a whole. All the members of the time-card service execute the same program (which we will call the service program). Another program (the query program) is used to query the service. We will develop both programs side by side, as is typical when programming with ISIS.

Part of the code for the service program is shown below. The value <port-no> is the port number used by ISIS to talk to applications. You will have to ask your system administrator for this. If ISIS is listed in the /etc/services file, you may give the value 0 for <port-no> and ISIS will look it up for you.

#include    "isis.h"
#define     QUERY_ENTRY     1
address     gaddr;
int         my_index;
int         my_dept;
main()
{
    int     service_maintask();
    int     group_change();
    int     receive_query();
    isis_init (<port-no>);
    /* Declare tasks and entry points */
    isis_task (service_maintask, "service_maintask");
    isis_task (group_change, "group_change");
    isis_entry (QUERY_ENTRY, receive_query,
                                      "receive_query");
    isis_mainloop (service_maintask);
}
service_maintask()
{
    int     group_change();
    /* Join the process group and monitor */
    /* membership changes                 */
    gaddr = pg_join ("timeservice",
                          PG_MONITOR, group_change, 0,
                     0);
    isis_start_done();
}

group_change (gview_p, arg)
  groupview *gview_p;
  int       arg;
{
    int     i;
    /* Compute a unique index for this member */
    i = 0;
    while (!addr_ismine (gview_p->gv_members[i]))
        i++;
    my_index = i + 1;
}

In an ISIS application, the function main usually just reads in the command line arguments (this example has none), initializes ISIS, declares tasks and entries, and sets off the main loop. The argument to isis mainloop is the first task to be run. The first thing that service maintask does is to join the process group timeservice and set up a monitor for group membership changes. The first argument to pg join is the name of the group, and the last argument is always a 0. In between these two arguments, you may specify a number of optional keywords and the arguments corresponding to those keywords. Here, the keyword PG MONITOR specifies that the task group change is to be called with the new group view and the given argument (in this case 0) whenever the group membership changes. The function pg join returns the address of the group, which is stored in the global variable gaddr. When the main task is begun, ISIS inhibits the delivery of new requests from other processes. This ensures that you can do all the necessary initialization before being asked to respond to other events like incoming messages. The call isis start done tells the ISIS system that the startup sequence is completed. This means that new tasks may be started up at the next blocking system call or after the main task terminates. ISIS automatically invokes isis start done when the main task terminates (the call is hence unnecessary here), but if the main task remains in a loop and you forget to call isis start done, your application will simply execute the main task and do nothing else. Notice that if you want to terminate the execution of an ISIS process, you must call exit explicitly.

It is important to realize that an ISIS process can be active even if there are no active tasks within it (e.g. the main task has finished, and no new tasks have been started). In fact, ISIS is designed under the assumption that tasks will start up, do the work they are supposed to do, and then terminate (by returning). This applies to the main task as well as any others. A process with no active tasks in it is in fact waiting in isis mainloop for work to do. Later in the manual we describe a way to obtain a printable dump of the internal state of a process that includes a list of all active tasks within it.

Look now at the routine group change. This routine is called in each member of the group (recall that they are all executing the same piece of code) whenever the group membership changes. Routines that monitor group memberships are always called with a pointer to the “group view” structure as its first argument. (The second argument is a value supplied by the user when the monitor is set up). The groupview structure contains information about the process group (Section 2.5). In particular, it contains a list of the addresses of all the current members gv members. The group view structure always orders this list according to the “rank” of the members. The oldest member in the group has rank 0, the second oldest rank 1, and so on. So the rank can be used to give each member a unique index that distinguishes it from the other members. In the example, my index contains the value of the rank +1. (Another way to obtain the rank is to call pg rank(gaddr, paddr), which returns the rank of process paddr in the group gaddr.) The task group change is invoked in a process when the process joins the group for the first time (this, too, is a membership change), so when isis start done is called my index will have a defined value. This index will change each time a member joins or leaves the group.

To receive incoming messages we must define an entry. The isis entry statement declares such an entry, giving it the entry number QUERY ENTRY. We now give the code for this entry. We assume that an incoming query message contains a string giving the name of an employee. For now, we assume that there are at least as many members in the process group as there are departments, and that each member is responsible for searching through the file for the department whose number is in my dept. Extra members have the value 0 in my dept and do nothing. We will see later how the members decide which department they are responsible for, and how they handle the case where there are fewer members than departments.

receive_query (msg_p)
  message   *msg_p;
{
    char    query_name[MAX_NAMELEN];

    int     query_hours;
    if (my_dept != 0)
    {
        /* Read employee name from message */
        msg_get (msg_p, "%s", query_name);
        /* Search through relevant file to find number */
        /* of hours worked in my_dept and store it in  */
        /* query_hours                                 */
        /* Send reply message */
        reply (msg_p, "%d%d", my_dept, query_hours);
    }
    else    /* I am not responsible for any department */
        nullreply (msg_p);  /* Say I won't be replying */
}

An entry is called when a message addressed to its entry number arrives at a process. Its first argument is a pointer to the message. This pointer may be used to read data out of the message using msg get, which has an interface similar to fscanf. In this case, it reads a string of characters out of the message and stores it in query name.

Let us shift gears for a minute and look at the query program. It has a similar initialization sequence, and simply reads in a name from the terminal, broadcasts a message to the timeservice process group, and prints out the replies. This is what the code looks like.

#include    "isis.h"
#define     QUERY_ENTRY     1 /* From the service */
#define     MAX_NAMELEN     64
#define     NDEPTS          5
main()
{
    int     query_maintask();
    isis_init (<port-no>);

/* Declare tasks and entry points */
isis_task (query_maintask, "query_maintask");
isis_mainloop (query_maintask);
}
query_maintask()
{
address gaddr;
char    name[MAX_NAMELEN];
int     dept[NDEPTS], hours[NDEPTS];
int     i;
/* Find address of timeservice process group */
gaddr = pg_lookup ("timeservice");
if (addr_isnull(gaddr))
{
    printf ("Sorry! the service is not available\n");
    exit();
}
isis_start_done();
/* Loop asking queries */
printf ("Enter employee name (^D to quit): ");
while (scanf ("%s", name) == 1)
{
    /* Broadcast a message containing the name and */
    /* collect replies                             */
    do
        bcast (gaddr, QUERY_ENTRY, "%s", name, ALL,
                                "%d%d", dept, hours);
    while (isis_nreplies != isis_nsent);
    /* Print out time card */
    printf ("Time card for %s:\n", name);
    printf ("    Dept.   Hours\n");
    for (i = 0; i < isis_nreplies; i++)
        printf ("%8d%8d\n", dept[i], hours[i]);

        /* Read in next name */
        printf ("\nEnter employee name (^D to quit): ");
    }
    /* Quit by explicitly terminating this process */
    exit(0);
}

Notice the use of pg lookup to obtain the address of a process group. The most significant part of the code, of course, is the call to bcast to send a message and collect the replies. As you can see, the call first specifies the address and the entry number. This is followed by a description of the data to be put into the outgoing message (in a form similar to fprintf). Next comes the number of replies wanted. The constant ALL specifies that a reply is wanted from all the processes to which a copy of this message was sent. This is followed by a description of where to put the data that is read out of the reply messages (in a form similar to fscanf). Unlike fscanf, though, each item is a pointer to an array of the given type, because there could be more than one reply message. The data from each reply goes into one element of each of the arrays. Compare the call to bcast in the query program with the calls to msg get and reply in the service program; it’s easy to see how they match up.

When a call to bcast returns, the global variable isis nsent contains the number of processes that were sent a copy of the message and isis nreplies contains the number of replies collected. (The latter value is also the return value of bcast, unless an error occurs, in which case an error code is returned.) In our example, these two values would normally be equal. However, if a process that was sent a message terminates before replying (possibly because of a failure), ISIS will detect this and the call to bcast will return without collecting a reply from this member. A process that terminates is automatically dropped out of any process group it belonged to, so our query program reissues the broadcast if this happens. This next time around the message will be sent to the new membership of the group and unless more processes terminate, a reply will be received from all of them.

Now we shall see how each member is assigned a department (we still assume that there are at least as many members as there are departments). Let NDEPTS be the number of departments. Earlier we showed how each member can compute a unique index (my index). A simple rule would be to make the member with index i responsible for department i, for i ≤ NDEPTS. A member with index i > NDEPTS does nothing unless an active member drops out of the group (possibly because of a failure). If the index of a previously inactive member now becomes less than or equal to NDEPTS, it will begin to take part in the search. Such a process is called a “standby”. Standbys make an application tolerant of failures, and are used often in ISIS. This application will tolerate the failure of as many processes as there are standbys.

The complete code for the service program is given below. Note that whenever the group membership changes, each member recomputes my index and opens the relevant file departmenti (and closes any previously opened one).

#include    <stdio.h>
#include    "isis.h"
#define     QUERY_ENTRY     1
#define     MAX_NAMELEN     64
#define     NDEPTS          5
address     gaddr;
int         my_index;
int         my_dept = 0;
FILE        *my_file_p;
main()
{
    /* Same as before */
}
service_maintask()
{
    /* Same as before */
}
group_change (gview_p, arg)
  groupview *gview_p;
  int       arg;
{
    char    filename[16];

/* Compute a unique index for this member */
i = 0;
while (!addr_ismine (gview_p->gv_members[i]))
    i++;
my_index = i + 1;
/* Close previously open file, if any */
if (my_dept != 0)
    fclose (my_file_p);
/* Reassign departments */
if (my_index <= NDEPTS)
{
    my_dept = my_index;
    /* Open relevant file */
    sprintf (filename, "department%d", my_dept);
    my_file_p = fopen (filename, "r");
    if (my_file_p == NULL)
    {
        printf ("Could not open file %s\n", filename);
        exit();
    }
}
else
    my_dept = 0;
}
receive_query (msg_p)
message   *msg_p;
{
char    query_name[MAX_NAMELEN], name[MAX_NAMELEN];
int     query_hours, hours;
if (my_dept != 0)
{
    /* Read employee name from message */
    msg_get (msg_p, "%s", query_name);

        /* Search through relevant file to find number */
        /* of hours worked in my_dept                  */
        query_hours = 0;
        while (fscanf (my_file_p, "%s %d", name,
                                            &hours) == 2)
            if (strcmp (query_name, name) == 0)
            {
                query_hours = hours;
                break;
            }
        /* Send reply message */
        reply (msg_p, "%d%d", my_dept, query_hours);
    }
    else    /* I am not responsible for any department */
        nullreply (msg_p);  /* Say I won't be replying */
}

We now have a complete implementation for the time-card service. At this point you can compile the two programs separately and link each of them with the ISIS libraries lib1.a, lib2.a, and mlib.a (in that order). (The code and some sample data files are provided in the demo directory. Check with your site administrator to find out where these subroutine libraries are located on your machine. ) You can then start up as many instances of the service program as you wish, perhaps on different machines, and as many instances of the query program as you want, also on different machines if desired, and begin issuing queries. To test the fault tolerance of the program, you may wish to add a loop to the query program, so that for each name you type in, it broadcasts the same query over and over, say 50 times. Then as the service is being queried repeatedly, you can add new members by starting up new instances of the service program on any machine or simulate a failure by killing existing members (using ^C or the kill command). You will see that as long as there are at least NDEPTS members, the service will continue to operate correctly. You can even turn off the power from a machine that has a member on it. In this case, there may be a pause because ISIS will wait for an answer from this machine for about 45 seconds before timing out and deciding that it has failed. To make this even more interesting and fun, we provide the code for an implementation that works even if there are fewer than NDEPTS members. The changes are simple. If the number of members drops below NDEPTS, some members take care of more than one department. The variables my dept and my file p become arrays, and the replies carry arrays, too. Notice the changes to bcast, msg get, and reply to handle arrays. The details of the syntax are given in Section 2.3. Here is the service program.

#include    <stdio.h>
#include    "isis.h"
#define     QUERY_ENTRY     1
#define     MAX_NAMELEN     64
#define     NDEPTS          5
address     gaddr;
int         my_index;
int         my_ndepts = 0;
int         my_dept[NDEPTS];
FILE        *my_file_p[NDEPTS];
main()
{
    /* Same as before */
}
service_maintask()
{
    /* Same as before */
}
group_change (gview_p, arg)
  groupview *gview_p;
  int       arg;
{
    char    filename[16];
    int     n_members;
    int     i;
    /* Compute a unique index for this member */
    i = 0;

while (!addr_ismine (gview_p->gv_members[i]))
    i++;
my_index = i + 1;
/* Record number of members in group */
n_members = gview_p->pg_nmemb;
/* Close previously open files, if any */
for (i = 0; i < my_ndepts; i++)
    fclose (my_file_p[i]);
/* Reassign departments */
my_ndepts = 0;
for (i = my_index; i <= NDEPTS; i += n_members)
{
    my_dept[my_ndepts] = i;
    /* Open relevant file */
    sprintf (filename, "department%d", i);
    my_file_p[my_ndepts] = fopen (filename, "r");
    if (my_file_p[my_ndepts] == NULL)
    {
        printf ("Could not open file %s\n", filename);
        exit();
    }
    my_ndepts++;
}
}
receive_query (msg_p)
message   *msg_p;
{
char    query_name[MAX_NAMELEN], name[MAX_NAMELEN];
int     query_hours[NDEPTS], hours;
int     i;
if (my_ndepts > 0)
{
    /* Read employee name from message */

        msg_get (msg_p, "%s", query_name);
        /* Search through relevant files to find number */
        /* of hours worked in my_dept[i] and store in   */
        /* query_hours[i]                               */
        for (i = 0; i < my_ndepts; i++)
        {
            query_hours[i] = 0;
            while (fscanf (my_file_p[i], "%s %d", name,
                                             &hours) == 2)
            if (strcmp (query_name, name) == 0)
            {
                query_hours[i] = hours;
                break;
            }
        }
        /* Send reply message */
        reply (msg_p, "%D%D", my_dept, my_ndepts,
                                  query_hours, my_ndepts);
    }
    else    /* I am not responsible for any department */
        nullreply (msg_p);  /* Say I won't be replying */
}

And here is the corresponding query program.

#include    "isis.h"
#define     QUERY_ENTRY     1
#define     MAX_NAMELEN     64
#define     NDEPTS          5
main()
{
    /* Same as before */
}
query_maintask()
{

address gaddr;
char    name[MAX_NAMELEN];
int     dept[NDEPTS * NDEPTS], hours[NDEPTS * NDEPTS];
int     i, j, k, rval;
int     arraylen_1[NDEPTS], arraylen_2[NDEPTS];
/* Find address of timeservice process group */
gaddr = pg_lookup ("timeservice");
if (addr_isnull (gaddr))
{
    printf ("Sorry! the service is not available\n");
    exit();
}
isis_start_done();
/* Loop asking queries */
printf ("Enter employee name (^D to quit): ");
while (scanf ("%s", name) == 1)
{
    /* Broadcast a message containing the name and collect */
    /* replies                                             */
    do
        rval = bcast (gaddr, QUERY_ENTRY, "%s", name,
                             ALL, "%D%D", dept, arraylen_1,
                                           hours, arraylen_2);
    while (isis_nreplies != isis_nsent);
    /* Exit on error */
    if (rval <= 0)
    {
        isis_perror("Sorry! bcast error");
        exit();
    }
    /* Print out time card */
    printf ("Time card for %s (based on %d replies):\n",
                                              name, nreplies);
    printf ("    Dept.   Hours\n");
    for (i = 0, k = 0; i < isis_nreplies; i++)

            for (j = 0; j < arraylen_1[i]; j++)
            {
                printf ("%8d%8d\n", dept[k], hours[k]);
                k++;
            }
        /* Read in next name */
        printf ("\nEnter employee name (^D to quit): ");
    }
}

Exercise

As an exercise, you may wish to add an “update” entry to the service program and write a corresponding update program. The update program should read in new data for each department from the terminal, and send this data in a message addressed to the update entry number of the service. The update entry should read the data out of the message and rewrite the files department1, department2, …. If you have a shared file system, each member should rewrite only the files corresponding to the departments it is responsible for; if you have separate copies of the files at each member, each member should update all the files. An interesting observation is that because ISIS ensures that message delivery events occur in the same order everywhere, you can continue to send query messages to the service even as an update message is being sent. It will never be the case that some members respond to a query based on old information, while others respond based on updated information - an important property for many applications.

But why does it work?

It is possible that you don’t believe that the program above will work. Here’s what seems to be a counter-example. Consider a query that is being sent to the service just about the same time as one of its members fails. Assume that the broadcast message reaches some members before the failure is noticed there (i.e. before the routine group change is called there), while it reaches the other members after group change is called. The first set of members respond based on the departments assigned to them before the failure, while the second set respond based on the new assignment of departments. Clearly, it is now possible for two reply messages to contain information about the same department, while the files for some other departments may not be searched at all. One of the main features of ISIS is that such anomalous orderings do not happen. The program above works correctly only because the notification of membership changes and the delivery of broadcast messages occur in the same order at all the members. ISIS guarantees that all events (including broadcast message deliveries, monitor notification, and a host of other functions to be discussed later) occur in the same order at all processes. This is true even for the notification of unpredictable events like process or site failures. It is this feature that makes programming with ISIS so simple. In the absence of this ordering guarantee, every query in our example would have to involve some kind of agreement protocol to ensure that the members agreed on the current state of the group. This not only muddles the application, but also leads to rather poor performance. ISIS insulates programmers from this level of complexity. This allows them to work in a simple and ordered environment and makes it possible to build distributed applications that would otherwise be intractable. We expand upon this concept below.

Ordering in ISIS

To illustrate how the ordering of events works in ISIS, let us first look at what an execution might look like if we didn’t have any ordering guarantees. Figure 1.2 shows three processes A, B, and C as they join and leave the process group Pgroup, while two other processes P and Q send messages to this group. The figure also shows (in curly braces) the view each process has of the current group membership. Notice the confusion. A receives m1 before m2, while B receives m2 before m1. If A and B were maintaining copies of the same data structure, for example, and m1 and m2 were requests to perform operations on this data structure (e.g. add an item to a queue, or remove the first item on the queue), then performing them in different orders could lead to the copies of the data structure becoming inconsistent. So additional communication is necessary before A or B can act on any incoming request to avoid such inconsistencies. Further in the execution we see that A receives m3 when it thinks that Pgroup consists of just A and B, while B and C receive it when they think the group contains A, B and C. We have already seen in our time service example that handling a message based on inconsistent views of the group membership could lead to Figure 1.2: An execution in a disordered world. incorrect results. Again, the only way to avoid this is to run some kind of agreement protocol for every incoming request. The figure also shows m4 being delivered to processes with inconsistent group views, this time because of a failure.

How does ISIS help? A programmer would like to think of actions like the delivery of a broadcast message or the notification of a group membership change as a single event, even though they consist of parts that take place in more than one process and possibly at different times. For example, one would like to be able to write a program thinking, “When the group receives the message broadcast by process A, do something,” or “when the group is notified of the failure of process B, do something else.” One look at Figure 1.2 should convince you that this kind of thinking is not possible in a disordered environment. The programmer is forced to consider the possible interleavings of the various events and cannot think of distributed events like message delivery or failure detection as single units. A programmer using ISIS, on the other hand, is guaranteed that distributed events like broadcast message deliveries, notifications of group membership changes (even if they are due to failures), and many other kinds of events will occur in exactly the same order in every process. In other words, interleavings like those in Figure 1.2 will simply never happen in ISIS. Figure 1.3 shows an execution that could occur in ISIS with the same set of events. Notice how much simpler things become. A programmer can work with the knowledge that each process has the same view of the world when an event like a message delivery or membership change occurs (because each process has seen the same preceding set of events and in the same order). Since the programmer knows the algorithm each process follows, he or she can code each process to make unilateral decisions and know that they will all make consistent decisions. No special agreement protocols need be coded (ISIS does all this hard work for you). The result is a program that is simpler to code, easier to understand, and quicker to debug.

One feature of Figure 1.3 is worth elaborating. Observe the delivery of m3. At the time P initiated the broadcast, process C was not a member of Pgroup. However, by the time delivery occurred, the members had been notified of C’s join. The question arises of whether m3 should be delivered to C or not. P broadcasts m3 to the group Pgroup, and if it is treating the group as an abstract entity, it should not be concerned with the actual membership of the group. On the other hand, if a member receives a broadcast message when it has a certain view of the group membership, it is reasonable for it to expect that the message was sent to all the other Figure 1.3: An execution in the ISIS environment. members in its view of the group. This is precisely what ISIS guarantees. If a member of a process group receives a broadcast message addressed to the group, then a copy of the message will also be sent to all other members that it knows to be in the group at the time the message is received (this membership may be different from when the send occurred). Accordingly, copies of m3 are delivered to A, B and C. It follows from this that all the members will have exactly the same view of the group membership when any particular broadcast message is received.

Virtual synchrony

The discussion above should have given you an idea of how the ordering of events ISIS makes it easier to write distributed programs. To enable you to use ISIS most effectively, however, we urge you to make one more conceptual shift in the way you view ordered events. Compare Figure 1.3 with Figure 1.4. In Figure 1.4, each process sees the same set of events and in the same order as in Figure 1.3. In other words, unless a process actually looks at a clock and records the time, the execution in Figure 1.4 is indistinguishable from the one in Figure 1.3, at least from the point of view of any individual process. The difference is purely conceptual and lies in the way you, as the programmer, look at the execution. Figure 1.4 shows distributed events like message delivery happening everywhere at the same time (i.e. in synchrony). Of course, ISIS does not guarantee that distributed events will actually be synchronized; it only guarantees that they will be ordered as in Figure 1.3. But as we earlier observed, a process cannot distinguish the ordered execution (Figure 1.3) from the synchronous one (Figure 1.4). What this means is that a programmer can code each process as if the execution will actually be synchronous. Any actual execution in the ISIS environment will only be ordered, not synchronized, but a process will not be able to tell the difference (unless of course it records the clock time). So any code written as if the environment were actually synchronous will work correctly when run under ISIS. This is why we call the ISIS execution environment virtually synchronous.

Virtual synchrony enables a programmer to write code while thinking of distributed events as occurring everywhere at the same time - precisely the kind of thinking we said was impossible in a disordered environment. To actually make distributed events happen simultaneously would be wasteful and inefficient because this would mean giving up the vast potential for con-Figure 1.4: A synchronous execution. currency normally available in a distributed system. Instead, ISIS enforces enough order that the resulting code works correctly, while not sacrificing concurrency. This idea goes beyond message delivery and the notification of events. Each of the ISIS tools is designed with virtual synchrony in mind. Even though they are quite complex and concurrent internally and often involve a number of rounds of communication, they can all be used as if their actions happen instantaneously and indivisibly at all the relevant processes. The state transfer tool described below is one such example. The result of virtual synchrony, then, is to remove from the programmer much of the complexity that arises from distribution, concurrency and fault-tolerance, making it as easy to write a distributed program as it is to write one for a single central machine.

State transfer

Let us go back to our time-service example. The rule we used to divide the work has one big disadvantage. Each time the group membership changed, a member could become responsible for a completely new set of departments. It had to close all its files and open new ones. In a real-life implementation, parts of the file (or all of it) would be read into main memory and fast access structures constructed to search through the data. All this would have to be redone each time the membership changed. Let us instead consider a rule for dividing the work that avoids unnecessary reassignment. For example, we could adopt the rule that when a member leaves the group, its departments are assigned to the member responsible for the fewest departments. A member that joins the group takes over half the departments from the member with the most departments. To compute the new assignments under this rule, it is not enough for a member to know just its own assignment of departments. Each member has to know the assignments of all the other members as well. The code below shows how this might be done.

#include    <stdio.h>
#include    "isis.h"
#define     QUERY_ENTRY     1
#define     MAX_NAMELEN     64
#define     NDEPTS          5
#define     MAX_MEMBERS     10
int         n_assignments = 0;

struct
{
    address his_addr;
    int     his_ndepts;
    int     his_dept[NDEPTS];
}           assignment[MAX_MEMBERS];
address     gaddr;
int         my_index;
int         my_ndepts = 0;
int         my_dept[NDEPTS];
FILE        *my_file_p[NDEPTS];
main()
{
    /* Same as before */
}
service_maintask()
{
    /* Same as before */
}
group_change (gview_p, arg)
  groupview *gview_p;
  int       arg;
{
    char    filename[16];
    int     n_members;
    int     i, small_i, failed_i;
    address small_addr, failed_addr_p;
    /* Compute a unique index for this member */
    i = 0;
    while (!addr_ismine (gview_p->gv_members[i]))
        i++;
    my_index = i + 1;
    /* Record number of members in group */

n_members = gview_p->pg_nmemb;
/* Reassign departments from failed members */
failed_addr_p = &gview_p->pg_failed[0];
while (!addr_is_null (*failed_addr_p))
{
/* Find member with fewest departments */
nsmall = NDEPTS + 1;
for (i = 0; i < n_assignments; i++)
    if (assignment[i].his_ndepts < nsmall)
    {
        small_i = i;
        nsmall = assignment[i].his_ndepts;
        small_addr = assignment[i].his_addr;
    }
/* Transfer departments from failed member */
failed_i = 0;
while (addr_isequal (assignment[failed_i].his_addr,
                                     *failed_addr_p))
    failed_i++;
for (i = 0; i < assignment[failed_i].his_ndepts; i++)
{
    assignment[small_i].his_dept[
        assignment[small_i].his_ndepts++] =
                    assignment[failed_i].his_dept[i];
    if (addr_ismyself (small_addr))
    {
        my_dept[my_ndepts] =
                    assignment[failed_i].his_dept[i];
        sprintf (filename, "department%d",
                                 my_dept[my_ndepts]);
        my_file_p[my_ndepts] = fopen (filename, "r");
        my_ndepts++;
    }
}
/* Remove failed member from assignment list */
for (i = failed_i; i < n_assignments - 1; i++)

            assignment[i] = assignment[i + 1];
        n_assignments--;
        /* Repeat for next failed member */
        failed_addr_p++;
    }
    /* Assign departments to new members */
    /* This code is similar to the above and is left as  */
    /* an exercise.  Note that it must also handle the   */
    /* case when the first process joins an empty group, */
    /* that is, when n_assignments = 0                   */
}
receive_query (msg_p)
  message   *msg_p;
{
    /* Same as before */
}

The integer n assignments and the array assignment describe the way the work is divided among the members. It is an example of “configuration data,” that is data that describes the state of a process group as a whole. One problem still remains. How are these configuration data to be initialized? When a new process joins the group, its configuration data structures must contain the assignment that was in effect just before the join, otherwise group change will go berserk when it is called. In other words, the state of the group at the time of a join must somehow be transferred to the joining process.

pg join provides an option that permits state transfer. When a process joins a process group, the system picks one of the existing members, and calls a user-specified “send routine” in that process to obtain the state to be transferred. A send routine calls the function xfer out one or more times, each time giving it a pointer to a piece of the state, its type, its size (if it is an array), and a non-negative integer “locator” associated with this piece of state. Each call to xfer out resembles a call to bcast that does not wait for replies, and conceptually results in a message being sent to the joining process. (In practice, more than one such message is packed into a larger one and shipped all together, but this is done simply to improve performance.)

At the joining process, a user-specified “receive routine” is called once for each call to xfer out, and it is given the corresponding message and locator. It reads the data out of the message using msg get. Should the process sending the state fail before the entire state is transferred, the system picks another member and calls its send routine. The value of the last locator delivered to the joining process is passed as a parameter to the send routine, so that the new sender can continue the transfer from where it broke off. (If no piece of state has been transferred, the send routine is called with −1 instead of a locator.) Depending on the application, a new sender could instead decide to redo the transfer from the beginning or to transfer something entirely different. The system simply ships the data from the current sender to the joining process, which uses the value of the locator to interpret the data. In our example, a failure in the middle of a transfer invalidates the current configuration data, so a restarted transfer must transfer the whole state from the beginning.

When a process joins the group for the first time (that is, when the group is first created), there is no state to transfer and so no send or receive routines are called. Instead an “initialization routine” is invoked. This is specified by the PG INIT option of pg join, which gives the name of the initialization routine. In our example, the initialization routine sets up the configuration data structure as appropriate for an empty group.

What about a group that doesn’t exist because all its members have failed? Normally, ISIS treats this case by calling the initialization routine. If desired, however, one can also arrange for the group state to be logged on a disk file, by specifying another option (PG LOGGED) to pg join. If this is done, the state will be recovered from the log after a recovery from a total failure of the group. Recovery from a log looks like a state transfer, and is discussed later in the manual.

A final case arises if all operational members fail in the middle of a state transfer to a new member. In this “in between” situation, the join of the new member will fail. The normal course of action is to terminate the new process, and start it again. The second time around, it will join an empty group (i.e. create the group from scratch) and proceed normally. Here is the modified code.

#include    <stdio.h>
#include    "isis.h"
#define     QUERY_ENTRY     1

#define     MAX_NAMELEN     64
#define     NDEPTS          5
#define     MAX_MEMBERS     10
#define     NASSIGN_LOC     1
#define     ADDR_LOC        2
#define     NDEPTS_LOC      3
#define     DEPT_LOC        4
int         n_assignments;
struct
{
    address his_addr;
    int     his_ndepts;
    int     his_dept[NDEPTS];
}           assignment[MAX_MEMBERS];
address     gaddr;
int         my_index;
int         my_ndepts = 0;
int         my_dept[NDEPTS];
FILE        *my_file_p[NDEPTS];
main()
{
    /* Same as before */
}
service_maintask()
{
    int     group_change();
    int     send(), receive(), init();
    /* Join the process group, monitor membership */
    /*  changes , and set up state transfer       */
    gaddr = pg_join ("timeservice",
                        PG_MONITOR, group_change, 0,
                        PG_XFER, 0, send, receive,
                        PG_INIT, init,

                 0);
if (addr_isnull (gaddr))
    exit();
isis_start_done();
}
send (last_locator)
int   last_locator;
{
address addr[MAX_MEMBERS];
int     ndepts[MAX_MEMBERS];
int     dept[MAX_MEMBERS][NDEPTS];
int     i, j;
for (i = 0; i < n_assignments; i++)
{
    addr[i] = assignment[i].his_addr;
    ndepts[i] = assignment[i].his_ndepts;
    for (j = 0; j < ndepts[i]; j++)
        dept[i][j] = assignment[i].his_dept[j];
}
xfer_out (NASSIGN_LOC, "%d", n_assignments);
xfer_out (ADDR_LOC, "%A", addr, n_assignments);
xfer_out (NDEPTS_LOC, "%D", ndepts, n_assignments);
xfer_out (DEPT_LOC, "%D", ndepts, n_assignments * NDEPTS);
}
receive (locator, msg_p)
int       locator;
message   *msg_p;
{
address addr[MAX_MEMBERS];
int     ndepts[MAX_MEMBERS];
int     dept[MAX_MEMBERS][NDEPTS];
int     i, j, len;
switch (locator)
{

case NASSIGN_LOC:
{
    msg_get (msg_p, "%d", &n_assignments);
    break;
}
case ADDR_LOC:
{
    msg_get (msg_p, "%A", addr, &len);
    for (i = 0; i < len; i++)
        assignment[i].his_addr = addr[i];
    break;
}
case NDEPTS_LOC:
{
    msg_get (msg_p, "%D", ndepts, &len);
    for (i = 0; i < len; i++)
        assignment[i].his_ndepts = len[i];
    break;
}
case DEPTS_LOC:
{
    msg_get (msg_p, "%D", dept, &len);
    for (i = 0; i < n_assignments; i++)
        for (j = 0; j < assignment[i].his_ndepts; j++)
            assignment[i].his_dept[j] = dept[i][j];
    break;
}
}
}
init ()
{
/* Initialize for an empty group */
n_assignments = 0;
}
group_change (gview_p, arg)
groupview *gview_p;
int       arg;

{
    /* Same as before */
}
receive_query (msg_p)
  message   *msg_p;
{
    /* Same as before */
}

To illustrate one of the ways that the “locator” argument can be used, we broke the state into four pieces based on type here, and shipped each with a separate call to xfer out. Observe how the send and receive routines match up, and how the locator is used to distinguish the pieces of state. In practice, the state would be divided into pieces based on function rather than on type, with different data structures going into different pieces, for example. Also, there was really no need in our example to send the four pieces in separate calls xfer out; this was done merely to show you how each call to xfer out matched up with a call to the receive routine. All the four pieces could have been sent in one call to xfer out using the format string "%d %A %D %D". In this case, the receive routine would have been called just once, and the data in the message could have been read out with one or more calls to msg get. You may wish to write the code for this as an exercise. The usual reason for calling xfer out several times is for the transmission of a multi-record data structure. A loop that iterates over the records would be used in this case, with the locator giving the record number.

The state transfer operation illustrates another aspect of virtual synchrony. Even though state transfer is a complex operation and may involve a number of messages being sent to and fro, this program was written as if the state transfer and the join occurred instantaneously and indivisibly. For example, we did not bother about query messages being delivered to the sending or the receiving process while the state transfer was still under way, even though the service may well be receiving queries as the state transfer is going on. This works because ISIS guarantees that transfer-state-and-join is a distributed event that is ordered consistently relative to other events, and this ensures the correctness of our program. It is important to observe that the state transfer (or initialization) is ordered before the join (i.e. the state transfer routines are called before the monitor routines are invoked), so the correct state to transfer is the state that existed just before the new member was added to the group, as is the case in our example. The exact sequence of events that occurs during a join is covered in the next chapter.

Observations

This chapter showed you how to develop a distributed application using ISIS. Our example essentially partitioned a database over a number of sites and divided the work of responding to queries among these sites. It was tolerant of failures and dynamically reconfigurable. Notice that our query program did not have to be changed when members joined or left the time-card service; in fact it could continue to run and issue queries as this was happening. We even changed the implementation of the service from one that required at least NDEPTS members to one that did not without changing the query program. Such an application would normally be extremely complicated to program, yet we were able to develop our program in a few relatively simple steps. We also discussed how the ordering properties of the ISIS system and the concept of virtual synchrony made it simple to develop a distributed program by enabling distributed events to be viewed as single units. Another aspect worth remarking on was the methodology we followed. We started with a simple version of the time-card service, and added more features to the service program (e.g. state transfer), with very little of the existing code being changed. This is a consequence of the virtually synchronous approach, and leads to a simple step-by-step development methodology that is used very often in ISIS. One begins with a simple form of the application and then adds more and more functionality, while still re-using large parts of the existing code. In most cases, adding functionality simply means adding options to existing function calls and writing a few new functions. As you become familiar with the various tools in ISIS and learn to take advantage of the simplicity arising from the well-ordered environment that ISIS provides, you will find that writing dynamic and fault-tolerant distributed programs can be as simple as writing programs for a single central machine.

Chapter 2

Basic Facilities

This chapter covers most of the basic facilities of ISIS. Most of the applications you might want to build can be constructed from the set of functions described here. As you gain experience with ISIS, you may wish to read further to learn about the more sophisticated tools, or to find out ways of improving the performance of your application. For each function below, we give its declaration, a description of its parameters, and a short note on what the function does.

Error numbers

Functions that return integer values return -1 if an error occurs (unless a negative number is a reasonable value for the function to return). Functions that return pointers return 0 on error. Functions that return structures return the appropriate null structure (e.g. a function that returns an address returns a null address). When an error occurs, the global variable isis errno usually contains an error number indicating its type. This is often also the return value of functions that return integers. Constants of the form IE XXXX are defined in the file isis errno.h to refer to error numbers. The function isis perror(string) prints out string: followed by a textual description of the error indicated by isis errno. Any exceptions to these rules will be indicated in the description below.

2.1 Sites

The term “site” refers to a machine that has ISIS running on it. Sites Site and incarnation numbers, site-id’s are organized into clusters, with each cluster having up to 31 sites. In the current implementation, there can be only one cluster, numbered 0. Each site in a cluster is assigned a number between 1 and 511^{1} through the ISIS “sites” configuration file (see Appendix A). This number is called the site number. ISIS gives each site an incarnation number, which is initially 0. It is incremented by 1 each time a site crashes and then comes back up. The site-id of a site contains its site number and its incarnation number. The type site id is defined as follows.

typedef short   site_id;

Since site-number 0 is not used, lists of site-id’s can be terminated by a null site-id.

Site-id’s are accessed using these macros.

MAKE_SITE_ID (s_no, incarn)  /* Return a site-id containing */
                             /* the given site number and   */
                             /* incarnation number          */
SITE_NO (s_id)          /* The site number contained in the */
                        /* given site-id                    */
SITE_INCARN (s_id)      /* The incarnation number contained */
                        /* in the given site-id             */

The following global variables are made available to ISIS applications.

int      my_site_no;     /* Site number of this site        */
int      my_site_incarn; /* Incarnation number of this site */
site_id  my_site_id;     /* Site-id of this site            */
char     my_host[64];    /* Full host name of this site     */

The ISIS system keeps track of which sites are currently active in the cluster and stores this information in the site view structure at every site. This structure is updated whenever a new site joins the cluster, an existing site is deemed to have crashed, or a site that was down comes back up. ISIS runs a protocol that ensures that every operational site in a cluster sees the same set of joins, crashes or recoveries, and in the same order. Crashes are detected by the system using timeouts. This means that if a site does not respond for a long time, it might be considered to have crashed even when it is just overloaded. If this happens, the system shuts off all communication to and from this site and will force it to temporarily halt and come back up again with a new incarnation number (when this happens, a message is printed in the log of the affected site: I am dead. Site xxx/xxx told me so). This is necessary if we want to ensure that all joins, crashes and recoveries are observed in the same order everywhere. The timeout interval is large, and is adaptively changed if the measured response time for a site seems high. The rule used is such that the probability of an operational site being forced to undergo recovery is rather small.

1ISIS is initially configured to limit site-numbers to a maximum of 127. This limit can be changed provided that the system and all ISIS user programs are recompiled.

The site view structure can be examined by calling sv getview:

siteview *
site_getview()

Get information about the site view

sv getview returns a pointer to the site view structure, which is defined as follows.

typedef struct
{
    int         sv_viewid;
    site_id     sv_slist[MAX_SITES + 1];
    u_char      sv_incarn[MAX_SITES + 1];
    bitvec      sv_failed;
    bitvec      sv_recovered;
} sview;

sv viewid is initialized to 0 and is incremented each time the site view is changed.

sv slist is a list of the site-id’s of all operational sites (terminated by 0).

sv incarn[i] gives the incarnation number of the site with site number i. If the site is down, its incarnation number is the defined constant

     DOWN INCARN.

sv failed and sv recovered are bit vectors describing which sites failed or recovered between the last site view and the present one. In sv recovered we also include sites that join the system for the first time. See Appendix B for a description of the bitvec type and the routines used to access the bits. For manipulation of the failed and recovered bit vectors, the most important of these is bis(bvec,bno), which tests to see if bit bno is set in bitvec bvec.

The macro SITE IS UP (s no, incarn) returns TRUE if site number s no is up and has incarnation number incarn.

2.2 Addresses

An address in ISIS is a structure used to identify a process or process group. It is most often used in sending messages to a process or a group. The global variable my address contains the address by which ISIS knows the current user process. Another variable, NULLADDRESS, contains a null address, which is often used to terminate lists of addresses.

address  my_address;    /* Address of this process */
address  NULLADDRESS;   /* A null address          */

The following functions are used to deal with addresses.

int
addr_cmp (addr_1, addr_2)
  address   addr_1, addr_2;

Compare two addresses

This function may be used to sort addresses. It returns the 0 if the addresses are equal, a negative integer if addr 1 is “less than” addr 2, and positive if addr 1 is “greater than” addr 2.

int
addr_isequal (addr_1, addr_2)
  address   addr_1, addr_2;

Test addresses for equality

This function returns TRUE if the addresses are equal and FALSE otherwise.

int
addr_isnull (addr)
  address   addr;

Is this address null?

This function returns TRUE if the addr is null and FALSE otherwise.

int
addr_ismine (addr)
  address   addr;

Is this address mine?

   addr ismine returns TRUE if the addr equals my address and FALSE

otherwise.

int
paddr (addr)
  address   addr;

Print a single address

Prints an address using the format (site/incarn:pid.entry). If possible, prints the entry number to a text string. The address is output to standard output with no spaces before or after it.

int
paddrs (alist)
  address   *alist;

Print address list

Prints a list of addresses by repeated calls to paddr.

For completeness, we give a description of the address structure, although addresses should normally be accessed through the routines above, and the contents of the structure should not be important. address structure

typedef struct
{
    u_char      cluster;    /* Cluster number     */
    u_char      site;       /* Site number        */
    u_char      incarn;     /* Incarnation number */
    u_char      entry;      /* Entry number       */
    u_char      type;       /* Type of address    */
    union
    {
        short   u_process;  /* Process-id         */
        short   u_groupid;  /* Group-id           */
    }   ad_un;
}   address;
#define process ad_un.u_process
#define groupid ad_un.u_groupid

In the current version of the system, the cluster number is always 0. The entry field is filled in with the entry number when this address is being used to send a message and is 0 otherwise. The type field contains the defined constant ISAPID if the union contains a process-id and ISAGID if it contains a group-id. For two addresses to be considered equal they must first have the same cluster, site, incarn, type, and union fields. When comparing entry numbers, entry 0 is treated as a wildcard (recall that entry numbers normally start with 1). When comparing addresses, the rule used is thus that either the two entry fields must be equal or one of the entry fields must be 0.

2.3 Messages

A message is simply a receptacle for carrying typed data from one process to another. Typically a process creates a message, puts data into it, and uses the ISIS broadcast mechanism to have copies of the message delivered to one or more processes. If the representation of a data type varies from one machine to another (e.g. some machines store integers with the highorder byte first, others with the high-order byte last), ISIS ensures that appropriate conversions are made. This section describes how messages are created and deleted, how data are put into and read out of messages, and how to perform other operations on messages. It covers enough for most normal applications, but for advanced message handling routines see Chapter 3.

message *
msg_newmsg()

Create a new message

msg newmsg returns a pointer to a structure of type message which can be used in other operations to access the newly created message. A pointer of this type will be called a message pointer.

msg_put (msg_p, formatstr, arg1, arg2, ...)
  message *msg_p;
  char    *formatstr;

Copy data into a message

msg p Message pointer. formatstr Format string giving the number and type of the arguments that

follow it (see below).

The interface for msg put is similar to that of the function fprintf. The arguments arg1, arg2, … are copied into the message. Multiple calls to msg put have the same effect as a single call with all the arguments concatenated together, that is successive calls result in the new data being stored after the data already in the message.

message *
msg_gen (formatstr, arg1, arg2, ...)
  char    *formatstr;

Create a message and copy data into it

formatstr Format string giving the number and type of the arguments that follow it (see below).

msg gen is a shorthand for a call to msg newmsg followed by a call to msg put. It returns a pointer to a message into which data has already been copied.

int
msg_get (msg_p, formatstr, arg1, arg2, ...)
  message *msg_p;
  char    *formatstr;

Read data out of a message

msg p Message pointer.

formatstr Format string giving the number and type of the arguments that follow it (see below).

This function resembles fscanf. Each successive call to msg get begins by reading the item after the last one read. It returns the number of items read (0 if there are no more items). It aborts the scan and returns -1, setting isis errno to IE MISMATCH, if the type of the item in the message fails to match the type of the item specified in formatstr.

msg_rewind (msg_p)
  message *msg_p;

Set up a message to be re-read msg p Message pointer.

You may wish to re-read the contents of a message from the beginning after one or more calls to msg get have been made. msg rewind sets the “read indicator” back to the beginning of a message, so that the next call to msg get will start with the first item. Calls to msg put are unaffected by

msg rewind.

msg_delete (msg_p)
  message *msg_p;

Release the space allocated for a message

msg p Message pointer.

msg delete releases the space allocated for a message, unless you have incremented its reference count (see below), in which case it decrements the reference count. When the reference count drops down to its initial value, the space is released. The following rules explain when to call msg delete.

• You must call msg delete for any message you create by calling

     msg newmsg or msg gen.

• You must call msg delete for any messages you obtain using the %m format item in a call to msg get.

• You must not call msg delete for any message delivered to you as an argument to a task. The system automatically deletes such messages when the task terminates.

• You must call msg delete once for every call to msg increfcount (see below).

msg_increfcount (msg_p)
  message *msg_p;

Increment the reference count of a message

msg p Message pointer.

The system automatically deletes messages delivered as the argument of a task when the task terminates. If you wish to retain a message beyond task termination, you can increment its reference count. The message will then be retained until msg delete is called explicitly once for each increment of the reference count.

Format strings

Format strings are used to denote the number and the type of the arguments following the format string, in a manner similar to the functions fprintf and fscanf. A format string is a null terminated string containing one or more of the format items described below. You may include other printable characters in a format string to improve readability; these are ignored in constructing or reading the message and serve the same function as a comment. The basic format items and the types they represent are given below. A number of examples are given at the end of this section, and a more complete list appears later in this documentation.

%c A variable of type char.

%s A pointer to a null-terminated string of characters.

%d A 4-byte integer variable.

%l Same as %d.

%h A 2-byte integer variable.

%a A variable of type address.

%m A message pointer.

%f A double-precision floating point variable (Not currently supported).

In msg put, a format item in the format string means that the string will be followed by an argument of the corresponding type, the order of the arguments being the same as the order of format items in the string. msg put copies the data from these arguments into the message. In the case of a message pointer (%m), the message pointed to is copied as a whole into the other message. In msg get, each format item in the format string means that the string will be followed by a pointer to a variable of the corresponding type. The data from the message is copied into the variable. In the case of a message pointer (%m), the corresponding variable is set to point to a message copied out of the original message. The message copied out must be explicitly deleted by calling msg delete. The type float is currently not supported. To put floating point data into a message, you will have to write them into a character buffer using sprintf and copy the characters into a message. The floating point data can be reassembled from the characters read out by using sscanf.

Most of the format items above have an array version, obtained by replacing the lower case letter in the item by the corresponding upper case letter (e.g. %D for an array of 4-byte integers). The two exceptions are %s and %m. msg put and msg get expect two arguments for each array item. In msg put the first argument is an array of the corresponding type (or equivalently a pointer to the first element of such an array) and the second is the number of elements to copy into the message. In msg get the first argument is a pointer to an area large enough to store the array and the second is a pointer to an integer. msg put sets the value of this integer to the number of array elements read out of the message.

Using msg get as above to read an array out of a message requires that the maximum size of the array be known in advance. A malloc version is provided for each type of format item to cover the case where this size is not known. This version of format item has the symbol “+” after the “%” (e.g. %+D for an array of 4-byte integers). When used in msg get, ISIS will allocate enough space for the array using the malloc system call. You must explicitly release this space by calling free. Again, msg get expects two arguments for each %+ format item. The first one is a pointer to a pointer variable of the given type and the second is a pointer to an integer variable. The pointer variable is set to point to the start of the malloc’ed space, while the integer is set to the number of array elements read out of the message.

If you wish to avoid copying arrays, you may use the “in place” versions of the array format items. This version of format item has the symbol “-” after the “%” (e.g. %-D for an array of 4-byte integers). The arguments expected by msg get are the same as for the malloc version. The difference is that instead of returning a pointer to malloc’ed space into which the array is copied, msg get returns a pointer to the array in the message itself. Use this feature with care, as unpredictable things can happen if you use the pointer to write new data into the array, or if you try to access the array after the message has been deleted.

Examples

Example 1 This code creates a new message, copies the values of a long and a short integer into it, and later deletes the message.

long        x;
short       y;
message     *msg_p;
    ...
msg_p = msg_newmsg();
msg_put (msg_p, "%d %h", x, y);
    ...
msg_delete (msg_p);

Example 2 This example copies the first five elements of an array of addresses and an integer value into a message.

address     alist[10];
int         number;
message     *msg_p;
    ...
msg_put (msg_p, "%A%d", alist, 5, number);

Notice that the array format item %A corresponds to two arguments, the address of the first element to copy (alist) and the number of elements to copy (5). What would have happened if we had &alist[2] instead of alist in the call to msg put?

Example 3 The data put into the message in Example 1 can be read out as follows.

long        a;
short       b;
message     *msg_p;
    ...
msg_get (msg_p, "%d This is the short one -> %h", &a, &b);

Example 4 The array elements added in Example 2 can be read in two ways. If the maximum size is known (say, 15), we could read it out as follows.

address     addrlist[15];
int         n_elem;
message     *msg_p;
    ...
msg_get (msg_p, "%A", addrlist, &n_elem);

After this call, the addresses in the message will be stored in the first five elements of the array addrlist, and n elem will have the value 5. If the maximum size is not known, the following alternative may be used.

address     *addrlist_p;
int         n_elem;
message     *msg_p;
    ...
msg_get (msg_p, "%+A", &addrlist_p, &n_elem);
    ...
free ((char *) addrlist_p);

Either alternative can be followed by

int         num;
    ...
msg_get (msg_p, "%d", &num);

This will store the value of number in Example 2 into the variable num.

Example 5 The following example creates two messages, copies some data into each of them, then puts a copy of the first message into the second. Later, it copies all the data out again.

int     a1, a2, b2, b2, n_elem;
char    c1, c2, d1[10], d2[10];
message *m1, *m2, *m3;
    ...
m1 = msg_newmsg();
m2 = msg_newmsg();

        ...
    msg_put (m1, "%d%c", a1, c1);
    msg_put (m2, "%d %C", b1, d1, 10);
    msg_put (m2, "%m", m1);
        ...
    msg_get (m2, "%d %C %m", &b2, &d2, &n_elem, &m3);
    msg_get (m3, "%d %c", &a2, &c2);
        ...
    msg_delete (m1);
    msg_delete (m2);
    msg_delete (m3);

At the end of this code, a2, b2, c2, and d2 will have the values that were in a1, b1, c1, and d1 respectively. Notice that m1, m2, and the message m3 obtained from msg get must be deleted explicitly. See the rules under

msg delete.

2.4 Broadcasts and replies

A broadcast involves sending a message to a process or process group and optionally collecting a specified number of reply messages from the recipients. If a broadcast is made to a process group, a copy of the message is sent to each of its members. The delivery of broadcast messages are ordered relative to one another. By this we mean that if any pair of broadcast messages go to overlapping destinations, they will be delivered at all such destinations in the same order. Broadcast message delivery is also ordered relative to other distributed events like the notification of group membership changes (see below). As a consequence of this, if a member of a process group receives a broadcast message addressed to the group, then a copy of the message will also be sent to all other members that it knows to be in the group at the time the message is received. (It follows from this that all the members will have exactly the same view of the group membership when any particular broadcast message is received.) In terms of our virtual synchrony model, this means that the delivery of any given broadcast message can be viewed as a single virtually synchronous distributed event.

A process performing a broadcast specifies an entry number in addition to the address. This entry number determines which task will be invoked in a recipient to handle this message. Each of the recipients must have associated the given entry number with a task using the isis entry declaration.

isis_entry (entry_no, routine, routine_name)
  int   entry_no;
  int   (*routine)();
  char  *routine_name;

Declare an entry

entry no Entry number.

routine Task to be invoked.

routine name Null-terminated string containing the name of the routine

         routine.

This function declares that when a message addressed to entry number entry no arrives at this process, a task is to be started up with the invocation routine(msg p), where msg p is a pointer to the incoming message. If a message addressed to an undeclared entry number is delivered to a process, it is simply discarded. Entry numbers should be in the range 1 to 50.

Instead of having to call msg newmsg to create a message, msg put to insert data into it, and msg delete to delete it when you are done, the broadcast interface allows you to specify the data you wish to put into a message (as in msg put). The system creates a new message for the data and deletes the message when it is no longer required. On the receiving side, msg get must be used to read data out of the delivered message.

The sending process can specify the number of reply messages it wants to wait for. The constants ALL or MAJORITY can also be specified, denoting that it wants to wait for replies from all or a majority of the currently operational processes to which a copy of the message was sent. The interface allows you to specify where the data in a reply message is to be stored, so you do not have to be concerned with collecting and deleting reply messages. This mechanism is flexible enough to be used as an asynchronous message passing discipline or as a generalized form of remote procedure call.

Note: The replies can only come from processes to which a copy of the broadcast was actually delivered. Thus, if a process joins a process group, it should not attempt to reply to a broadcast that had been sent to the group prior to its joining. This is true even if a copy of the message is passed as part of a state transfer. Were a reply were sent by a non-destination of a broadcast, it would be discarded by ISIS silently.

  int
  bcast (addr, entry, fmt1, arg1, arg2, ..., nwanted,
                                    fmt2, rep1, rep2, ...)
    address     addr;
    u_char      entry;
    char        *fmt1, *fmt2;

Broadcast a message and collect replies

addr Address of the group (or process) to which to deliver the message.

entry Entry number in recipient process(es).

fmt1 Format string for data to be put into outgoing message (see Section 2.3).

nwanted Number of reply messages wanted, or the constants ALL or MAJORITY.

fmt2 Format string for data to be read out of incoming reply messages (see Section 2.3). This and the arguments that follow it may be omitted if nwanted = 0.

  reply (in_msgp, fmt1, arg1, arg2, ...)
    message *in_msgp;
    fmt1    *char;

Send a reply to an incoming message

in msgp Pointer to incoming message.

fmt1 Format string describing how data is to be put into reply message.

fmt1 specifies the type of data to be put into the outgoing message, and the arguments following fmt1 are treated exactly as in msg put. fmt2 specifies how data is to be read out of reply messages (all replies to the same message are read using the same format string). The arguments following fmt2 differ from those in msg get in one aspect. In msg get the arguments are pointers to variables of the type specified in the format string. In bcast, the arguments are pointers to arrays of such variables, the size of each array being at least nwanted. The data from each reply message goes into an element of these arrays, the order in each array being the order in which reply messages are collected.

Normally, a call to bcast returns when nwanted replies have been received, with any subsequent replies being ignored. The return value is the number of replies collected. This function also sets the value of the global variable isis nsent to the number of processes that were sent a copy of the outgoing message, and the value of the global variable isis nreplies to the number of replies collected.

When a specific value is given for nwanted, it is often an error if the number of replies received is smaller than this number. We had originally planned to have ISIS return an error code in this case. However, a problem then arises because the caller will still need to deallocate any memory allocated as a result of the reply format items %+x or %m having been used. In the current implementation, ISIS returns the number of replies received, and the user is expected to decide if a broadcast has failed because too few replies were received.

Null replies

A call to bcast returns when nwanted replies have been received or when all the processes that were sent a copy of the message have either replied or terminated. It is possible to code an application in which it is known that, for example, only 3 out of 6 members of a process group will reply to a given message, and so the sender sets nwanted to 3. If one of the 3 members supposed to reply terminates before replying (possibly due to a failure), there is no way for the system to know that the remaining operational members will never reply to this message. The call to bcast will never return unless the other 3 recipients happen to terminate as well. If this type of situation could arise in your application, recipients of a message that do not intend to reply should inform the system of this by sending a “null reply” to the message. In general, a call to bcast will return when nwanted replies have been received or when all the recipients of a message have replied, terminated or sent null replies.

  nullreply (in_msgp)
    message *in_msgp;

Send a null reply to a message

in msgp Pointer to incoming message.

   Note: A nullreply(msg p) is not the same as reply(msg p, ""). The

former is never visible to the caller, whereas the latter results in an empty reply message that really will reach the caller. In particular, a null reply can never trigger the error code IE MISSMATCH, whereas the latter could do so (this error code arises when the contents of a message do not match with the format items specified in a msg get format string.

  abortreply (in_msgp)
    message *in_msgp;

Abort a broadcast

in msgp Pointer to incoming message.

abortreply causes the caller of the broadcast to stop waiting for replies. Error code IE ABORT is returned, and any replies collected by the system prior to receiving the abort are discarded.

  forward (in_msgp, to, entry, out_msgp)
    message *in_msgp, *out_msgp;
    address to;

Forward a message

in msgp Pointer to incoming message.

to Address of destination.

entry Entry number to use in destination.

out msgp Pointer to outgoing message.

forward is used by a process that is acting as an intermediary between the caller of a broadcast and the process that will actually reply. The system will deliver a copy of out msg to the designated address arranging that any reply sent to out msg is delivered to the sender of in msg. Although it is expected that out msg will generally be the same as in msg, this is not required, and in fact the two messages can be completely different (for example, this can provide a way for a trusted intermediary to avoid forwarding access credentials). Routines are available for determining whether or not a message has been forwarded (msg isforwarded (msgp), for determining the “original sender”, to whom replies will be delivered (msg getsender (msgp), and for determining the “most recent” sender of

a message (msg gettruesender (msgp).

Programming considerations

The bcast interface may seem unusable if the number and type of data items to be put into a message or a reply may vary at runtime, or if replies from different recipients carry different types of data. (You may wish to put calls to msg put in a loop or in an if-statement, for example.) Another interface that gives you explicit control of the message to be sent is described in Chapter 3. It also gives you greater flexibility in specifying destinations for a broadcast message (you can specify multiple process groups, for example). Another way around this problem is to create your own message using msg newmsg, put in the data as required, and copy this message as a whole into the broadcast (or reply) message using the %m format item. On reception, this message can be extracted using %m and the data can then be read out of the extracted message using msg get. Remember to call msg delete on any message you create or read out of another.

2.5 Process groups

Process groups form the unit upon which many ISIS operations are based, the most common one being to broadcast a message to the members of a group and obtain replies. The process group mechanism also provides options to allow state information to be transferred to a joining process, to enable logging of data on disk, to automate the recovery of the group from disk should all the members fail, and to authenticate the credentials of processes attempting to join or access the group. Some of the ISIS facilities that operate based on a process group are

Replicated data. This consists of mechanisms for replicating data among the members of a group. See Chapter 7 for details.

Distributed execution. This consists of a collection of methods for distributing the execution of a request over the members of a process group (Chapter 8). For example, the coordinator-cohort tool provides a support for distributed executions where one member of a process group (the coordinator) carries out a computation, while other members (the cohorts) monitor the coordinator and take over to complete the computation if the coordinator fails.

The token tool. Provides synchronization among the members of a process group. It includes features to handle the failure of a process holding mutual exclusion (Chapter 9).

Process groups are intended to be highly dynamic entities. A process can create a new group, join an existing one, or leave a group at any point in its computation. Membership in a process group is cheap, and any given time, a process may be a member of several groups. Conversely, several different groups may have the same membership. It is possible for a group of processes to temporarily form a group to make use of one of the options of the process group mechanism or to invoke one of the tools listed above, after which they may all drop out of the group. This section describes the routines that deal with joining, leaving, and obtaining information about process groups.

Groups have symbolic names , and this raises the question of uniqueness. Because ISIS is intended to be useful in large networks, the namespace has been divided into naming “scopes” or domains. A scope is just a set of sites, defined in the system “sites” file at system startup time. Although sites can crash and reboot, the scope remains static. One site may be a member of more than one scope. All sites belong to the global scope.

A group name must be unique within the scope in which it was created, and namespace searches are limited to the scope specified at the time the operation was invoked. The bigger the scope, the more costly these rules are for ISIS to enforce. To obtain the best possible performance, namespace scopes should be small and “accurate”. For example, on a factory floor, each manufacturing cell might be given a namespace scope of its own. Groups formed internal to the cell could thus have names confined to the cell’s namespace scope, and any costs associated with creating or searching for those names confined to the sites that comprise the cell. As a network gets large, controlling these costs becomes critical to obtaining good performance.

The programmer specifies the scope within which ISIS should search for a process group name by using a special notation. A group name is either given as a simple string, e.g. “timeservice” or “/pmake/mygroup”, or in the form “@scope:name”, e.g. “@building2:timeservice”. The scope name and group name are each limited to 64-characters in length. The global scope, which encompasses all sites, is specified by “@*:name”. If no scope is specified, the scope will be the scopes to which the site where your application is run belongs (as defined in the sites file; see “Setting up ISIS”). If none are specified in the sites file (which would certainly be an error) the global scope is assumed.

To avoid accidental name conflicts within a scope, we recommend that a UNIX file-system style of naming groups be employed: “/pmake/mygroup” rather than “mygroup”.

If ISIS cannot map the scope you give to a set of sites, group create and lookup operations will fail. The cmd tool can be used to list the currently known scopes, to cause the sites file to be rescanned after a change is made (perhaps to add a new site or scope), and to list the process groups known in any specified scope. This tool is described in section 14.10 of the manual.

Creating and joining process groups

address
pg_join (gname,
            :
            PG_KEYWORDi, argi1, argi2, ...,
            :
        0)
  char  *gname;

Join a process group. Optionally monitor membership, transfer state, etc.

gname Null-terminated string giving the name of the group.

If a group with the given name already exists in the specified scope, the process calling pg join is made a member of the group. Otherwise, a new group is created with the calling process as its only member unless the PG DONTCREATE option is specified (see below). The address of the group is returned. If the group does not exist in the specified scope, and the scope does not include the calling site, pg join will fail and return NULLADDRESS. Note: The new member can be at a site that is not included in the scope of the search, but in this case if all the other group members fail and only the new member remains operational, searches using the original scope will not find the group.

Options to pg join are placed between the first argument and the last, which is always 0. Each option consists of a keyword followed by the arguments required for that option. Some of the keywords are listed below, with their arguments in square brackets. Other options are discussed in later sections.

PG DONTCREATE [no arguments] Disallows group creation if a group does not already exist.

PG LOGGED [fname, reply entry, flush type, end replay] Tells the sys-

tem that the state of this process group should be backed up on a log file. On recovery, if the process group is restarting after a total failure group does not already exist, the log will be reread to recover the group state. Otherwise, if the group was already operational, the log will be ignored and the join will make use of a state transfer from an operational member. Logging and the meaning of the arguments to PG LOGGED are discussed in much more detail in chapter 12.

PG INIT [routine (pointer to a function)] Calls routine (gaddr) if this group is being created and no log for it could be found. The routine is responsible for the first-time initialization of the group, which will have been assigned address gaddr. Warning: the initialization routine will be invoked before pg join returns.

PG MONITOR [routine (pointer to a function), arg (integer)] Sets up a monitor for group membership changes. routine (gview p, arg) is invoked as a task with the new group view and arg as parameters whenever the group membership changes (see pg monitor below). Warning: the monitor routine will trigger for the first time before the pg join returns. Notice that the group address is available as part of the groupview data structure.

PG XFER [domain (integer), send routine, receive routine (pointers to

functions)] Transfers state to the joining process (see State transfer below).

PG BIGXFER [no arguments] Specifies that a TCP/IP channel should be used to transfer state, as it is likely to contain a large amount of data (see State transfer below).

PG CREDENTIALS [credentials (null-terminated string)] Defines credentials

to be the credentials string for this process. It is presented to an existing member of the group to obtain authentication for this join request.

PG JOIN AUTHEN [routine (pointer to a function)] Prevents processes from joining the group without presenting credentials. When a process attempts to join, routine is called in one of the existing members with the credentials string of the joining process passed as its first parameter. If routine returns −1, the join is refused.

PG CLIENT AUTHEN [routine (pointer to a function)] Makes it possible to prevent processes that are neither members nor clients from communicating with this group (see pg client below). When a process attempts to become a client by calling pg client, routine is called in one of the existing members with the credentials string of the process passed as its first parameter. If routine returns −1, the pg client request is refused.

The sequence of events that occurs when a pg join is invoked is as follows. First, either the the initialization routine or the state transfer receive routines will be invoked, depending on the current state of the group. Next, the first monitor invocation will take place. After this pg join will return. Only after all of these events will incoming requests to the group begin to be processed. Reception of incoming requests will be deferred even longer if the task that called pg join is the startup task. In this case, the group will not receive incoming requests until that task either terminates or calls

isis start done

Inhibit new members pg_join_inhibit(state);

from joining a process group

state  One of TRUE or FALSE.

This facility is intended mostly for use in coordinator-cohort computations (Chapter 8). pg join inhibit temporarily prevents new processes from joining any process group that the process calling pg join inhibit is a a member of. The function inhibits joins as long as the TRUE requests outnumber FALSE requests. A process attempting to join a process group when joins are inhibited is simply made to wait until they are not.

Inhibit new members isis_inhibit_joins(entry-number);

from joining a process group while an entry is active

This facility is intended only for use in guarded broadcasts (Chapter 11). isis inhibit joins arranges for the system to call pg join inhibit when a message to the designated entry point is received, and to undo this when the entry terminates. The feature is needed only in connection with guarded broadcasts.

Comments about possible deadlocks during pg join

Users of pg join should be aware that deadlocks can arise from certain patterns of interactions between joining processes and the groups that they join, especially when the call to pg join is done during startup (from the main task, before isis start done has been called).

First, notice that if a member of a process group has inhibited joins than a join request may be forced to wait, possibly indefinitely in the case where the inhibit was due to a bug. In such a case it would be necessary to obtain a client dump (see Chapter 14). By interpreting the dumps from the process group members and the process attempting to join, it is easy to determine what has happened.

There are also more insidious ways to cause deadlocks. In particular, since pg join involves a request by a potential new member to the current members of a group, during the interval between when a new member joins and when it first begins accepting requests, further attempts to join the group will hang. Thus, a deadlock can occur if two processes simultaneously both attempt to join the same two groups during their startup sequence, and do so in different orders. Such a deadlock could be eliminated by calling isis startdone before doing the second pg join in either process, or by issuing the two pg join calls in the same order in both processes.

Creating subgroups

address pg_subgroup(pgaddr, sgname, incarn, members, clients)
  char *sgname;
  address members[], clients[];

Create a process

group with prespecified initial

membership

pgaddr Address of the parent group, caller must be a member.

sgname Scope and name for the subgroup, as in pg join.

incarn Incarnation number, normally specified as 0.

members Null-terminated list of initial members, subset of parent group membership.

clients Null-terminated list of initial clients, unrestricted.

Some applications dynamically create subgroups of existing groups and would pay a high cost if subgroup members had to joins one by one. pg subgroup is provided for this purpose. The group is created with a prespecified membership and client list. The members must be a subset of the members of a specified parent group. Aside from the way in which it is created, a subgroup is a completely normal process group and permits all the ISIS process group operations.

Subgroup members should manually call pg monitor to monitor the subgroup membership (see Section 2.6) and allow xfers xd to enable state transfers (see Section 2.7), if desired. Often, it is helpful for the process that creates the group to send an initial broadcast to the members causing them to take these actions.

Leaving a process group

address
pg_delete (gaddr)
  address gaddr;

Delete a process group

gaddr Address of the group to delete; caller must be a member.

pg delete causes the specified group to be deleted. The group membership and client counts drop to 0, triggering all applicable watch and monitor routines, and the group then ceases to exist. If recreated, it will receive a different group-address. Subgroups of a deleted group are not deleted automatically when the parent group is deleted.

pg_leave (gaddr)
  address   gaddr;

Leave a process group

gname Address of a process group.

The process calling pg leave ceases to be a member of process group gaddr. When a process terminates (either normally or because of a failure), this function is invoked automatically once for every group that the process was a member of.

Other functions for dealing with process groups

address
pg_lookup (gname)
  char  *gname;

Get the address of a process group gname Null-terminated string giving the scope in which to search and

the name of the group.

pg lookup returns the the address of a process group, without causing the calling process to join the group.

pg_client (gaddr, credentials)
  address   gaddr;
  char      *credentials;

Become a client of a process group

gname Address of a process group.

credentials Null-terminated string used as credentials.

Process groups can restrict operations to only members or only clients.

If a process group wishes to restrict some of its operations to be done only by members or clients, it should specify PG CLIENT AUTHEN in pg join. When an operation is invoked, it should start by calling pg rank all to verify that the request came from a legitimate client or member (see below). Illegal requests can then be explicitly rejected either by replying with an error indication or by sending a nullreply or an abortreply. Notice that ISIS does not perform this check automatically. To become a client of a process group, a process calls pg client with a string describing its credentials. The client authentication routine is invoked in one of the members, with credentials being passed as its first parameter. If the routine returns −1, the process is not made a client. This mechanism can be used to enforce security policies.

Performance hint: Even if there is no authentication mechanism in place, it might be desirable to make a process a client of a process group. Information about a group is always stored locally at each of its members and clients. Thus clients use a local copy of this information when communicating with the group, which leads to better performance than if this information had to be obtained from another site. So if a non-member process does a lot of communication with a process group, it is advisable to make it a client of the group.

groupview *
pg_getview (gaddr)
  address   gaddr;

Get information about a process

group gaddr The address of a process group (obtained by calling pg join or

         pg lookup).

This function returns a pointer to a group view structure for the process

groupview structure group. The contents of this structure are as follows.

#define         PG_GLEN        128
#define         PG_ALEN        64
typedef struct
{
    int         gv_viewid;             /* View number */
    int         gv_incarn;             /* Incarnation number */
    address     gv_gaddr;              /* Group address */
    char        gv_name[PG_GLEN];      /* Group name */
    short       gv_nmemb;              /* Number of members */
    short       gv_nclient;            /* Number of clients */
    address     gv_members[PG_ALEN];   /* List of members */
    address     gv_clients[PG_ALEN];   /* List of clients */
    address     gv_joined;             /* New member, if any */
    address     gv_departed;           /* Departed member, if any */
} groupview;

The view number is incremented each time the group membership changes. The incarnation number is used by the system to keep track of recoveries when all the members of the group fail. gv joined and gv departed indicate the address of any process that joined or departed from the group since the last membership change, at most one of these will be non-null because only one group membership change happens at a time in ISIS. It is possible for both to be null in the case where the only change was to the list of clients. Both address lists are terminated by NULLADDRESS. The addresses in gv members are ordered according to the rank of the member (see below).

int pg_rank (gaddr, paddr)
  address   gaddr, paddr;

Obtain the rank of a process in a process group, or for group membership process groups, check membership

gaddr Address of process group.

paddr Address of process.

pg rank returns the rank of process paddr in process group gaddr, if it is a member of the group. Each member of a process group has a unique rank, which changes only when the group membership changes. The oldest member has rank 0, the second oldest is rank 1, and so on (ties are broken in the same way everywhere). The rank may be used to give each member of a process group a unique identifier. If the process is not a member of the process group, pg rank returns −1. It can hence be used to test for membership in a group.

int pg_rank_all (gaddr, paddr)
  address   gaddr, paddr;

Obtain the rank of a process or client in a process group, or test for group membership gaddr Address of process group.

paddr Address of process.

pg rank all is just like pg rank, but includes clients in the ranking as well. Clients have larger rank than members. Processes that are neither members nor clients are ranked −1.

pg_signal (gaddr, signo)
  address   gaddr;
  int       signo;

Send a UNIX signal to the members of a

process group

gaddr Address of process group.

pg signal causes the UNIX signal signo to be delivered to the members of a process group. This function bypasses the ISIS ordering mechanisms and is intended to be used only in exceptional situations.

2.6 Monitors and watches

A process uses monitors and watches to ask the ISIS system to inform it when a particular event or type of event occurs. When a process sets a monitor or a watch, it gives the system the name of a routine and an argument for the routine. When the event occurs, the named routine is run as a task within the process, with the argument being passed as a parameter. We say that the process has received a monitor or watch notification. A watch is used for a one-time event like the termination of a specific process, while a monitor is used for a class of events (e.g. to be notified of all future changes to the membership of a particular process group.) Once a watch event has triggered, it will never trigger a second time. A monitor event will trigger repeatedly each time the event in question occurs, until it is explicitly canceled.

All monitor or watch notifications for the same event form a single distributed action that is ordered relative to all other monitor or watch notifications and to broadcast message delivery. In other words, all processes will receive notifications in exactly the same order. Also, it will never be the case that one process receives a broadcast message before a particular notification, while another process receives the same message after that notification. In terms of our virtual synchrony model, then, watch or monitor notifications are virtually synchronous distributed events.

int
sv_monitor (routine, arg)
  int   (*routine)();
  int   arg;

Monitor changes to the site view

routine Routine to be called if the site view changes.

arg Argument to be passed to routine.

If the site view changes (a site failure or recovery is detected by the system), a task is started to execute the function call

    routine (sview_p, arg);

sview p is a pointer to the new site view (Section 2.1). sv monitor returns an integer monitor-id that can be used to cancel the monitor.

sv_monitor_cancel (sv_monitor_id)
  int   sv_monitor_id;

Cancel a site view monitor

sv monitor id Monitor-id of monitor to cancel.

This function returns 0 in the normal case. It takes no action and returns −1 if given a meaningless monitor-id or if the monitor has already been canceled.

int
pg_monitor (gaddr, routine, arg)
  address   gaddr;
  int       (*routine)();
  int       arg;

Monitor changes to the membership of a

process group

gaddr Address of process group.

routine Routine to be called if the group membership changes.

arg Argument to be passed to routine.

If the group membership changes, a task is started to execute the function call

    routine (gview_p, arg);

gview p is a pointer to the group view data structure (Section 2.5) for the named group. pg monitor returns an integer monitor-id that can be used to cancel the monitor. The value will be positive normally; -1 if the group was unknown or the caller was not a member.

pg_monitor_cancel (pg_monitor_id)
  int   pg_monitor_id;

Cancel a process group monitor

pg monitor id Monitor-id of monitor to cancel.

This function returns 0 in the normal case, and error code −1 if given a meaningless monitor-id or if the monitor has already been canceled.

int
sv_watch (sid, event, routine, arg)
  site_id   sid;
  int       event;
  int       (*routine)();
  int       arg;

Watch for a given site to fail or recover

sid Site-id of site to watch.

event  One of W FAIL or W RECOVER.

routine Routine to be called if the requested event occurs.

arg Argument to be passed to routine.

If W FAIL is specified and the site fails, or if W RECOVER is specified and the site recovers, a task is started to execute the function call

    routine (sid, event, arg);

If sv watch is called with NULLSID as the value for sid, routine will be called if any site fails or recovers. In this case, the second parameter to routine will be the site id of the site that actually crashed or recovered. Warning: When sv watch is called with NULLSID, and several failure or recovery events are noted at once, the watch routine will be invoked only once, with the arguments corresponding to one of the events. Hence, if this feature is used, it is recommended that you look at the group view structure to determine the full list of events, and not rely on the arguments to the watch routine.

sv watch returns an integer watch-id that can be used to cancel the watch. If the requested action is meaningless (for example, a request to watch for a site failure of a site that isn’t operational, or to watch for a recovery of a site that is already operational), the routine will return 0. The incarnation number of the parameter sid is used in the case of W FAIL, but is ignored in the case of W RECOVER. If the specified group is unknown, −1 is returned.

sv_watch_cancel (sv_watch_id)
  int   sv_watch_id;

Cancel a site view watch

sv watch id Watch-id of watch to cancel.

This function returns 0 in the normal case, and returns error code −1 if given a meaningless monitor-id or if the monitor has already been canceled.

int
pg_watch (gaddr, paddr, event, routine, arg)
  address   gaddr;
  address   paddr;
  int       event;
  int       (*routine)();
  int       arg;

Watch for a process to join or leave a named group

gaddr Address of process group to watch. paddr Address of process to watch.

event  One of W JOIN or W LEAVE.

routine Routine to be called if the request