Distributed systems: Algorithms and file systems

Distributed systems: Algorithms and file systems

1. Mutual Exclusion Algorithms

   • Assume reliable messages and unique timestamps
   • Process trying to enter critical section
     • Sends to all other processes, the name of the section and unique timestamp
     • Enters critical section if it has a lower timestamp than receiver else it is queued
       • Lowest logical clock allowed in
         • Guarantees fairness
         • Grants mutual exclusion without deadlock
   • Process receiving request message
     • Sends an "OK" if not interested in critical section
     • Queues message if it is already in critical section
   • Problems
     • Requires that everyone knows about all other hosts
       • Need to wait for confirmation from all other hosts
     • Algorithm fails if one host fails
       • Reconstruction go network necessary
       • Suitable for stable networks

2. Token ring algorthm

   • Network organised in ring
     • Each node has unique successor
     • Generate token at intitialisation
       • Pass around continuously
         • Whoever has token can enter critical section
           • Only ever one host in CS
           • After leaving CS, pass token to neighbour
   • Properties
     • Detecting lost tokens difficult
     • Detecting dead process easy if sent token is acknowledged

3. Election Algorithms

   • Select new co-ordinator
     • Assume know id of every host on network
   • Two types
     • Bully algorithm
       • P sends message to all hosts with higher id number
         • No response = P wins and becomes co-ordinator
         • Answer received = host with higher number takes over
     • Ring algorithm
       • Any host may send election message
         • Passed around network - each host id added
           • If original host gets message, it determines co-ordinator and sends new message around
             • After it has gone round, host removes it

4. File systems

   • Special problems
     • Naming: identify files system wide with no clashes
       • Location transparency
         • Name gives no hint on location
       • Location independence
         • Files can be moved without name being changed
           • Standard approach: remote mounting
             • Make remote filesystem available under local name
             • Requires name server
     • How are concurrent reads/writes executed?
   • Implementation issues
     • Stateful vs stateless servers
       • Stateless
         • Fault tolerant
         • No open/close requests needed
         • No problem when client crashes
         • Caching employed
       • Stateful
         • Read ahead possible
         • File locking possible
     • Cache inconsistency
   • NFS
     • Make FS available on other hosts

Imágenes y archivos del mapa