title: Message ordering in distributed system
body: <p>I want to build a distributed system where I have "threads" (a collection of messages with it's own ID, not a system process) that are distributed across many servers. These threads must have two critical properties:</p>
  
  <ol>
  <li>Each message in thread must have an order number that reflects it's position in thread based on time. For example by saying "thread1/message10" I can get to message #10 in thread #1</li>
  <li>Once new message gets added to thread a system must be able to assign it an order number that is consistent for all instances of thread on all servers and this number must never change. </li>
  </ol>
  
  <p>I want to know if there's any known solution, library or algorithm that can help me implement a second option because now I see it as a big problem because due to many factors different servers can get the same message at different times and that might affect it's order number.</p>
  
  <p>Just to outline my thoughts on a problem so far say I have 3 servers with my distributed thread which already contains 5 messages and each server sends a new message to it's own thread and to remaining two.</p>
  
  <ul>
  <li><p>Naive ordering. Each server think it's own message number is 6 and the remaining two messages from other servers will get their numbers on arrival depending on network latency and many other random factors so order numbers are not consistent across servers. This is unacceptable right away.</p></li>
  <li><p>UTC timestamp based ordering. When each thread gets a new message I take say 10 preceding messages that already have correct order numbers, extract their timestamps and determine a new message's order number by finding it's timestamp place in a list of last 10 timestamps. 
  This might work I guess but it does require that some message's order number can be assigned and then changed at some point which is unacceptable. Also I'm not sure if this will work right when a number of incoming messages is huge.</p></li>
  </ul>
  
  <p>Thanks for all the help.</p>