diff --git a/common/rfb/DecodeManager.cxx b/common/rfb/DecodeManager.cxx
index ddebf0a..3c1ddb4 100644
--- a/common/rfb/DecodeManager.cxx
+++ b/common/rfb/DecodeManager.cxx
@@ -251,18 +251,27 @@
        ++iter) {
     DecodeManager::QueueEntry* entry;
 
+    std::list<DecodeManager::QueueEntry*>::iterator iter2;
+
     entry = *iter;
 
     // Another thread working on this?
     if (entry->active)
       goto next;
 
+    // If this is an ordered decoder then make sure this is the first
+    // rectangle in the queue for that decoder
+    if (entry->decoder->flags & DecoderOrdered) {
+      for (iter2 = manager->workQueue.begin(); iter2 != iter; ++iter2) {
+        if (entry->encoding == (*iter2)->encoding)
+          goto next;
+      }
+    }
+
     // Check overlap with earlier rectangles
     if (!lockedRegion.intersect(entry->affectedRegion).is_empty())
       goto next;
 
-    // FIXME: check dependencies between rects
-
     return entry;
 
 next:
diff --git a/common/rfb/Decoder.h b/common/rfb/Decoder.h
index f631a55..9a03eb3 100644
--- a/common/rfb/Decoder.h
+++ b/common/rfb/Decoder.h
@@ -33,6 +33,8 @@
   enum DecoderFlags {
     // A constant for decoders that don't need anything special
     DecoderPlain = 0,
+    // All rects for this decoder must be handled in order
+    DecoderOrdered = 1 << 0,
   };
 
   class Decoder {
diff --git a/common/rfb/TightDecoder.cxx b/common/rfb/TightDecoder.cxx
index 24236db..ec329e4 100644
--- a/common/rfb/TightDecoder.cxx
+++ b/common/rfb/TightDecoder.cxx
@@ -46,7 +46,7 @@
 #include <rfb/tightDecode.h>
 #undef BPP
 
-TightDecoder::TightDecoder() : Decoder(DecoderPlain)
+TightDecoder::TightDecoder() : Decoder(DecoderOrdered)
 {
 }
 
diff --git a/common/rfb/ZRLEDecoder.cxx b/common/rfb/ZRLEDecoder.cxx
index c9245c0..c13f286 100644
--- a/common/rfb/ZRLEDecoder.cxx
+++ b/common/rfb/ZRLEDecoder.cxx
@@ -62,7 +62,7 @@
 #undef CPIXEL
 #undef BPP
 
-ZRLEDecoder::ZRLEDecoder() : Decoder(DecoderPlain)
+ZRLEDecoder::ZRLEDecoder() : Decoder(DecoderOrdered)
 {
 }