Suppose I want to implement a 1-D cellular automaton in Prolog (come to think of it, has anyone ever studied cellular automata not driven in synchronous fashion by a central clock? don’t answer this).
For this I need a “randomly accessible” 1-D array of character. A list, being singly linked, sounds less than ideal. In fact, any linked data structures sound like a bad deal. Do I need to go for a C-based opaque data structure?
arg/3 and setarg/3 
I know it sounds crazy.
See my personal notes here. While not specifically about arg/3 it does give some useful details.
Also see the code that the notes are for in this post.
While I have not used these there are a few SWI-Prolog packs for matrix, e.g.
The idea by @EricGT is not at all crazy. This is the closest you get to an “array”. This is exactly how library(hashtable) is implemented at the moment.
For example, you can use message passing between neighbors. Is that what you mean? But!
Your computer is driven by a central clock, so in order to simulate anything that is “not driven by a central clock” you must simulate whatever would be pushing your simulation forward, on the computer with a central clock. So if you tried to use message passing and just let the system handle it, “time” becomes an artifact. Can be useful to study the machine as a black box, for example how the message passing and concurrency is implemented.
Great idea 
A bit beholden to the actual implementation of the Prolog one is choosing, but why not.
For example, you can use message passing between neighbors. Is that what you mean?
I was actually thinking about the theoretical side - if cells don’t all compute their next step in a universal lockstep but sample their surrounding cells probabilistically at random times (but with small spread) and then update. Will the whole system exhibit interesting behaviour or turn into mush? There will be probably be a phase diagram of some sort …
The moniker “N+K trees” seems not be something in common usage.
From O’Keefe’s book:
Suppose you want to represent a collection of several thousand items, but you will need fast access to any one of them. A list is a good way of representing a sequence; it it is not a good way of getting at a particular item. Provided you don’t want to replace elements, it is sufficient to use a tree of terms, with the terms being as wide as your system will permit. A general hack is the N + K-tree, where each node of the tree contains slots for N elements and K subtrees.
This is very Prolog specific; the only other place where I can think of having to distinguish between “1 item” and “N items” as the node’s payload is a filesystem on a block-oriented device. Maybe.
I did (at least partly) - somewhen back in the late 90s. But I can’t remember all that much. Douglas Coupland’s Microserfs was more fun. And Levy’s Hackers. I can’t remember much else, except fat Win32 API manuals, Soltis on the AS/400 and sci-fi by Greg Egan.
Also it seems they are called Asynchronous Cellular Automata
Prolog systems seemed to have had an upper limit to the arity of terms at the time when the book was written. So you needed an N+K tree to represent any “array” longer than that limit.
In SWI-Prolog, there is no such limit. So if your data structure just needs an array, a flat term is good enough.
I might be completely wrong here but my impression is that molecular dynamics simulations work in a similar way (the randomness comes from the initial seed for the state of each individual atom).
I always thought that weather simulations work in a similar way too, but about that topic I really know nothing at all.