E. O. Lawrence Berkeley National Laboratory

Berkeley, California USA

Louise E. Moser

P. Michael Melliar-Smith

Ravi K. Budhia

Department of Electrical and Computer Engineering

University of California, Santa Barbara USA

• Large scale experiments
• Airplanes
• Virtual laboratories Transaction and database systems

• Bank databases
• Stock broker systems

• Asynchronous distributed system
• Processors separated into broadcast domains
• Broadcast domains interconnected by gateways
• Processors and gateways have stable storage Fault model

• Unreliable communication
• Corrupted messages detected
• Fail-stop, timing and omission faults for processors/gateways
• Network partitioning and remerging
• Faults determined by local-area protocol

• Configuration changes Properties

• Uniqueness of topologies
• Consensus
• Termination
• Topology change consistency

• Total order on messages that is consistent across the network
• Preserves causality
• All preceding messages delivered
• Timestamps Safe order

• Agreed order
• All other processors in the configuration have received and will deliver the message unless they fail

• Constrains message delivery by processors transitioning between the same configurations
• Processes deliver the same messages in the same order Extended virtual synchrony

• Virtual synchrony
• Constrains message delivery by processors in separate partitions

Delivery

• Agreed order
• Safe order Membership

• Configuration change messages

Messages timestamped on generation

Gateway operation

• Forwards messages
  • Agreed order
  • Timestamp unchanged
  • New sequence number appropriate to new ring

• Messages forwarded by the gateways in order
• The messages received from the single ring protocol are maintained in a table,
• one column per ring
• When a processor receives a message in agreed order for its local ring, it has received all preceding messages from that message's source ring
• Can deliver low timestamp message in table

• Messages delivered safe by single-ring protocol
• Gateways and processors maintain guarantee vectors
• Gateways broadcast guarantee vectors periodically
• All processors and gateways maintain guarantee arrays
• A message can be delivered in safe order when all entries in the corresponding column of the guarantee array have higher timestamps

• Generated by single-ring membership protocol
• Contains
  • Timestamp of configuration change
  • Unique identifier for new ring
  • Membership of new ring
  • Gateways on new ring

• Sent by gateway when processing a local Configuration Change message
• Inform the rest of the connected network
• of changes to the local topology representation
• Topology representation is updated when
• the message is low timestamp message

• Allows processors and gateways on the ring
• to determine the new topology after a local configuration change
• Details current connected topology (not including the new ring)
• Sent by a gateway when the Configuration Change message is the low timestamp message
• Has same timestamp as Configuration Change message
• Is not forwarded

Gateway x:

• Network Topology message broadcast by x
  • topology = ring A
• Network Topology message broadcast by y
  • topology = ring C
• Topology Change message broadcast by x
  • add rings: B, C
  • add gateways: x (A,B), y(B,C)
  • delete ring: B'

• Two rings (10Mbit/s Ethernet)
• Four Sun IPCs
• One Sun SPARCstation 20 as gateway
• Messages 1024 bytes Performance on a single ring

• Single-ring protocol 768 agreed messages/sec
• Multiple-ring protocol 636 agreed msgs/sec
• Additional overhead 0.27 milliseconds/msg With gateway

• Multiple-ring protocol 631 agreed msgs/sec

Total order derived from timestamps and sequence numbers

Excellent performance

Global total order

Integrated flow control

Consistency maintenance simplified

• Single-ring protocol implemented
• Single-ring protocol simulator completed
• Multiple-ring protocol implemented
• Multiple-ring protocol simulator completed
• Process group layer implemented
• Demonstration application
• Implementation as a kernel module underway
• Security underway
• Gateway filtering underway