The best word to describe this book is “epic”. Kim Stanley Robinson is best known for long and detailed science fiction – his Mars trilogy, for example, but this is much more clearly speculative fiction.
Science fiction and speculative fiction are fairly similar – in fact the nature of speculative fiction is quite similar to how science works – the idea is to change a few details of reality and see how that affects the rest of the world. In speculative fiction, of course, the results are speculative – it isn't like changing what surface something is sliding on to investigate friction. Speculative fiction, however, is much more respectable as a genre than science fiction...
Here, two main things are changed about the world. The Black Death kills almost everyone in Europe, instead of just a large proportion of them, and the story starts with the Mongol Hordes about to invade Europe, but who find everyone dead. The other thing that is changed is that reincarnation happens, which allows the book to take what some of the characters later describe as a Buddhist model of story-telling: following a group of people through successive reincarnations.
In doing so, Robinson cover nearly 1000 years of speculative history, through seeing the same characters reincarnated, sometimes as men, sometimes women, sometimes Muslims, sometimes Chinese, sometimes Indians or Native Americans, in lots of different contexts, so that we see the major turning points of his alternative history.
There's a few things I'd pick up on – he seems unaware of the Christian communities in South India, for example. Sometimes he gets self-referential, especially when discussing historiography or hypotheticals in history, which I can see might annoy some, but I think is quite clever.
It's a clever book, and a fun, thought-provoking read.