when a client is trying to access a topic partition for which the given broker is not the leader. For example a producer can only send new messages to the partition that is considered the leader for a replica set of partitions. Only after the leader partition receives the messages will they be sent to the other brokers that hold the replicas of that partition.
It can happen when the client/producer has stale information about which broker is the leader for a partition. In this case the NotLeaderForPartitionException is thrown by the broker that the client is connecting. Another possible reason , when a leader re-election happened recently (like when restarting brokers one by one in your case and for a short time the leader partitions for certain replicas were unavailable and new leaders were elected for the partitions that used to have a leader on the unavailable broker).
Ideally it is harmless as it is retrial, It can retry and try to send request to other brokers
Kafka maintains a set of in-sync replicas. Only the members of this set are eligible for election as leader. It will be stored in ZK.
Sharing quote from Kafka document “Each partition has one server which acts as the "leader" and zero or more servers which act as "followers". The leader handles all read and write requests for the partition while the followers passively replicate the leader. If the leader fails, one of the followers will automatically become the new leader. Each server acts as a leader for some of its partitions and a follower for others so load is well balanced within the cluster”