Java synchronization to avoid ConcurrentModificationExceptions?

The basic problem with your code is that your objects synchronize on different objects (locks). To fix this, instead of declaring the methods synchronized - which synchronizes on the class's object - synchronize on the requests object itself:

public class Client { //main class

 public static void insertRequest(int req_nr, String node, int file_id, long sbyte, int length, int pc_id) {
    ...
    synchronized (requests) {
      requests.put(req_nr, tempr);
    }
    ...
 }

public class ScheduledEvent implements Job {
 public boolean isRequested(long sbyte, int length, int file_id, String node) {
    ...
    synchronized (requests) {
      while (it.hasNext()) {
          req = Client.requests.get(it.next());
          if (req.node.equals(node) && req.file_id == file_id && hits(req.sbyte,   req.length, sbyte, length)) {
            return true;
        }
      }
    }
    ...
 }  
}

You could replace HashMap with ConcurrentHashMap.

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentHashMap.html#keySet%28%29

keySet() Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations. The view's returned iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

The ConcurrentModificationException occurs due to the Fail Fast nature of the iterator on the Maps keyset.

You should probably be using ConcurrentHashMap instead of HashMap, which will allow you to get rid of a lot of your manual synchronization.

UPDATE:

Looking at your question again, I have a couple of questions/suggestions:

1. Does ScheduledThreadPoolExecutor do what you need? I highly recommend using the higher-level concurrency constructs provided in java.util.concurrent where possible, because it's so hard to get concurrency right when you're starting with just the basic concurrency primitives.
2. Assuming the answer to the previous question is no, is there a reason you can't use a classic producer-consumer pattern using a Queue instead of a Map keyed on request number? It seems like one of the BlockingQueue implementations would be ideal for this.

You are A) misunderstanding the use of the volatile keyword, and B) misunderstanding the use of synchronized. This can be a tricky subject so I'll try and give a brief overview of both.

volatile tells the compiler that the variable being referred may be updated by multiple threads, so it must ensure that each thread sees the correct value when it reads/writes to the variable. The reason you are misusing volatile is that when you declare a volatile Object you are telling the compiler the reference is volatile. Ie, the pointer to the HashMap could change at any time (for instance, if you did requests = new HashMap() the pointer would have changed). You are not changing the reference to requests at any time in your program however, so it does nothing to declare it volatile, and as mentioned in another answer, you should declare it final.

synchronized is a keyword that is essentially a shortcut for a lock() on some object. When you use synchronized within the context of an instance of a class, synchronized will lock on the instance. Ie:

class X {
  public synchronized doStuff() {
    ...
  }
}

X instance = new X();
instance.doStuff();

will have the exact same effect as:

class X {
  public doStuff() {
    lock(this) { // or lock(instance)
      ...
    }
  }
}

If you use synchronized in a static context however, the lock generate by synchronized has no instance to lock on, so instead it will lock on the instance of the class type. To simplify, for every class that uses synchronized statements, a synchronized in a static context will lock on lock 1 in all cases, and a synchronized in a non-static context will lock on lock 2 every time. This means there is no multithreading safety unless you make sure things are using the same lock.

One way of making your code work is to use lock(requests) statements explicitly so they all share the same lock. It is not always best practice to actually lock on the object you want to use, rather usually people create a new Object to lock on and not to use for any other purpose to avoid confusion.

Other responses have mentioned using ConcurrentHashMap, this is a valid solution although those answers do not address the root problem here. If you decide to use ConcurrentHashMap however, be sure you understand what safety guarantees it does and does not give you with respect to concurrent modification. It may not always be as you expect.